CS/알고리즘

Backtracking은 DFS와 같은 방식으로 트리를 탐색하는 방법 중 하나다. 탐색을 진행하다가 더 갈 수 없으면 다시 이전 노드로 돌아와 탐색하는 방법이다. Sum of Subsets 문제도 backtracking으로 풀 수 있는 문제 중 하나다. Sum of Subsets은 집합 wi의 부분 집합 중 그 합이 W와 같은 부분 집합들을 찾는 문제다. 예를 들어서, 𝑛 = 5, 𝑊 = 21, and 𝑤𝑖 = [5, 6, 10, 11, 16]이 주어졌다고 하자. 그러면 21이 될 수 있는 조합은 {5, 6, 10}, {5, 16}, {10, 11}이다. 이렇게 푸는 것을 상태공간트리를 만들어서 풀어보자. 왼쪽은 wi를 포함시키는 것이고 오른쪽은 wi를 포함하지 않을 때의 값이다. weight가 ..

K번째로 작은 값 찾기Median of MediansQuick sort으로 Selection 문제를 접근하는 데에 있어 불균형을 해결하기 위해서, 비교적 균등하게 배열을 나누는 알고리즘이다. 문제를 푸는 방법은 다음과 같다. 1. 배열 L을 5개씩 묶어준다. 즉, n/5로 분할한다.2. 각 묶음에서 median 값을 찾는다. 이때, 묶음은 5개이므로 6번 비교하면 median 값을 찾을 수 있다. 비교 횟수는 총 (6 * n/5)번이다.3. Median들 중에서 median인 m*을 찾는다. 이때 T(n/5)가 걸린다.4. m*과 비교해서 loser 그룹과 winner 그룹으로 나눈다. 비교 횟수는 총 n번이다.5. 재귀호출하거나 m*를 반환한다. 이때 T(|loser|) 이거나 T(|winner|) 시..

K번째로 작은 값 찾기Quick sortn과 K가 주어질 때 K 번째로 작은 값을 찾아야 한다. Quick Sort 방식으로 pivot보다 작은 것은 왼쪽, 큰 것은 오른쪽에 두고 pivot이 K번째에 위치할 때까지 재귀적으로 반복하여 푸는 방법이다. 먼저 pivot을 선택한다음에 Loser 배열과 Winner 배열로 나눈다. Loser는 pivot보다 작고 Winner은 pivot보다 큰 값들의 배열이다. pivot과 같은 값이면 M 배열에 집어 넣는다. 이 배열들을 만들기 위해서는 n-1번의 비교가 필요하다. Loser 집합의 개수가 K보다 큰 경우우리가 찾으려는 K가 Loser에 존재한다는 뜻으로, K번째 값을 반환하면 된다.Loser 집합의 개수와 M 집합의 개수가 K보다 작은 경우우리가 찾으려는..

