9._.coding

활동 선택 문제는 시작 시간과 종료 시간이 주어진 다양한 활동 중에서 가장 많은 활동을 할 수 있는 활동의 집합을 고르는 문제이다. 활동의 정보를 보고 활동 간의 관계를 계산하여 가장 긴 활동들의 sequence를 구한다. 이 문제는 순간의 최적을 전체의 최적이라고 판단하는 그리디 알고리즘으로 구할 수 있는데, 가장 빨리 끝나는 (=종료 시간이 가장 빠른) 활동을 선택하여, 남는 시간이 가장 크도록 하는 활동들을 최적이라고 판단하여 선택한다. 그리디 알고리즘의 개념은 아래 게시물에 잘 설명되어 있다. 가장 짧은 활동, 가장 덜 겹치는 활동, 일찍 시작하는 활동을 선택할 경우 반례가 존재해 문제 전체로 봤을 때 최적의 해를 구할 수 없게 되기 때문이다. 수열 S = {1, 2, … , n}을 종료 시간 순..

그리디 알고리즘은 현재 가장 좋아보이는 선택을 하는 알고리즘이다. 다시 말해, 순간마다 최적의 선택을 진행하여 적합한 해를 도출하며, 그것이 전체의 최적이 될 것이라고 생각한다. 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성되며, 이를 최적 부분 구조라고 한다. 이러한 특성으로 인해, 그리디 알고리즘은 장점과 단점이 뚜렷한 알고리즘이다. 장점은 각 부분에서 최적의 선택을 진행하기 때문에 계산 속도가 빠르다. 단점은 부분에서만 최적을 계산하기 때문에 전체적으로 봤을 떄 최적이 아닐 가능성이 있어 도출된 해가 최적임을 보장하지 않는다. 그리디 알고리즘은 Greedy-Choice Property(탐욕적 선택 속성)과 Optimal Substructure(최적 부분 구조)를 만족하는 문제를..

연쇄행렬곱셈 문제는 행렬곱의 횟수를 최소로 할 때의 최적 답안과 그 횟수를 구하는 문제이다. 행렬을 곱할 때에는 한 번에 두 행렬끼리만 곱할 수 있는데, 여러 행렬을 곱해 답을 구하는 과정에서, 어떠한 행렬쌍을 먼저 곱하는지에 따라 연산의 횟수가 달라지게 된다. 예를 들어 A는 2x3 행렬, B는 3x5 행렬, C는 5x2 행렬이라고 가정했을 때, ((A B) C)는 50회, (A (B C))는 42회가 나오는 것처럼 괄호의 위치에 따라 연산 횟수가 다르게 나온다. 따라서, 가장 적은 횟수로 최종 행렬곱을 구하는 방법을 구하는 것이 연쇄 행렬 곱셈이다. 이 계산을 하기 위해 일일이 하나하나 곱해가면서 값을 비교해 최솟값을 구한다면, 위에 보이는 식과 같이 기하급수적으로 값이 (시간복잡도가) 커지게 된다...

편집 거리 문제, Edit Distance Problem은 하나의 문자열을 수정해 Insert/Delete/Copy(또는 Substitute)를 사용하여 최소한의 횟수/비용으로 다른 문자열로 변환하는 문제이다. 하나의 문자열을 최소 시행을 거쳐 다른 문자열로 변환하기 위해서는 copy라는 과정을 꼭 거쳐야 한다. algorithm을 alligator로 바꾸는 예제를 살펴보자. Insert/Delete/Copy를 적절히 사용하여 사진에서처럼 변환해주면, (회색은 아직 하지 않은 부분, 남색은 삽입, 빨간색은 삭제, 보라색은 복사) 14번의 시행으로 변환을 마칠 수 있다. 그렇다면, 이게 그냥 다 지우고 다시 쓰는 것과 무슨 차이가 있을까? Copy를 사용해 문자열을 변환했을 경우에는 14번의 시행인데, a..

