겜돌이의 개발일지

개요 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이라면, 플로이드-와샬 알고리즘은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 이차원 배열을 사용해 최소값을 계속 저장해두기 때문에, 다이나믹 프로그래밍 기법의 일부로도 볼 수 있다. 설명 A에서 B로 가는 최소 비용과 A에서 C를 거쳐 B로 가는 최소 비용을 비교한다. 다음과 같은 비용을 가지는 양방향 그래프가 있다고 가정하다. 초기값을 먼저 표시하면 다음 표와 같다. 1을 지날 때 다음 영역을 갱신 해줘야 한다. 4 -> 1-> 5 (반대도 같음)의 비용이 14이므로 INF에서 갱신해준다. 2를 지날 때 3 -> 2 -> 4 (반대도 같음)의 비용이 7로, 기존의 비용 8보다 더 저렴하..

개요 분기 한정법은 백트래킹 기법과 같이 상태 공간 트리를 구축하여 문제를 해결하는 방법이다. 최적 해를 구하는 문제에 주로 사용된다. 원리 마디를 검색할 때마다, 마디가 유망한 지 여부를 결정하기 위해서 한계값(bound)을 계산한다. 한계값이 현재까지의 최적의 해보다 좋지 않으면 유망하지 않은 것이다. 이 마디는 더 이상 검색할 필요가 없다. 위 그림은 최소 등산 코스를 찾는 과정 중 하나이다. 이미 80이라는 최적의 해를 찾은 상태에서 최소 100, 200의 거리를 갖는 등산로 A, B를 조사할 필요는 없다. 즉, A와 B는 유망하지 않다. A와 B 중에서 A가 더 작은 값을 가질 수 있으므로, A 먼저 조사하는 것이 좋다. 위 그림은 반대로 최대 가치의 보물을 찾는 과정이다. 이미 180이라는 최..

개요 N-queens 문제는 N * N 체스판에 N개의 퀸을 서로 공격받지 않게 놓는 방법의 개수를 구하는 문제이다. 예시 n = 4일 때 정답의 개수를 구해보자. 먼저 각 열에는 한 개의 퀸을 놓을 수 있다. 무작정으로 놓을 수 있는 모든 경우에 수를 고려하면 다음과 같다. 총 4 * 4 * 4 * 4 = 256가지의 경우에 대해 놓을 수 있는지 각각 검사해야 한다. 하지만 (2, 1)에 퀸을 놓는 순간 조건을 만족하지 않으므로 이후 자식 노드들은 검사하지 않아도 된다. 따라서 백트래킹을 활용하면 검사해야 하는 가짓 수를 줄일 수 있다. 스도우 코드 상태공간트리 예제 코드(C++) n을 입력받아 n * n 체스판에서 n개의 퀸을 놓을 수 있는 총 방법의 개수를 출력하는 코드 1 2 3 4 5 6 7 8..

개요 0-1 배낭 문제는 n개의 물건에 대해 최대 가치가 되도록 담는 알고리즘이다. 시간복잡도 분석 각각의 물건은 넣는다 / 넣지 않는다의 2개의 경우가 있으므로 단순히 시간 복잡도를 계산하면 O(2^n)이다. Dynamic Programming으로 해결 i > 0이고 w > 0일 때, 전체 무게가 w를 넘지 않도록 i번째까지의 항목 중에서 얻어진 최고 이익을 P[i][W]라고 하면 P[i][W]는 다음과 같이 구할 수 있다. 이 알고리즘의 시간복잡도는 이다. W = 10이고, 품목이 다음과 같을 때의 0-1 배낭 문제 예시 문제점 불필요한 항을 계산한다. (위 그림에서 P[3][8]과 P[3][9]를 구할 필요는 없다.) 위 그림의 경우 총 n(4) * W(10)의 40번의 비교가 필요하다. 아래와 같..

개요 허프만 코드란 최적 이진 코드를 만드는 알고리즘 중 하나이다. Fixed-length binary code 코드의 길이가 고정적이다. ex) a : 00, b : 01, c : 11 등 문제점 : 자주 나타나는 코드의 길이도 고정이므로 낭비가 생긴다. Variable-length binary code 코드의 길이가 가변적이다. ex) a : 10, b: 0, c : 11 등 자주 나타나는 코드의 길이를 줄일 수 있다. 문제점 : 위의 예시에서 d를 00으로 표기하는 방법을 추가하면 00이 d인지, bb인지 구별할 수 없어진다. optimal binary code (최적 이진 코드) 주어진 파일에 있는 문자들을 이진코드로 표현하는데 필요한 비트의 개수가 최소가 되는 코드이다. Prefix code 한..

개요 다익스트라 알고리즘은 가중치가 있는 방향성 그래프에서, 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 문제이다. 알고리즘의 단계는 다음과 같다. 1. F는 공집합으로 둔다. 2. Y(최단 경로가 확정된 집합)에는 시작 정점 v1을 포함해 {v1}으로 둔다. 3. 최종해답을 얻을 때까지 다음 과정을 반복한다. (a) 선정 절차 / 적정성 점검 : V-Y에 속한 정점 중에서, v1에서 Y에 속한 정점만을 거쳐서 최단 경로가 되는 v를 선정한다. (b) v를 F에 추가한다. (c) v에서 F로 이어지는 최단경로 상의 이음선을 F에 추가한다. (d) 해답 점검 : Y = V가 되면 T = (V, F)가 최단경로를 나타내는 그래프가 된다. 예시 초기화 : v1에서 v2~v5까지의 최단 거리를..

1. 간선 정렬 2. 가중치 낮은 간선 부터 이어줌. 3. 두 노드가 이미 선택되었다면 이어주지않고 패스

빅($O$) 표기법 정의 : 점근적 상한 어떤 함수 $g(n)$이 $O(f(n))$에 속한다는 말은 $n$이 커짐에 따라 $cf(n)$보다는 작은 값을 가지게 된다는 의미 따라서 $g(n)$은 $cf(n)$에 비해 좋다(빠르다)라고 할 수 있다. 즉, 어떤 알고리즘의 시간복잡도가 $O(f(n))$이라는 것은 입력 $n$에 대해 알고리즘의 수행시간이 늦어도 $cf(n)$은 된다는 말이다. (점근적 상한) 알고리즘의 수행시간이 $cf(n)$보다 느릴 수 없다는 말과 같다. 오메가($\Omega$) 표기법 정의 : 점근적 하한 어떤 함수 $g(n)$이 $\Omega (f(n))$에 속한 다는 말은 $n$이 커짐에 따라 $cf(n)$보다는 큰 값을 가지게 된다는 의미 따라서 $g(n)$은 $cf(n)$에 비해 ..

맨날 헷갈려서 정리 출처 [C++] 순열(Permutation) 조합(Combination) 알고리즘 백준에서 완전 탐색 문제를 풀다가 항상 조합과 순열을 만들 때 헷갈려서 아예 시간을 내어 정리하였다. 이 네 가지 알고리즘의 뼈대를 이해하면, 여러 방면에 쓰여서 좋은 거 같다. 이후 나오는 hongchan.tistory.com