할머니의 콤퓨타 도전기

위상 정렬 순서가 정해져 있는 작업을 차례대로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 DAG (Directed Acyclic Graph: 사이클이 발생하지 않는 방향 그래프)에만 적용 가능 사이클이 발생하는 경우 위상 정렬을 수행할 수 없음 위상 정렬은 시작점이 존재해야함. 사이클 그래프에서는 시작점 찾을 수 없음. 불가능 위상 정령은 두 가지의 해결책 보여줌 현재 그래프는 위상 정렬이 가능? 가능하다면, 그 결과는? 구현 방법 진입 차수가 0인 정점을 큐에 삽입 큐에서 원소를 꺼내 연결된 모든 간선 제거 간선 제거 이후에 진입차수가 0이된 정점을 큐에 삽입 큐가 빌 때 까지 2~3번 과정 반복 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재하는 것 모든 원소를 방문했다면 큐에..

Knapsack 알고리즘 무게와 가치가 따로 있고 가져갈 수 있는 최대 가치를 묻는 문제에 사용 모든 경우를 다 따져보는 Greedy 알고리즘으로 해결할 수 있지만 시간복잡도가 2^n, 최적의 답일 보장 없음 다이나믹 프로그래밍으로 풀어야함 w[i] : i 번째 보석의 무게 v[i] : i 번째 보석의 가치 d[i][j] : i 번째 보석까지 탐색한 현 상태, j 만큼 무게를 가져갔을 때 획득한 최대 가치 i 번째 보석을 가져간 경우 : d[i][j] = d[i-1][j-w[i]] + v[i] i 번째 보석을 가져가지 않은 경우 : d[i][j] = d[i-1][j] i를 첫 번째 보석부터 n 번째 보석까지, j를 0kg부터 k (배낭이 담을 수 있는 최대 무게)까지 d[i][j] = max(d[i][j..

다익스트라(Dijkstra) 알고리즘 다이나믹 프로그래밍을 활용한 대표적인 최단 경로탐색 알고리즘 다익스트라 알고리즘은 특정 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌 (음의 간선은 포함 X) 다익스트라 알고리즘에서 최단 거리는 여러 개의 최단거리로 이루어져있기 때문에 작은 문제가 큰 문제의 부분 집합에 속해 있다고 할 수 있음 따라서 다이나믹 프로그래밍 문제 작동 과정 출발 노드 설정 출발 노드를 기준으로 각 노드의 최소 비용 저장 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 해당 노드를 거쳐서 특별한 노드로 가는 경우를 고려해 최소 비용 갱신 3~4번 반복 0 2 5 1 무한 무한 2 0 3 2 무한 무한 5 3 0 3 1 5 1 2 3 0 1 무한 무한 무한 5 1 0 2 ..

트리의 지름 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것 트리의 지름 구하는 방법 임의의 점(A)에서 가장 먼 지점 B를 찾음 B에서 가장 먼 지점(C)를 찾음 B~C의 거리가 트리의 지름 증명 (귀류법) 관련 문제 www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net

분할 정복 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산, 각 부분 문제의 답으로 부터 전체 문제의 답을 계산 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눔 일반 재귀 호출은 항상 문제를 한 조각과 나머지로 쪼개는 방식 분할 정복법은 항상 문제를 절반씩 나누는 분할 정복 알고리즘 구성 요소 문제를 더 작은 문제로 분할 (Divide) 각 문제에 대한 구한 답을 원래 문제에 대한 답으로 병합 (Merge) 더 이상 답을 분할하지 않고 바로 풀 수 있는 매우 작은 문제 (Base Case) 특성 문제를 둘 이상의 부분으로 나누는 자연스러운 방법이 있어야 함..

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아감 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 가는 것 (가지치기) 일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요하므로 처리가 불가능할 수 있음. 따라서 가지치기를 얼마나 잘하느냐에 따라 효율성 결정 즉 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에..