Longest Common Subsequence, 줄여서 LCS는 주어진 여러 수열의 공통 부분수열 중에서 가장 긴 수열을 찾는 문제이다. 아래 예시로, 수열 x와 y가 있다고 하자. x는 ABCBDAB, y는 BDCABA일 때, 이 둘의 공통 수열은 매우 다양하지만, 그 중에서 가장 긴 수열은 BCBA이다. 이처럼 다양한 공통 수열 중에서 가장 긴 것을 찾는 문제이다. 문제 해결을 위하여 테이블을 구성하고, 일치하는 문자가 있을 경우 더해주는 방식의 DP를 사용했다. DP, 동적 계획법에 대한 내용은 아래 링크에 자세하게 설명되어 있다. [알고리즘] Dynamic Programming (동적 계획법) 동적 계획법, Dynamic Programming(DP)는 최적화 이론의 한 종류로, 특정 값을 구하기..

T(n) = aT(a/b) + f(n)의 형식일 때 마스터 정리를 활용해 시간 복잡도를 간단하게 계산할 수 있다.

T(n)의 복잡도를 추정하기 위해, 즉 알고리즘의 시간복잡도를 모델링하기 위해서 재귀트리를 사용합니다. 재귀트리를 이용해 시간복잡도를 구하기 위해서는 점화식이 필요한데, 점화식을 다양한 높이의 재귀호출에서 발생할 비용을 나타내는 노드가 있는 트리 구조로 변환합니다. 시간 복잡도를 구하기 위해 높이와 층별 노드합을 구해야 하는데, 높이는 n층에서의 일반항을 구해 나타내며(필기 참조), 노드합은 하나의 깊이에서 노드를 모두 더해 나타냅니다. 계수가 같고 합이 일정한 경우 점화식이 T(n) = 2T(n/2) + cn의 꼴이므로 T(n)은 호출 시마다 2개의 T(n/2)를 호출합니다. 따라서 트리가 그림과 같이 그려지게 되고, 각 층의 노드합은 cn이 되며, 그러므로 O(nlogn)의 시간복잡도를 가지게 됩니다..

동적 계획법, Dynamic Programming(DP)는 최적화 이론의 한 종류로, 특정 값을 구하기 위해서 다른 범위의 값을 이용해 효율적으로 값을 구하는 알고리즘으로, 쉽게 말해 답을 재활용하는 알고리즘이다. 답을 구하기 위한 계산을 반복하는 구조, 즉 같은 답을 계속 내서 다른 값을 이용해야 하는 문제(대표적으로 피보나치 수열)에 매우 뛰어난 방법이다. 분할 정복 기법 - 큰 문제를 작은 문제로 쪼개어 풀이하는 알고리즘에서 값을 저장하는 로직이 추가되었다고 할 수도 있다. 가장 중요한 아이디어는 문제를 재계산(예를 들어 재귀적으로 풀이하는 기법)하지 않는 것이고, 이를 막기 위해 값을 기억하거나 테이블을 만들어 해결한다. 그러므로, 최종 목표를 달성하기 위한 단계를 한 번 씩만 풀게 된다는 것을 ..

점근 표기법, Asymptotic Notation을 활용해 우리는 극한(입력값 n이 충분히 클 때)에서 함수의 동작을 설명할 수 있습니다. 주로 시간 복잡도(Time Complexity)에서 사용합니다. 특정 함수를 다른 함수들을 통해 비교하여 그 특정 함수가 어느 정도 범위를 가질지 예측하는 것으로 이것을 통해, 알고리즘의 우열을 구할 수 있고 어떤 알고리즘이 더 효율적인지 분석할 수 있습니다. 예를 들어, T(n) = 10n^2 + 7n + 102라고 하면 낮은 차수의 항을 삭제하고, 최고차항의 계수를 지워 n^2으로 나타냅니다. Big-O Notation 가장 많이 사용되는 점근표기법, 빅 오 표기법(Big-O notation)입니다. 필기 사진에 나와있듯, 빅오 표기는 f(n) = O(g(n)) ..