one Book a Day

최단 경로 알고리즘. 주요 알고리즘 BFS (완전탐색 알고리즘) 가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구하는 경우 가장 빠르다 다익스트라 알고리즘 (Dijkstra Algorithm) 음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm) 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 전체 쌍 최단 경로 문제, 다수출발, 단일도착 하나의 정점에서부터 다른 하나의 정점까지의 최단 경로를 구하는 경우 A*알고리즘이 적합하다. 다익스트라 특정 노드에서 다른 모든 노드로 가는 최단경로를 갱신. 음의 간..

멍토님, 우의님의 10분 테코톡 보고 작성했습니다 Blocking vs Non-Blocking, Sync vs Async 제어권(행동할수있는 권리, 행동할수 있는 시간)의 반환 결과값의 전달 (return) 1. Blocking vs Non-Blocking 제어할 수 없는 대상의 처리 방법. -Blocking : 자신의 작업을 진행하다가 다른 주체의 작업이 시작되면 *다른 작업이 끝날 때까지 *기다렸다가 자신의 작업을 시작하는 것 호출된 함수가 자신의 작업을 모두 마칠 때까지 호출한 함수에게 제어권을 넘겨주지 않고 대기하게 만든다 호출되는 함수가 바로 리턴하지 않으면 Blocking 호출한 함수가 제어권을 가지고있따가 function A에게 가서 제어권을 줌, 함수 시행 후 제어권에 결과값을 얹어서 호출..

JS는 싱글 쓰레드 자바스크립트의 메인 쓰레드인 이벤트 루프는 싱글 쓰레드이다. 하지만 이벤트 루프만 독립적으로 실행되지 않고 웹 브라우저나 NodeJS같은 멀티 쓰레드 환경에서 실행된다. 즉 JS는 싱글쓰레드지만 JS런타임은 싱글 쓰레드가 아니다. 싱글쓰레드로 병렬처리를 하는 방법. 기존 동기식 요청은 코드를 한줄 한줄 차례로 실행한다. 하지만 이렇게 되면 앞의 작업시간이 길수록 병목이 생기고 시간과 자원이 낭비된다. 요청이 완료될때까지 기다리지 않고 다른작업을 비동기 호출로 수행한다. JS의 비동기 런타임. Call Stack: 자바스크립트에서 수행해야 할 함수들을 순차적으로 스택에 담아 처리(메인 스택) Web API: 웹 브라우저에서 제공하는 API로 AJAX나 Timeout등의 비동기 작업을 실..

아이디어 1. 추 무게의 합을 전부 구해서 dp에 체크 2. 모든 무게에 다시한번 추를 빼주며(반대쪽 저울에 올려놓으며) dp체크 사실 같은 추를 두번사용하는 즉 왼쪽에도 오른쪽에도 올려놓는 경우를 체크하기는 하나 양쪽에 올려봤자 안올렸을 때의 dp와 같으므로 문제없다. (같은걸 두번 더하거나 두번뺄때가 아니면 결과 집합은 같다.) import sys input = sys.stdin.readline chu_N = int(input()) chu_list = list(map(int,input().split())) glass_ball_N = int(input()) ball_list = list(map(int,input().split())) dp_chu = {i:False for i in range(sum(ch..

숨바꼭질보다 조금 쉬운 하위문제 느낌? 어차피 이동의 모든 가중치는 같으므로 따로 우선순위큐나 appendleft없이 차례로 탐색하면 된다. 어차피 먼저 도착하면 먼저 출력된다. import sys input = sys.stdin.readline from collections import deque def BFS(F,S,G,U,D): dp_count = {i:float('inf') for i in range(1,F+1)} dp_count[S] = 0 queue = deque() queue.append(S) while queue: cur_stair = queue.popleft() if cur_stair == G: print(dp_count[G]) return for next_stair in (cur_sta..

루트노드를 줬으니 루트노드부터 BFS로 전위순회 하며 부모를 기록해줬다. import sys input = sys.stdin.readline from collections import deque # BFS로 루트부터 전위순회. def BFS(start): queue = deque() visited = [False]*(N+1) visited[start] = True queue.append(start) while queue: cur_node = queue.popleft() for next_node in graph[cur_node]: if not visited[next_node]: visited[next_node] = True super_node[next_node] = cur_node queue.append(..

에라토스테네스의 체 란? 소수를 판별하는 알고리즘이다. 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 단일 숫자 소수 여부 확인 어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다. 만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다. 소수 구하기 n=100 def isPrime(a): if(a 소수의 배수들을 배제하는 방법으로 남는 소수를 가져갈 수 있지 않을까? 에라토스테네스의 체 원리 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당..

​ 순서는 그냥 쓰는대로 썼음 1. lambda ​ 수업듣고 이해하게 됐음. 함수를 표현식형태로 다른곳에 인자로 쓰기위한 느낌. ​ lambda 매개변수 리턴값 뒤에 조건문 오던 말던. ​ sorted의 key값으로 쓰면 매우 유용함. sorted(list, lambda x: (x[1],x[0]),reverse=True) ​ => 2번째 열, 1번째 열 순으로 이중정렬을 할수도있음. ​ sorted(dict,lambda x: dict[x]/[2])로 key값 대신서 index값 같고 key다른 여러값 동시에 뽑아 리스트로 만들수도있음. 2. map,reduce,filter ​ 앞에 설명한 lambda를 쓰기 가장 좋은 함수를 인자로 받는 메소드들. ​ map,filter은 (함수,리스트)를 인자로 받고 ..

뜬금 정렬 정리. 최근 문제풀이에 열중하다보니 다시한번 기본서를 보고싶은 느낌이 들어 정리. 버블 정렬 O(n^2) def bubbleSort(lst): LEN = len(lst) for last_idx in range(LEN-2, 0, -1): # 각 턴의 마지막 인덱스 isSwap = False # 최적화 for l_idx in range(0, last_idx+1): if lst[l_idx] > lst[l_idx+1]: lst[l_idx], lst[l_idx+1] = lst[l_idx+1], lst[l_idx] isSwap = True if not isSwap: # swap이 일어나지 않았으면 정렬 완료상태 return lst return lst 나랑 내뒤에랑 비교해서 큰게 뒤로감. 여러번 순회해서 ..

set을 이용하는 문제로 set 삽입, 삭제 메소드인 add remove discard만 알면 무난한 코드로 풀린다. import sys input = sys.stdin.readline m = int(input()) S = set() for _ in range(m): commands = input().strip().split() # split()을 통해 띄어씌기가 있으면 튜플인 commands # 없으면 그냥 commands if len(commands) == 1: if commands[0] == "all": S = set([i for i in range(1, 21)]) else: S = set() # set은 add remove discard(discard는 없는거 없애려해도 오류아냄.) else: c..