Rosie

0-1 knapsac 문제는 제한된 가방 용량(W) 안에서 물건들의 가치(bi)와 무게(wi)가 주어졌을 때, 물건들을 조합해 최대의 가치를 가지도록 하는 문제입니다. 단, 각 물건은 딱 한 번만 사용할 수 있습니다. 배낭문제,수도코드(pseudo code)를 살펴보겠습니다. for w = 0 to W B[0, w] = 0 for i = 1 to n B[i, 0] = 0 for w = 1 to W if wi B[i-1, w] B[i,w] = bi + B[i-1, w-wi] else B[i,w] = B[i-1, w] else B[i, w] = B[i-1, w] 해당 코드는 냅색(Napsack) 문제를 동적 계획법(Dynamic Programming)으로 푸는 방법 중 하나인 0/1 냅색 문제를 푸는 코드입..

Knapsack이란? 냅색(Napsack) 문제는 배낭에 담을 수 있는 무게 한계가 정해져 있고, 각각의 물건들은 무게와 가치가 정해져 있을 때, 배낭에 담을 수 있는 최대 가치의 합을 구하는 문제입니다. 배낭문제는 대표적으로 두 가지 종류로 나뉩니다. 1. 0-1 knapsack problem: 각각의 물건은 단 하나씩만 존재하며, 배낭에 담거나 담지 않거나 둘 중 하나의 선택만 가능하다. 2. Fractional knapsack problem: 각각의 물건은 무게에 비례하여 일부분만 담을 수 있으며, 물건을 자를 수 있다. Branch and Bound Branch and Bound는 최적화 문제를 풀기 위한 알고리즘으로 가능한 모든 해를 차는 대신, 최적의 해를 빠르게 찾기 위해 탐색 범위를 줄이는..

Greedy 란? 각 단계에서 가장 최적의 선택을 하는 것으로, 그 순간에는 최선의 선택이지만 전체적으로는 최적해를 보장하지는 않는 알고리즘입니다. Huffman code란? 데이터를 인코딩(encoding)/디코딩(decoding)하기 위해 필요한 알고리즘입니다. 인코딩하는 과정 ① 입력 문자열에서 문자의 빈도수를 구한다. ② 빈도수를 기준으로 이진 트리를 생성한다. ③ 왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1를 부여해서 huffman 코드를 생성한다. ④ 입력 문자열에서 찾은 huffman 코드를 순차적으로 연결하여 하나의 비트 스트림으로 생성한다. 디코딩하는 과정 ① 저장된 비트 스트림을 읽어 각 문자의 huffman code를 생성해서 원래 문자로 변형한다. 디코딩하는 과정에서 중요하게 살펴..

다이나믹 프로그래밍(Dynamic Programming)란? 큰 문제를 작은 문제로 쪼개서 그 답을 리스트에 저장해서 사용하는 알고리즘입니다. DP를 사용하게 되면 같은 문제를 여러 번 반복되지 않아도 되는 장점이 있기 때문입니다. Recursion을 사용하면 아래 코드와 같이 자기 자신을 계속 호출하게 됩니다. Fib(n) { if(n

마스터 정리 (Master Theorem)란? T(n)=aT(n/b)+f(n) 형식의 재귀적인 알고리즘을 계산하기 위한 방법입니다. ① If f(n) = O(nˡºᵍ𝚋ª⁻ᵋ) Ɛ>0, then T(n) = θ(nˡºᵍ𝚋ª). ② If f(n) = θ(nˡºᵍ𝚋ª), then T(n) = θ(nˡºᵍ𝚋ªlg n). ③ If f(n) = Ω(nˡºᵍ𝚋ª⁺ᵋ) Ɛ>0 and a f(n/b) ≤ c f(n), T(n) = θ(f(n)) 문제를 풀면서 이해를 해보도록 하겠습니다. Excercise 1: T(n) = 4T(n/2) + n T(n)=aT(n/b)+f(n)을 보면 a = 4, b = 2, f(n) = n임을 알 수 있습니다. Case 1에 만족함을 확인했습니다. Excercise 2: T(n) = 4T..

재귀 트리(Recursion Tree Theorem)란? 각 노드가 재귀호출되는 하위 문제에 대한 비용을 나타내는 방법입니다. 치환법으로 추측이 불가능할 때 사용합니다. Step 1: 식 구하기 T(n) = 3T(n/4) + Θ(n2) 계수는 중요하지 않으므로 Θ를 풀 때 c(c>0)로 대체해줍니다. T(n) = 3T(n/4) + cn² Step2: 재귀트리 구하기 cn²을 기준으로 3개의 branch를 생성해줍니다. 위와 같은 방식으로 계속 branch를 생성해 줍니다. T(1)이 나올 때까지 트리를 이어가 줍니다. Step3: 트리의 길이(height) 구하기 그림을 따라서 각각의 트리 레벨의 길이를 구하다보면 트리의 총 길이는 1 = n/4ʰ임을 알 수 있습니다. 1 = n/4ʰ 은 n = 4ʰ로 ..

점근적 표기법(Asymptotic notation)란? 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법으로, 중요하지 않은 상수와 계수들은 무시하면서 실행시간을 표기하는 것을 말합니다. 점근적 표기법의 종류는 아래와 같습니다. Theta - f(n) = θ(g(n)) BigO - f(n) = O(g(n)) Omega - f(n) = Ω(g(n)) Little Oh - f(n) = o(g(n)) Little Omega - f(n) = ω(g(n)) Theta, BigOh, Omega는 자주 사용되기 때문에 더 자세히 알아보도록 하겠습니다. BigO - f(n) = O(g(n)) Big O는 최악의 경우에 이 기준을 넘지 않음을 의미합니다. Omega - f(n) = Ω(g(n)..

시간복잡도(Time complexity)란? 작성한 코드의 실행 시간을 말합니다. 작성한 코드의 반복문, 입력 값 등을 통해 대략적으로 실행 시간을 추측할 수 있습니다. 아래 그래프는 자료의 수가 증가함에 따라 소요되는 처리시간 증가율을 나타내는 그래프입니다. 하나하나 살펴보도록 하겠습니다! O(1) printf("Hello world!") O(1)은 일정한 복잡도(constant complexity)이며, 입력값이 증가하더라도 시간이 증가하지 않습니다. o(n) for(int i = 0; i0){ i+=j; j/=2; } O(log n)은 로그 복잡도(logarithmic complextify)라고 부르며, 알고리즘을 수행할 때마다 찾아야할 대상이 절반으로 줄게됩니다. → O(1) 다음으로 빠른 시간 ..