코딩 테스트/개념34 최소 신장 트리 최소 신장 트리 minimum spanning tree 모든 노드를 연결할 때 사용된 에지의 가중치의 합을 최소로 하는 트리사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음n개의 노드가 있으면 최소 신장 트리 구성 에지 개수는 n-1이다.1. 에지 리스트로 그래프 구현, 유니온 파인드 리스트 초기화2. 그래프 데이터를 가중치 기준 정렬3. 가중치가 낮은 에지부터 연결 시도사이클 형성 여부 find로 확인 후사이클이 아닌 경우에만 union 연산으로 두 노드 연결 4. 연결 에지 개수 n-1만큼 반복 5. 에지 개수 n-1인 경우 종료완성된 최소 신장 트리의 총 에지 비용 출력 2024. 8. 10. 트라이 트라이 Trie 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료 구조단어들을 사선 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용하여 검색 수행 - n진 트리: 문자 종류의 개수에 따라 n 결정 (알파벳 26개 : 26진 트리)- 루트 노드는 공백 상태 유지 2024. 8. 4. 플로이드-워셜 플로이드-워셜 floyd-warshall 그래프에서 최단 거리를 구하는 알고리즘모든 노드 간에 최단 경로 탐색음수 가중치 에지가 있어도 수행 가능동적 계획법의 원리를 이용해 알고리즘에 접근D[s][e] = min(D[s][e], D[s][k] + D[k][e])1. 리스트 선언하고 초기화하기s == e 인 경우, 0s != e 인 경우, 무한2. 최단거리 리스트에 그래프 데이터 저장3. 점화식으로 리스트 업데이트하기 (n: 노드 개수)for 경유지 k에 대해(1, n): for 출발노드 s에 대해(1, n): for 도착노드 e에 대해(1, n): D[s][e] = min(D[s][e], D[s][k] + D[k][e]) 2024. 8. 3. 유니온 파인드 유니온 파인드 Union Find 아래 두 개의 연산으로 구성된 알고리즘- 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산- 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산- Union 연산각 노드가 속한 집합을 1개로 합치는 연산ex) a∈A, b∈B일 때, union(a, b) = A∪B - Find 연산특정 노드 a에 관해 a가 속한 집합의 노드를 반환하는 연산ex) a∈A 일 때 find(a)는 A집합의 대표 노드 반환 1. 대상 노드 리스트에 index값과 value값이 동일한지 확인2. 동일하지 않으면 value값이 가리키는 index 위치로 이동3. 이동 위치의 index값과 value값이 같을 때까지 1~2 반복 (재귀함수로 구현)4. 대표.. 2024. 7. 28. 벨만-포드 벨만-포드 bellman-ford-moore 그래프에서 최단 거리를 구하는 알고리즘특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색음수 가중치 에지가 있어도 수행할 수 있음전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기출발노드0, 나머지는 무한으로 초기화2. 모든 에지를 확인해 정답 리스트 업데이트 하기노드개수 -1 만큼 반복: 에지 개수 만큼 반복: E = (s, e, w)에서 아래 조건을 만족하면 업데이트 D[s] != 무한, D[e] > D[s] + w 이면, D[e] = D[s] + w 3. 음수 사이클 유무 확인하기모든 에지를 다시 사용하여 업데이트되는 노드가 있는지 확인(음수 사이클.. 2024. 7. 27. 그래프 그래프: 노드와 에지로 구성된 집합 - 노드: 데이터를 표현하는 단위- 에지: 노드 연결ex) 그래프가 아래와 같다고 하자!! 그래프 생성 방법 1. 에지 리스트 (edge list)에지를 중심으로 그래프 표현출발노드도착노드(가중치)12713524183493514453 그래프 생성 방법 2. 인접 행렬 (adjacency matrix)노드를 중심으로 그래프 표현가중치가 없는 경우 모두 1로 표현 도착노드출발노드index123451 75 2 18 3 9144 35 그래프 생성 방법 3. 인접 리스트 (adjacency list)가중치가 없는 경우 ()없이 표현List 1>(2, 7), (3, 5)2>(4, 18)3>(4, 9), (5, 14)4>(5, 3)5> 2024. 7. 21. 이전 1 2 3 4 5 6 다음 728x90
