욤미의 개발일지

백트래킹(backtracking)이란? 모든 경우의 수를 전부 고려하는 알고리즘으로 해를 찾는 도중 조건에 맞지 않으면 되돌아가서 다시 해를 찾아가는 기법 특징 상태 공간 트리를 탐색하는 일종의 트리 탐색 알고리즘이다. 코딩에서는 불필요한 경로를 조기에 차단하여 반복문의 횟수를 줄일 수 있으므로 효율적인 방법이다. 하지만 N! 경우의 수는 최악의 경우 여전히 지수함수 시간을 필요로 가방법이 효율성이 결정한다. 동작 과정 1. 방문 중인 노드가 유망한지 체크한다. 유망함(promising): 방문 중인 노드에서 하위 노드가 해답을 발견할 가능성이 있는 것 유망하지 않음(nonpromising): 하뒤 노드에서 해답을 발견할 가능성이 없는 것 2. 유망하지 않으면, 부모노드로 돌아간다.(백트래킹) 3. 이때..

사이클 판별 무방향 그래프: 서로소 집합으로 사이클 판별 가능 방향 그래프: 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)이다. 단순히 최단 거리를 구하는 문제가 많이 출력된다. 그리디 및 다이나믹 프로그래밍의 한 유형이다. 대표적인 최단 거리 알고리즘 다익스트라 최단 경로 알고리즘 플로이드 워셜 벨만 포드 알고리즘