일반적으로 Selection Problem은 정렬되지 않은 배열에서 K번째로 큰 값 혹은 작은 값을 구하는 문제이다. K = 1이라면, 그 배열에서 가장 큰 값 혹은 가장 작은 값을 구하고 K = 2라면 2번째로 큰 값 혹은 2번째로 작은 값을 찾으면 된다.입력 : n개의 값과 K(1출력 : K번째로 크거나 작은 값목표 : 비교 횟수를 최적화하는 것 최댓값 찾기(K = n)K = n일 때, S 배열에서 가장 큰 값을 찾아야 한다. S 배열의 수가 n일 때, n-1번 비교해야 한다. n-1 번이면 항상 최댓값을 찾을 수 있기 때문에 상한(Upper Bound)이라고 한다. n-1 번이면 최솟값을 찾기 위한 하한(Lower Bound)이다.  최솟값과 최댓값을 동시에 찾기(K = 1, K = n)최댓값과 최..

이전 글에서는 Knapsack problem을 Backtracking으로 접근하여 최적 해를 구했다. 이 방법은 bound가 maxprofit보다 크지 않을 때 non-promising이라고 판단한다. 알고리즘의 효율성을 따지면, 조금 더 나은 방법이 있다.그 방법은 branch and bound로 접근하는 것이다. 이 방법의 특징을 잘 살리면 bound를 보고 판단하는 것 외에, promising한 노드들의 bound를 비교해서 그 중에서 가장 좋은 자식 노드들만 방문할 수 있다. DFS처럼 이미 정해진 순서대로 노드를 방문하는 것보다 더 빠르게 최적값을 찾을 수 있다. 이런 방법을 Best-First Search with branch and bound라고 한다. 이러한 방법은 BFS 방식을 약간 수정..

Knapsack Problem은 아주 유명한 문제이다. 어떤 배낭이 있고 그 배낭에 넣을 수 있는 최대 무게가 W라고 하자. 배낭에 넣을 수 있는  n개의 물건이 각각 무게 wi와 이익 pi를 가지고 있을 때, 배낭이 최대한 비싼 물건들을 담을 수 있는 조합을 찾는 문제이다. knapsack 문제는 원하는 만큼 물건을 쪼개어 담는 문제인 Fractional Knapsack와 물건을 쪼갤 수 없어 무게와 가치가 무조건 정수형태를 가지는 0-1 Knapsack 두 유형으로 나뉜다. 이번에는 0-1 Knapsack 문제를 해결하는 방법에 대해서 생각해보자.먼저 마디가 promising한지 판단해야 한다. Greedy Algorithm으로 접근하면, 해당 아이템의 무게가 배낭에 넣을 수 있는 최대 무게 W보다 ..

Optimal Binary Search Trees 이진 탐색 트리에서 평균 탐색 비용을 최적화하는 알고리즘이다. 이진 탐색 트리에 대한 내용은 [자료구조] Tree(트리) - 이진 트리를 참고하면 된다. 간단하게 이진 탐색 트리의 성질은 다음과 같다. 각 노드는 하나의 유일한 key를 가진다. 모든 노드의 key는 그 노드의 왼쪽 서브 트리의 key보다 항상 크다. 모든 노드의 key는 그 노드의 오른쪽 서브 트리의 key보다 항상 작다. 문제 접근 n개의 key들이 배열 K에 정렬되어 있고, 각 key의 탐색 확률인 pi가 주어진다. 각 key의 비교 횟수는 ci이다. 이러한 조건에서 각 key의 평균 탐색 비용는 pi * ci이다. 먼저, Brute Force로 접근해보자. 모든 경우에 대해 최적의 ..

Chained Matrix Multiplication 연쇄 행렬 곱셈은 곱셈을 할 때 곱셈 연산을 최소로 하는 곱셈 순서를 찾는 알고리즘이다. 행렬에서 곱셈은 결합 법칙이 성립하기 때문에 곱셉 순서는 상관 없지만, 연산의 양이 달라진다. 예를 들어, 2 * 3 행렬 A와 3 * 5 행렬 B, 5 * 7 행렬 C가 있다고 하자. 이 행렬들의 곱 ABC를 구하는 경우는 2가지가 있다. (A * B) * C 연산 횟수 : 2 * 3 * 5 + 2 * 5 * 7 = 100 A * (B * C) 연산 횟수 : 3 * 5 * 7 + 2 * 3 * 7 = 147 결과는 같지만 연산의 횟수가 달라진다는 것을 알 수 있다. 먼저 Brute Force로 접근해보자. 모든 경우의 수를 계산해야 하기 때문에 exponenti..

플로이드 알고리즘 플로이드 알고리즘은 최단 경로를 구하는 유명한 알고리즘이다. 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘인 반면, 플로이드 알고리즘은 모든 노드 간의 최단 경로를 구하는 방법이다. 2차원 인접 행렬을 구성해서 경로마다 더 짧은 길이를 선택해 줄이는 과정을 반복한다. 플로이드와 다익스트라에 대한 자세한 내용은 [자료구조] Graph(그래프) - 최단 경로 알고리즘을 참고하면 된다. 플로이드 알고리즘은 모든 경로를 확인해야 하기 때문에 Brute Force 방법으로 접근할 수 있다. 그러나, 시간복잡도가 O(n!)이므로 효율적인 다른 방법을 사용해야 한다. Dynamic Programming을 사용하면, n!인 시간복잡도를 조금 더 줄일 수 있다...

이항계수 이항계수는 주어진 집합에서 원하는 개수만큼 순서에 상관없이 뽑는 조합의 개수를 의미한다. 이항계수는 위와 같은 수식으로 표현해 풀 수 있다. 알고리즘적으로 조금 더 쉽게 풀어보면 아래 수식과 같다. 이항계수를 계산하는 방법은 2가지가 있다. Divide-and-Conquer과 Dynamic Programming으로 푸는 방법이다. Divide-and-Conquer k 가 0이거나 n이 k일 때는 1을 리턴하고, 그게 아니라면 재귀를 반복한다. 아래와 같이 코드를 짤 수 있다. typedef unsigned long long LongInteger; LongInteger bin(int n, int k) { if (k == 0 || n == k) return 1; else return bin(n - ..