코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 두 탐색의 시간 복잡도는 O(V + E)로 같다. BFS 시작 정점에서 가까운 정점을 찾는 데 적합하다. 특정 정점을 탐색할 경우 최단 거리 경로를 보장한다. 탐색 시 생성된 검색 트리는 짧고 넓으며 많은 메모리를 필요로 한다. 상대적으로 코드 크기가 커 명령어 캐시 적중률이 낮다. DFS 시작 정점에서 먼 정점을 찾는 데 적합하다. 특정 정점 탐색 시 최단 경로를 보장하지 않는다. 탐색 시 생성된 검색 트리는 길고 좁으며 상대적으로 적은 메모리를 사용한다. 상대적으로 코드 크기가 작아 명령어 캐시 적중률이 높다.

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 깊이 우선 탐색(DFS) 그래프 내 모든 정점을 탐색하는 방법의 하나이다. 시작 정점에서 멀어지는 방향으로 탐색하며, 더 방문할 정점이 없으면 다른 경로를 찾아 멀어지는 방향으로 재귀적으로 탐색한다. O(V + E) 시간에 수행된다. 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 백트래킹(Backtracking) 기법의 하나이다. 시작 정점 v를 스택에 삽입한다. 스택이 비어있지 않은 동안 반복한다. 스택에서 정점 1개를 꺼낸다. 아직 방문하지 않았다면 방문하고, 이미 방문했다면 2로 돌아간다. 꺼낸 정점을 방문했다고 표시한다. 꺼낸 정점에 연결된 정점들 중 방문하지 않은 정점들을 스택에 삽입한다. 2로 돌아간다. #incl..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 너비 우선 탐색(BFS) 그래프 내 모든 정점을 탐색하는 방법의 하나이다. 시작 정점으로부터 가까운 정점에서 먼 정점 순으로 방문하게 된다. O(V + E) 시간에 수행된다. 시작 정점 v를 큐에 삽입한다. 큐가 비어있지 않은 동안 반복한다. 큐에서 정점 1개를 꺼낸다. 아직 방문하지 않았다면 방문하고, 이미 방문했다면 2로 돌아간다. 꺼낸 정점을 방문했다고 표시한다. 꺼낸 정점에 연결된 정점들 중 방문하지 않은 정점들을 큐에 삽입한다. 2로 돌아간다. #include #include #include #include #include #include using namespace std; template struct Edge { unsigned src..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 서로소 집합(a.k.a Union Find) 트리의 집합으로 구성된 숲(Forest)이다. 각 트리는 ID로 표현되며, 순위(Rank)와 부모에 대한 참조를 갖는다. 초기화 시 각 트리는 1 ~ N까지의 ID를 가지며, 순위는 0이고 부모에 대한 참조는 자기 자신이 된다. 서로소 집합의 연산들 make_set(x) 순위가 0이고 부모에 대한 참조가 자기 자신이며 x를 ID로 갖는 트리를 서로소 집합에 추가한다. find(x) 부모에 대한 참조를 따라 이동하여 트리의 루트를 반환한다. union(x, y) x, y 각각의 루트를 찾는다. 루트가 같으면 아무 것도 하지 않는다. 루트가 다르면 순위가 높은 루트를 낮은 루트의 부모로 설정한다. 서로소 집..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 최단 작업 우선 스케줄링 처리 시간이 짧은 작업을 우선적으로 배치해 전체 수행 시간을 줄이는 방법이다. 가능한 많은 작업의 대기 시간을 줄이기 위해서는 짧은 작업을 우선적으로 처리해야 한다. 최단 작업 우선 스케줄링의 예 프로세스 수행 시간에 따른 CPU 할당 순서 지정 ... #include #include #include #include using namespace std; template auto compute_waiting_times(vector& service_times) { size_t size = service_times.size(); vector W(size, 0); for (int i = 1; i < size; ++i) W[i] =..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 탐욕법 매번 탐욕스럽게 현재 상황에서의 최적해를 선택하는 방법이다. 탐욕법의 해가 항상 최적해가 되는 것은 아니다. 다음의 두 가지를 만족하면 탐욕법을 통해 최적해를 구할 수 있다. 최적 부분 구조(Optimal Substructure): 문제 P의 최적해가 P의 부분 문제들의 최적해로 구성될 경우 탐욕 선택(Greedy Choice): 문제 P의 지역적 최적해를 반복적으로 선택해 전체 최적해를 구할 수 있는 경우 탐욕법의 예 다익스트라(Dijkstra) 알고리즘 지도에서의 최단 경로 계산 등 최단 작업 우선(SJF, Shortest Job First) 스케줄링 총 대기 시간 단축 등