너비 우선 탐색 (Breadth-First Search) 너비 우선 탐색이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다. 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색 너비 우선 탐색(BFS)이 깊이..

깊이 우선 탐색 (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..