Dijkstra Implementation Dijkstra 구현 설명 가중치가 있는 그래프에서, 특정한 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 문제 음의 가중치가 있는 경우 사용 불가하지만, 유향 그래프에서는 사용 가능 아래 코드는 무향 연결 그래프이며, 그래프가 2d array 형태로 주어진 경우 0번 부터 N - 1번 까지의 노드가 존재 smallestNode 함수와 dijkstra 함수로 구성 smallestNode 함수 방문하지 않은 노드 중 시작 점에서 가장 가까운 노드를 방문하는 함수 모든 노드가 방문된 경우 -1을 반환 dijkstra 함수: 다음과 같은 알고리즘을 따름 각 노드 i에 대해 출발 노드로부터의 최소 거리를 distance[i]에 저장 출발 노드는 이 거리가 0임 나머지 노드들은 무한대로 초기화 ``smallestIdx함수를 통해curNode`노드를 선택하고, 방문했다고 표시 최초에는 출발 노드가 선택됨 curNode 기준으로 인접하지만 방문되지 않은 노드 i 들에 대해 다음을 수행 distance[curNode] + weights[curNode][i]를 계산 이 값이 distance[i]보다 작다면, 현재 i로 가는 경로보다 curNode를 거쳐 i로 가는 길이 더 짧다는 뜻 이 경우, distance[i] = distance[curNode] + weights[curNode][i]로 업데이트 하면 됨 모든 노드를 방문할 때 까지 2 - 3번 반복 구현 // Input public static int N = read(); public static int[][] weights = readGraph(); public static int smallestNode(int[] arr, boolean[] visited) { int node = -1; int smallest = Integer.

Exponent Implementation Exponent 구현 설명 $a^b$ 를 컴퓨터를 통해 계산하기 위해서는, a를 b번 곱하는 방법이 가장 직관적. 시간 복잡도는 $O(b)$ 그러나 이 방법은 $b$ 가 아주 큰 경우 비효율적 다음과 같은 방법을 통해 시간 복잡도를 $O(lg{b})$ 로 줄일 수 있음 $b$ 를 이진수로 생각해서, $b = b_k * 2^k + b_{k-1} * 2^{k-1} +…+ b_0 * 2^0$로 표현 가능 이러면 $a^b$ 는 다음과 같은 연속곱으로 표현됨 $$a^b = \prod_{b_i=1} (a^{2^i}) ^ {b_i}$$

Permutation Combination (Java) Permutation (Java) public static void perm(int N, int depth, boolean[] isVisited, int[] result) { if (depth == N) { printArr(result); return; } for (int i = 0; i < N; i++) { if (!isVisited[i]) { isVisited[i] = true; result[depth] = i + 1; perm(N, depth + 1, isVisited, result); result[depth] = 0; isVisited[i] = false; } } } 순열을 구현하기 위해서는, 1 부터 N 까지의 모든 수를 선택하되, 순서를 고려해야 함 Backtracking을 통해 depth가 깊어질 때 마다, 선택되지 않은 하나의 수를 선택하면 모든 경우의 수를 탐색 가능 perm(N, 0, new boolean[N], new int[N])으로 실행하면 됨 Combination (Java) public static void comb(int N, int M, int depth, int lastVisited, int[] result) { if (depth == M) { printArr(result); return; } for (int i = lastVisited + 1; i < N; i++) { result[depth] = i + 1; comb(N, M, depth + 1, i, result); result[depth] = 0; } } 조합을 구현하기 위해서는, 1 부터 N 까지의 수 중에서 M개를 선택하되, 순서를 고려하지 않아도 됨 이전에 x번을 선택했다면, 다음에는 x + 1번째 수 부터 선택하면 됨.

Tim Sort Various Sort Disadvantage Heap Sort best와 worst case의 시간 복잡도가 다 O(nlogn) 그러나 배열의 i번째 원소와 2 * i 번째 원소를 비교하므로, 공간 지역성의 원리를 만족하지 못함 즉, 캐시 메모리를 잘 활용하지 못함 Merge Sort 역시 best와 worst case의 시간 복잡도가 다 O(nlogn) 두 배열의 각각의 인덱스를 증가시키기 때문에 공간 지역성의 원리를 만족 그러나 정렬에 추가적인 메모리 필요 Quick Sort 메모리를 추가적으로 사용하지도 않고, 공간 지역성의 원리도 만족 그러나 worst case가 O(n^2)임 Tim Sort 기존 Sort 방법의 문제를 해결하기 위해 등장한 정렬 방법 Insertion sort와 merge sort를 병합 최적의 경우 O(n), 평균과 최악의 경우 O(nlogn) 대부분의 프로그래밍 언어에서 표준으로 채용 Tim Sort 원리 작은 n에 대해, insertion sort는 quick sort보다 빠름 위 원리를 활용해, 전체 배열을 작은 덩어리로 쪼개어서 insertion sort를 수행하고 병합하면 효율적이라는 점에서 착안 데이터를 $2^x$ 개씩 쪼개어서 insertion sort를 수행 이후 merge sort를 수행해서 데이터 병합 각 덩어리를 run, $2^x$ 를 minrun이라 부름 동작 순서 run의 첫 두 원소를 비교 두 번째 원소가 첫 번째 보다 큰 경우, 값을 순차적으로 증가시키는 방향으로 insertion sort (작은 경우는 반대로) minrun 번째 원소까지 insertion sort를 수행 minrun 다음 원소가 minrun 번째 원소보다 큰 경우, 해당 원소들을 덩어리에 포함 minrun 보다 작은 원소가 나오면 다음 run을 생성해 1번으로 돌아감 감소하는 run인 경우 뒤집어서 증가하는 run으로 만들고, 이후 merge sort Insertion Sort 최적화 minrun은 min(데이터의 갯수, 2^5 ~ 2^6) 으로 설정 Insertion sort 으로 삽입해야 할 위치를 찾을 때 binary insertion sort를 통해 빠르게 위치를 찾음 이렇게 해도 insertion sort 자체의 시간 복잡도는 O(n^2)이나, 시프트 연산이 더욱 빨라짐 Merge Sort 최적화 각 run들이 모두 크기가 다르므로, 일반적인 병합 정렬과 다른 방식 사용 각 run이 만들어질 때마다 stack에 담음 이 때 stack의 각 run 들이 다음 조건을 만족하도록, 작은 run들을 병합 stack[i] > stack[i - 1] stack[i] > stack[i - 1] + stack[i - 2] 각 run의 길이가 피보나치 수보다 크므로, stack의 크기가 적당한 수준에서 제한됨 또한 2-run merge 라는 방법을 통해 작은 크기의 run 만 복사하고도 병합 정렬 수행 가능 이 과정을 통해 공간을 최소 절반 이상 아낄 수 있음 Galloping이라는 방법을 사용해 merge sort에서 사용되는 index를 최적화해서 움직이기도 함 References https://d2.

Recursion Recursion (재귀 함수) 정의 단계에서 자신을 재참조하는 함수 매 호출마다 입력값(혹은 상태)이 변해야 하며, 그렇지 않은 경우 stack overflow 발생 입력값에 따라 base case와 recursive case로 동작하는 방식이 달라짐 Base case에서는 함수를 탈출 Recursive case에서는 자신을 입력값을 바꿔서 다시 호출 반복문을 사용해서 풀 수 있는 문제는 재귀로도 풀리고, 그 역도 성립 반복문보다 훨씬 직관적이고 쉬운 코드를 구현 가능하다는 장점이 존재 재귀를 사용하면 호출 스택이 쌓여서 메모리 오버헤드 발생 가능 Tail recursion이라는 방법을 통해 호출 스택을 쌓지 않을 수 있음 References https://namu.

0-1 Knapsack 1D 0-1 Knapsack 문제에 대한 고찰 0-1 Knapsack 문제의 점화식은 다음과 같음 m[i, w] = max(m[i - 1, w], m[i - 1, w - w_i] + v_i) i번째 행을 구하기 위해 i - 1번째 행을 사용 이를 구현하기 위해 2차원 배열을 사용하면 간단함 그러나 실제로 사용하는 것은 마지막 행 / 열의 원소이므로, 이전 행들의 정보는 사용 후 덮어씌워도 됨 이를 활용해 1차원 배열로 구현이 가능 공간복잡도가 O(W)가 될 뿐만 아니라, 시간 복잡도는 동일해도 실제 계산 시간은 감소됨 0-1 Knapsack 1차원 배열 구현 코드 dp[0] = 0 for cur_v, cur_w in zip(values, weights): for w in range(max_w, cur_w, -1): dp[w] = max(dp[w], dp[w - cur_w] + cur_v) 코드 설명 dp[w] 는 물건들의 무게의 합이 w 이하일 때 가치의 최댓값.

0-1 Knapsack Problem 0-1 Knapsack problem 각 무게가 w_i, 가치가 v_i 인 n개의 물건이 있음 이 중 몇 개의 물건을 선택해 총 무게의 합은 W 이하가 되게 하며, 가치들의 합의 최대값을 찾는 문제 Basic Idea DP로 해결 가능. 각 물건들에 번호를 1, 2, …, n번까지 부여 다음과 같은 배열을 생각 가능 m[i, w]: 총 무게의 합이 w이하 이고, i번째 물건 까지만 사용했을 때 가치들의 합의 최대 값 m[i, 0] 및 m[0, w]는 0임 i <= n, w <= W 이므로 m의 크기는 nW임.