욤미의 개발일지

사이클 판별 무방향 그래프: 서로소 집합으로 사이클 판별 가능 방향 그래프: DFS를 이용하여 사이클 판별 가능 판별 알고리즘 union 연산은 간선을 의미, 간선을 확인하며 두 노드의 루트를 확인 루트 노드가 다르면 → 두 노드에 대해 union → 같은 집합으로 만든다. 루트 노드가 같다면 → 사이클이 발생 그래프의 모든 간선(E)에 대해서 1번 과정을 반복 동작 예시 1. 부모 테이블의 모든 노드에 대해 자기 자신을 부모로 설정 노드 번호 1 2 3 부모 노드 번호 1 2 3 간선을 하나씩 확인해서 간선을 구성하는 노드에 대해 합집합 연산을 수행 2. 간선 (1, 2) 확인 → 노드1의 부모는 1 노드2의 부모는 2이므로 더 큰 번호를 가지는 노드2의 부모를 1로 갱신 노드 번호 1 2 3 부모 노..

서로소 집합 공통 원소가 없는 두 집합을 의미 예를 들어, {1, 2}와 {3, 4}는 서로소 관계인 반면 {1, 2}와 {2, 3}은 2가 공통원소이므로 서로소 관계가 아니다. 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 몇몇 그래프 알고리즘에서 사용된다. union, find 2개의 연산으로 동작한다. union(합집합) 연산: 원소가 포함된 집합 2개를 하나의 집합으로 합치는 연산 find(찾기) 연산: 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산' 서로소 집합 계산 알고리즘 트리 자료구조를 이용하여 집합을 표현 노드 개수(V) 크기의 부모 테이블을 초기화 서로소 집합 정보가 주어짐 union 연산으로, 서로 연결된 두 노드 A,B를 확인 A..

플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘 특징 3중 반복문 이용 2차원 리스트에 최단 거리 정보를 저장 = 인접 행렬 노드 개수가 적은 경우에 사용 N개 노드에 대해 점화식에 맞게 2차원 리스트를 갱신 → 다이나믹 프로그래밍 시간 복잡도 N개 노드가 있으면 N번의 단계를 수행한다. 각 단계마다 해당 노드를 거쳐 가는 경우를 고려한다. A → 노드 → B 의 비용을 확인하고 최단 거리를 갱신한다. 즉, 현재 노드를 제외하고 N-1개의 노드 중 서로 다른 노드 (A, B)쌍을 선택한다.$O(P_{N-1}^2) = O(N^2)$ K번 노드를 볼 때, 구체적인 점화식은 $D_{ab} = min(D_{ab}, D_{ak}+D_{kb})$ 이다. A에서 B로 가는 최..

다익스트라 최단 경로 알고리즘 특정 하나의 노드에서 출발하여 다른 모든 노드로 가는 각각의 최단 경로를 구하는 알고리즘 특징 음의 간선이 없을 때 정상적으로 동작 노드와 간선의 수가 많을 때 사용하기 적합 각 노드별로 연결 정보를 저장 = 인접 리스트 실제 GPS 소프트웨어의 기본 알고리즘으로 사용 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복 → 그리디 알고리즘으로 분류 각 단계를 거치면서 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.(한 단계마다 하나의 노드에 대한 최단 거리를 확실히 찾는 것) 다익스트라 알고리즘을 수행한 뒤에는 테이블에 각 노드까지의 최단 거리 정보가 저장된다. *완벽한 형태의 최단경로를 구하려면 추가적인 기능을 더 넣어야 한다. 동작 과정 출발 노드 ..

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 상황에 맞는 효율적인 알고리즘이 정립되어 있다. 사례에 맞는 알고리즘을 알고 있어야 문제를 풀기 쉽다. 보통 그래프를 이용해 표현되며 각 지점은 노드(node)이고 지점에 연결된 부분은 간선(edge)이다. 단순히 최단 거리를 구하는 문제가 많이 출력된다. 그리디 및 다이나믹 프로그래밍의 한 유형이다. 대표적인 최단 거리 알고리즘 다익스트라 최단 경로 알고리즘 플로이드 워셜 벨만 포드 알고리즘

컴퓨터는 연산 속도에 한계가 있고 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 이러한 문제를 해결하기 위해서는 연산 속도와 메모리 공간을최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. ＊ 해결하기 어려운 문제에 대해서 깊게 다루는 분야로는 P-NP 문제를 다루는 계산 복잡도 이론이 있다. 다이나믹 프로그래밍(동적 계획법) 메모리를 약간 더 사용하여 수행 시간 효율성을 비약적으로 향상시키는 대표적인 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일방적으로 두가지 방식(탑다운-하향식과 보텀업-상향식)으로 구성된다. 일반적인 프로그래밍 분야에서의 동적 할당(Dynamic All..