깊이 우선 탐색 (Depth-First Search) 1. BFS 와 DFS 란? * 대표적인 그래프 **탐색** 알고리즘 - 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 - 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 - BFS 방식: A - B - C - D - G - H - I - E - F - J - 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함 - DFS 방식: A - B - D - E - F - C - G - H - I - J - 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아..

참고: 공간 복잡도 - 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음 - 시간 복잡도: 얼마나 빠르게 실행되는지 - 공간 복잡도: 얼마나 많은 저장 공간이 필요한지 > 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘 - 통상 둘 다를 만족시키기는 어려움 - 시간과 공간은 반비례적 경향이 있음 - 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선 - 그래서! 알고리즘은 시간 복잡도가 중심 공간 복잡도 대략적인 계산은 필요함 - 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많음 - 그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간 복잡도 제약 사항이 있는 경우가 있음 - 또한, 기존 알고리즘 문제에 영향을 받아서..

백 트래킹 기법의 이해 1. 백 트래킹 (backtracking) - 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름 - 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 - 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법 - 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현 - 각 후보군을 DFS 방식으로 확인 - 상태 공간 트리를 탐색하면서,..

프림 알고리즘 파이썬 코드 0. 모든 간선 정보를 저장 (adjacent_edges) 1. 임의의 정점을 선택, '연결된 노드 집합(connected_nodes)'에 삽입 2. 선택된 정점에 연결된 간선들을 간선 리스트(candidate_edge_list)에 삽입 3. 간선 리스트(candidate_edge_list)에서 최소 가중치를 가지는 간선부터 추출해서, - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵함(cycle 발생을 막기 위함) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리(mst)'에 삽입 - 해당 간선에 연결된 인접 정점의 간선들 중, '연결된 노드 집합(conn..

최소 신장 트리의 이해 1. 프림 알고리즘 (Prim's algorithm) - 대표적인 최소 신장 트리 알고리즘 - Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘) - 프림 알고리즘 - 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 - Kruskal's algorithm 과 Prim's algorithm 비교 - 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) - Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 M..

- union-by-rank 와 path compression 기법 사용시 시간 복잡도는 다음 계산식을 만족함이 증명되었음 - O(M log^*{N}) - log^*{N} 은 다음 값을 가짐이 증명되었음 - N이 2^{65536} 값을 가지더라도, log^*{N} 의 값이 5의 값을 가지므로, 거의 O(1), 즉 상수값에 가깝다고 볼 수 있음 6. 크루스칼 알고리즘 (Kruskal's algorithm) 코드 작성 mygraph = { 'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'edges': [ (7, 'A', 'B'), (5, 'A', 'D'), (7, 'B', 'A'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'), (8..