목록C++ (67)
나만의 작은 도서관
[알고리즘] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)이란?플로이드-워셜 알고리즘은 가중치가 있는 그래프(weighted graph)에서 모든 정점 쌍 사이의 최단 경로 길이를 구하는 알고리즘이다. 플로이드-워셜 알고리즘은 이전 단계에서의 최단 경로 길이를 저장해두었다가 현재 단계에서의 최단 경로 길이를 구할 때 재사용하기 때문에 다이나믹 프로그래밍(dynamic programming) 알고리즘으로 분류된다. 점화식플로이드-워셜 알고리즘은 다이나믹 프로그래밍 알고리즘으로 분류되기때문에 점화식이 존재한다. 정점 i를 vi, k번 이하의 정점들만 거쳐서 vi에서 vj로 가는 최단 경로 길이를 dist(k, i, j)라 했을 때(1 , 점화식은 다음과 같다. dist(k, i, j) = min(..
[알고리즘 부록] 트리를 순회하는 방법 3가지(프리오더, 인오더, 포스트오더)
트리의 순회 방법트리를 순회하는 방법은 크게 3가지가 있다. 각각의 방법은 다음과 같다.프리오더(preorder traversal) 또는 전위 순회: root -> 왼쪽 -> 오른쪽 순으로 순회하는 방식인오더(inorder traversal) 또는 중위 순회: 왼쪽 -> root -> 오른쪽 순으로 순회하는 방식포스트오더(postorder traversal) 또는 후위 순회 : 왼쪽 -> 오른쪽 -> root 순으로 순회하는 방식그림으로 보면 다음과 같다.동작방식 전위 순회는 처음 마주친 노드를 방문한다는 점이 특징이며, 중위 순회는 왼쪽부터 오른쪽으로 차례대로 방문한다는 점이, 후위 순회는 루트 노드를 가장 늦게 방문한다는 점이 특징이다.구현 코드struct node{ char left; c..
[알고리즘] 너비 우선 탐색(BFS)와 dx, dy 테크닉
너비 우선 탐색(BFS)이란?너비 우선 탐색(BFS, Breadth First Search)은 그래프 탐색을 진행할 때 깊이와 너비 중 너비를 우선적으로 탐색하는 방식을 의미하며, 깊이 우선 탐색(DFS, Depth First Search)와 동일하게 완전 탐색 알고리즘으로 분류된다. BFS를 이용한 그래프 탐색의 시간복잡도: O(V+E) or O(V^2)너비 우선 탐색은 깊이 우선 탐색과 동일하게 그래프에 존재하는 모든 정점들을 탐색하는 것이 주 목적이다. 따라서 너비 우선 탐색 또한 그래프가 어떻게 표현되었는가에 따라 시간복잡도가 다음과 같아진다. 그래프의 정점(Vertex)수를 V, 간선(Edge)수를 E라고 했을 때,그래프가 인접 리스트로 표현된 경우 O(V + E)그래프가 인접 행렬로 표현된 ..
[알고리즘] 백트래킹(backtracking)과 깊이 우선 탐색(DFS)
백트래킹이란? 백트래킹은 한국말로 "되추적"이라는 뜻으로, 이름에서 알 수 있듯 해답이 아닌 경우 이전 단계로 되돌아가 다른 경우를 선택하여 해답을 추적하는 방법이다. 백트래킹은 가능한 모든 경우를 탐색하기 때문에 완전 탐색(exhausted search) 알고리즘으로 분류되며, 일반적으로 상태공간트리(state space tree)나 그래프(graph)를 탐색할 때 사용한다. 상태공간트리란?상태공간트리는 탐색 알고리즘에서 문제의 해결 과정을 트리 구조로 표현한 것이다. 노드는 특정 과정에서의 상태를, 마디(경로)는 문제를 해결하기 위해 선택된 일련의 결정들을 의미한다. 틱택토에 대한 상태공간트리를 그림으로 표현하면 다음과 같다. 상태공간트리의 탐색 시간복잡도: O(M^N)백트래킹은 모든 경우의 수들을 ..
[알고리즘] 최대공약수(GCD)와 유클리드 호제법(Euclidean algorithm)
최대공약수(GCD), 최소공배수(LCM) 구하는 법최대공약수(GCD, Greatest Common Divisor)는 두 자연수의 공통된 약수 중에서 가장 큰 수를 의미하며, 최소공배수(LCM, Least Common Muliple)는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다. 최대공약수는 두 자연수를 나누어 떨어지게 하는 최댓값을 찾으면 되며, 최소공배수는 두 자연수를 곱하고 GCD만큼 나눠주면 된다. 이를 코드로 구현하면 다음과 같다.// 시간복잡도 O(N)int gcd(int a, int b){ int res = 0; for(int i = 1; i N개의 자연수의 최대공약수를 구하고 싶은 경우2개의 자연수에 대한 최대공약수가 아닌 N개의 자연수에 대한 최대공약수를 구하고 ..
[알고리즘] 소수 판별법과 에라토스테네스의 체
소수 판별법소수는 양의 약수를 2개만 가지는 자연수, 즉 1과 자기자신으로만 나누어 떨어지는 자연수를 의미한다(1 제외). 임의의 수 N이 소수인지 판별하기 위해선 2~N-1까지의 수들로 N이 나누어 떨어지지 않는 지 확인하면 된다. 코드로 구현하면 다음과 같다.// 시간복잡도 O(N)bool isPrime(int num){ for(int i = 2; i 최적화를 할 수는 없을까?위 코드는 최적화가 가능하다. 2 이상의 자연수 N에 대해서 N의 약수는 짝이 반드시 존재하고, 짝이 되는 약수 중 작은 쪽에 속하는 약수는 √ N을 초과할 수 없기 때문에 num까지가 아닌 √ N이하의 자연수까지만 루프를 돌면 된다. 따라서 코드에 적용하면 다음과 같다.// 시간복잡도 O(√N)bool isPrime(i..