9._.coding

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

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

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