Redddy's Devlog

※ 그래프 사진은 직접 그려서 추가예정! 갤럭시 탭이 오면 그걸로 그려야지ㅎ.ㅎ DFS와 BFS는 모두 그래프 탐색 알고리즘이다. 코딩테스트를 준비하다보면 어느 순간 만날 수 밖에 없는 알고리즘이다. DFS DFS는 Depth-first Search의 약자로 깊이 우선 탐색을 의미한다. 그래프의 가장 깊은 곳 우선으로 탐색을 하는 알고리즘이다. 스택 자료구조를 사용하여 그래프를 탐색한다. DFS의 탐색과정은 다음과 같다. 탐색 시작 노드를 스택에 넣고, 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그중 가장 작은 값의 인접 노드를 스택에 넣고 방문처리한다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때가지 반복..

우선순위 큐는 내부적으로 힙(heap)이라는 완전이진트리 Complete binary Tree로 되어 있다. 힙 트리의 루트 노드(root node)에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데, 전자는 최대힙(max-heap), 후자는 최소힙(min-heap)이라 한다. 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 이 과정이 꽤 효율적이라 우선순위 큐의 값 삽입/삭제 시간 복잡도는 O(log N)이다. 무작위 숫자들을 힙에 전부 넣고 하나씩 빼면 정렬된 결과를 얻을 수 있는데, 이게 힙정렬이다. from queue import PriorityQueue pq = PriorityQueue() pq.put(123) pq.put(789) p..

Queue는 스택과 상반된 특징을 띄고 있는 자료구조이다. 둘 다 선형 자료구조이지만, 데이터 입출 순서가 달라지는 부분이 있다. 큐에는 데이터를 넣은 순서 그대로 빼게 된다. 첫 번째로 넣은 데이터가 첫 번째로 빠지며 이를 FIFO라 한다. 큐에 데이터를 넣고 뺄 때 시간 복잡도는 O(1)이므로 N개의 데이터를 넣고 빼야 한다면 총 O(N)이 될 것이다. from queue import Queue q = Queue() q.put(123) q.put(456) q.put(789) while not q.empty(): print(q.get()) 이렇게 import 해서 사용하면 된다. 위 코드에서 대문자 Q로 시작하는 Queue 모듈은 멀티스레딩 환경까지 고려해서 스레드 간에 안전한 방식으로 동작하는 모듈이..