알고리즘의 점근적 분석이란? 크기가 작은 문제에서는 알고리즘의 효율성이 중요하지 않다. 그래서 비효율적인 알고리즘을 사용해도 무방하다. (오히려 더 빠른 경우도 존재한다) 크기가 충분히 큰 문제에서는 알고리즘의 효율성이 매우 중요하다. 그래서 비효율적인 알고리즘은 치명적으로 작용한다. 이렇게 입력의 크기가 충분히 큰 경우에 대한 분석을 점근적 분석이라 한다. 표기법에는 Ο, Ω, Θ, ω, ο 가 존재한다. 점근적 상한 ( asymptotic upper bound ) 정의 (lim n->INF) f(n) / g(n) 0, n0 ≥ 0 s.t.∀n ≥ n0, cg(n) ≥ f(n) } f(n) ∈ O(g(n))을 관행적으로 f(n) = O(g(n))이라고 쓴다. 직관적 의미 f(n) = O(g(n)) ⇒ ..

알고리즘의 수행 시간을 좌우하는 기준은 다양하게 잡을 수 있습니다. 예를 들면 반복문의 반복 횟수, 특정한 행이 수행되는 횟수, 함수의 호출횟수 등이 있죠. 복잡도 분석 예시 Algorithm A Algorithm B Algorithm C sum

다이나믹 프로그래밍 적용 문제 (4) 최장 공통 부분순서 LCS 문제 설명 부분순서와 공통 부분순서의 예시는 다음과 같다. 는 문자열 의 부분순서. 는 문자열 와 의 공통 부분순서. 최장 공통 부분순서(Longest Common Subsequence)란 공통 부분순서들 중 가장 긴 것을 말한다. 예를 들어, 다음 두 문자열의 LCS를 구하면 다음과 같다. h e r o i c a l l y s c h o l a r l y 결과 문자열 : holly, LCS : 5 주어지는 두 문자열의 LCS를 구하라. 점화식 LCS(i, j) : 문자열 X[i] = "x1,x2, … ,xi" 과 Y[j] = "y1,y2, … ,yj" 의 LCS 길이 LCS(i, j) = { 0 ( if i = 0 or j = 0 ) L..

다이나믹 프로그래밍 적용 문제 (3) 행렬 곱셈 순서 문제 설명 행렬 A1, A2, A3, . . . , An을 곱하는 수를 최소로 하는 최적의 곱셈 순서를 구하라. 예로, 행렬 A(2 × 3), B(3 × 5), C(5 × 2)가 있을 때 곱할 수 있는 경우의 수는 다음과 같다. (AB)C = 2 × 3 × 5 + 2 × 5 × 2 = 50 A(BC) = 3 × 5 × 2 + 2 × 3 × 2 = 42 두 경우의 수에서 최솟값인 42에 해당하는 연산이 최소의 곱셈 횟수 42와 최적의 곱셈 순서 A(BC) 가 된다. 마지막 행렬 곱셈이 수행되는 상황을 다음과 같이 정리할 수 있으며, 경우의 수는 총 n - 1이다. 점화식 Ak의 크기 : pk-1 * pk m[i, j] : 행렬 Ai, …, Aj의 곱을 ..

다이나믹 프로그래밍 적용 문제 (2) 조약돌 놓기 문제 설명 • 3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 있다 • 조약돌을 놓는 방법 (제약조건) - 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다 - 각 열에는 적어도 하나 이상의 조약돌을 놓는다 • 목표: 돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌을 놓는다 5 2 -1 3 -1 8 -5 0 2 3 12 7 • 임의의 열을 채울 수 있는 패턴은 모두 4가지다. 패턴 위치 P1 ● P2 ● P3 ● P4 ● ● • 서로 양립할 수 있는 패턴은 다음과 같다. 패턴 양립 가능한 패턴 P1 P2 P3 P2 P1 P3 P4 P3 P1 P2 P4 P2 예로, 어떤 i열의 패턴이 P3라면 전 열에 올 수 있는 패턴은 P1과 P..

다이나믹 프로그래밍 적용 문제 (1) 행렬 경로 문제 설명 양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 우하단까지 이동한다. • 이동 방법 (제약조건) - 오른쪽이나 아래쪽으로만 이동할 수 있다 - 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다 • 목표: 좌상단에서 우하단까지 이동하되, 방문한 칸에 있는 점수들의 최대합을 구한다. 점화식 maxSum[i, j] = 위치 (i, j) 에 이르는 최대합 m[i, j] = 위치 (i, j) 에 해당하는 원본 값 0 ( if i = 0 or j=0 ) m[i, j] + max(maxSum[i - 1, j], maxSum[i, j - 1]) ( else ) 최대합 = maxSum(n, n) (i, j)의 위치에 있는 값은 위치의 위쪽 혹은 왼쪽 ..