JUINTINATION

위상정렬(Topological Sort)이란? 유향 비순환 그래프(DAG, Directed Acyclic Graph)에서 정점을 간선의 방향을 거스르지 않도록 나열하는 알고리즘이다. 다음 라면 끓이기 예제를 보자 우리는 라면을 끓일 때 냄비에 물을 먼저 부어도 되고 라면 봉지를 먼저 뜯어도 되지만 계란은 맨 마지막에 풀어야 한다. 이러한 방향은 있지만 사이클은 없는 그래프를 간선의 방향을 거스르지 않고 한 줄로 정렬시키는 것이 위상정렬이라고 보면 될 것 같다. 위상정렬 알고리즘(1) 진입 간선이 없는 정점을 연결리스트 R의 맨 뒤에 연결하고 해당 정점과 그 정점의 진출 간선을 제거하는 과정을 반복한다. 의사 코드는 다음과 같으며 위의 예시를 구하는 과정은 그 다음 그림과 같다. topological_so..

최소 신장 트리(MST)란? 가중치 그래프에서 사이클 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 즉, 어떤 가중치 그래프의 신장 트리 중 선분들의 가중치 합이 최소인 트리 신장 트리는 그래프에서 사이클 없이 모든 점들을 연결시킨 트리로 주어진 그래프의 신장 트리를 찾으려면 사이클이 없도록 모든 점을 연결시키면 된다. 신장 트리는 그래프에서 사이클 없이 모든 점들을 연결시킨 트리로 그래프의 점이 n개 있다면 신장 트리에는 n-1개의 선분이 있다. 다음 예시에서 왼쪽 그림의 그래프의 최소 신장 트리는 오른쪽 그림의 그래프와 같다. MST를 찾기 위한 알고리즘 최소 신장 트리를 찾는 대표적인 그리디 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리..

서로소 집합(Disjoint Set)이란? 공통 원소가 없는 두 집합, 즉 A∩B=∅을 만족시키는 두 집합 A, B를 서로소 집합이라고 한다. 유니온 파인드(Union-Find)란? 서로소 집합에 대한 연산을 할 때 사용하는 알고리즘이다. 쉬운 이해를 위해 다음의 예시를 보자. https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 위의 문제처럼 초기에 n+1개의 집합 {0}, {1}, {2}, ... , {n}이..

알고리즘 설계 과제 내용 설계과제#1 : QuickSort를 3가지(Iterative, Recursive(devide&conquer), Randomized(pivot 요소 랜덤으로 선택)) 버전으로 구현하여 각 알고리즘에 따른 비교 연산 횟수를 비교하는 프로그램 작성 입력 데이터는 아래와 같이 랜덤으로 생성 for i(데이터의 사이즈) = 10**2, 10**4, 10**8, 10**16, ... // 본인 컴퓨터가 적당한 시간 내에 감당할 수 있는 한... for j=1,2,...,30(30개세트를만듬) // i 사이즈 만큼의 데이터를 j 생성하는 for loop data_set(i,j) = {x | x = random[1..i] * i} 설계과제#2 : LCS(Longest Common Substri..

그래프(Graph)란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조 그래프 G는 (V, E)로 표시 정점(vertices) 여러 가지 특성을 가질 수 있는 객체 노드(node)라고도 불림 간선(edge) 정점들 간의 관계 링크(link)라고도 불림 DFS란? 깊이 우선 탐색(depth-first search)한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행 스택(Stack)을 사용하거나 재귀함수 사용 # 재귀함수를 사용한 DFS depth_first_search(v): v를 방문되었다고 표시; for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면) then depth_first_..

동적 계획법(dp)이란? 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 메모이제이션을 통해 중복 계산을 방지하여 프로그램 실행 시간을 줄이는 방법 동적 계획법의 조건 어떤 문제(problem)가 여러 개의 하위 문제(sub problem)로 나누어지는 경우 하위 문제들의 답으로 어떤 문제를 해결할 수 있는 경우 서로 다른 문제에서 하위 문제들이 겹치는 경우 동적 계획법의 예시 dp를 사용하는 많은 문제 중에 피보나치 수를 구하는 문제가 있다. 피보나치 수는 다음과 같이 정의된다. fib(n) { if (n = 0) then return 0; else if (n = 1) then return 1; else return (fib(n - 1) + fib(n - 2)); } 이 문제는 재귀적 알고리즘..