Dynamic Programming - 편집 역사

2025년 11월 24일 (월) 05:14에 Pinkgo님의 편집

2025-11-24T05:14:22Z

← 이전 판		2025년 11월 24일 (월) 05:14 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	상위 문서: [[알고리즘 설계와 분석#문제\|알고리즘 설계와 분석]]		상위 문서: [[알고리즘 설계와 분석#Dynamic Programming\|알고리즘 설계와 분석]]

	==개요==		==개요==

Pinkgo: /* Limitations of Dynamic Programming */

2025-11-18T06:22:52Z

Limitations of Dynamic Programming

← 이전 판		2025년 11월 18일 (화) 06:22 판
88번째 줄:		88번째 줄:
	동적 프로그래밍은 효율적이지만 항상 사용 가능한 것은 아니다. 동적 프로그래밍은 부분 문제의 결과를 테이블에 저장하여 전체 계산을 빠르게 하므로, 이를 효율적으로 구현하기 위해서는 부분 문제의 수가 작아야 한다. 예를 들어 순열(Permutations) 문제에 대해, n개의 원소를 순열로 나누면 n!개의 순열이 존재하므로 부분 문제의 수가 많아 이를 다 저장할 수 없다. 따라서 순열 기반 문제는 보통 동적 프로그래밍이 불가능하다. 이는 부분집합의 경우에도 n개의 원소를 가지는 집합에 대한 부분집합의 개수는 2<sup>n</sup>이므로 동적 프로그래밍이 불가능하다. 또한 TSP 문제도 동적 프로그래밍으로 기존 <math>O(n^2)</math> 알고리즘보다 더욱 효율적으로 구현할 수 있음에도 저장의 문제로 구현하지 못하는 예시이다. TSP의 점화식은 아래와 같다:		동적 프로그래밍은 효율적이지만 항상 사용 가능한 것은 아니다. 동적 프로그래밍은 부분 문제의 결과를 테이블에 저장하여 전체 계산을 빠르게 하므로, 이를 효율적으로 구현하기 위해서는 부분 문제의 수가 작아야 한다. 예를 들어 순열(Permutations) 문제에 대해, n개의 원소를 순열로 나누면 n!개의 순열이 존재하므로 부분 문제의 수가 많아 이를 다 저장할 수 없다. 따라서 순열 기반 문제는 보통 동적 프로그래밍이 불가능하다. 이는 부분집합의 경우에도 n개의 원소를 가지는 집합에 대한 부분집합의 개수는 2<sup>n</sup>이므로 동적 프로그래밍이 불가능하다. 또한 TSP 문제도 동적 프로그래밍으로 기존 <math>O(n^2)</math> 알고리즘보다 더욱 효율적으로 구현할 수 있음에도 저장의 문제로 구현하지 못하는 예시이다. TSP의 점화식은 아래와 같다:
	<math>T(i;S)=\min_{j\in S}C[i,j]+T(j;S-\{j\})</math>		<math>T(i;S)=\min_{j\in S}C[i,j]+T(j;S-\{j\})</math>
	이 경우 시간복잡도는 <math>n^22^n</math>이며, 기존 알고리즘보다 더욱 빠르지만 부분문제의 개수가 너무 많아 동적 프로그래밍으로 구현할 수 없다. 반대로 동적 프로그래밍이 적용될 수 있는 대표적인 예시가 문자열 관련 문제인데, 문자열의 substring의 개수는 <math>n(n+1)/</math>이므로 충분히 적용할 수 있다.		이 경우 시간복잡도는 <math>n^22^n</math>이며, 기존 알고리즘보다 더욱 빠르지만 부분문제의 개수가 너무 많아 동적 프로그래밍으로 구현할 수 없다. 반대로 동적 프로그래밍이 적용될 수 있는 대표적인 예시가 문자열 관련 문제인데, 문자열의 substring의 개수는 <math>n(n+1)/2</math>이므로 충분히 적용할 수 있다.

	또한 동적 프로그래밍는 선형 구조나, 왼쪽에서 오른쪽으로의 순서가 있는 구조와 같이 순서가 고정된 구조에서 강하다. 이는 예를 들어 트리 구조 관련된 문제, 문자열의 문자들, 행렬 chain, 다각형 boundary 위의 점들과 관련한 문제가 있다.		또한 동적 프로그래밍는 선형 구조나, 왼쪽에서 오른쪽으로의 순서가 있는 구조와 같이 순서가 고정된 구조에서 강하다. 이는 예를 들어 트리 구조 관련된 문제, 문자열의 문자들, 행렬 chain, 다각형 boundary 위의 점들과 관련한 문제가 있다.

Pinkgo: /* Book Partition Problem */

2025-11-18T06:18:29Z

Book Partition Problem

← 이전 판		2025년 11월 18일 (화) 06:18 판
81번째 줄:		81번째 줄:
	그 이전 구간들(1 ~ i)은 k−1개의 구간으로 나눠져야 한다. 이에 따라 전체 partition의 cost(최대 구간 합)는 아래와 같이 구해진다:		그 이전 구간들(1 ~ i)은 k−1개의 구간으로 나눠져야 한다. 이에 따라 전체 partition의 cost(최대 구간 합)는 아래와 같이 구해진다:
	<math>M[n,k]=\min^n_{i=1} \max(M[i,k-1], \sum^n_{j=i+1}s_j)</math>		<math>M[n,k]=\min^n_{i=1} \max(M[i,k-1], \sum^n_{j=i+1}s_j)</math>
	base case 1: <math>M[1][k]=s_1</math>: 원소 하나는 구간 합이 그 원소뿐		base case 1: <math>M[1,k]=s_1</math>: 원소 하나는 구간 합이 그 원소뿐
	base case 2: <math>M[n][1]=\sum^n_{i=1}s_i</math>: 한 구간만 있으면 전체 합		base case 2: <math>M[n,1]=\sum^n_{i=1}s_i</math>: 한 구간만 있으면 전체 합
	위 점화식을 그대로 구현하면, DP 테이블의 크기는 <math>n\times k=O(nk)</math>이고, 각 DP cell에 대한 계산은 <math>1\le i \le n</math>을 만족하는 <math>i</math>에 대해 전부 계산한다. 이에 따라 총 시간복잡도는 <math>O(nk)\times O(n)= O(kn^2)</math>이다.		위 점화식을 그대로 구현하면, DP 테이블의 크기는 <math>n\times k=O(nk)</math>이고, 각 DP cell에 대한 계산은 <math>1\le i \le n</math>을 만족하는 <math>i</math>에 대해 전부 계산한다. 이에 따라 총 시간복잡도는 <math>O(nk)\times O(n)= O(kn^2)</math>이다.

Pinkgo: /* High-Density Bar Codes */

2025-11-18T05:56:28Z

High-Density Bar Codes

← 이전 판		2025년 11월 18일 (화) 05:56 판
66번째 줄:		66번째 줄:
	* Shift: 일시적으로 다른 모드의 한 글자를 표현하는 명령이지만, 비용이 latch보다 작다.		* Shift: 일시적으로 다른 모드의 한 글자를 표현하는 명령이지만, 비용이 latch보다 작다.
	따라서 문장을 인코딩할 때는 “지금 모드를 유지할까? 잠깐 shift할까? latch해서 영구적으로 바꿀까?”라는 복잡한 선택이 필요하다. 기존 방식과 달리 동적 프로그래밍을 활용하면 모든 prefix에 대해 모든 모드의 최소 비용을 계산할 수 있다. 이를 위한 DP 테이블은 M[i][j]와 같이 구성된다. 이는 모드 j에서 끝난 i번째 문자까지 고려했을 때 누적 최소 비용을 의미한다. 이에 대한 DP 점화식은 아래와 같다:		따라서 문장을 인코딩할 때는 “지금 모드를 유지할까? 잠깐 shift할까? latch해서 영구적으로 바꿀까?”라는 복잡한 선택이 필요하다. 기존 방식과 달리 동적 프로그래밍을 활용하면 모든 prefix에 대해 모든 모드의 최소 비용을 계산할 수 있다. 이를 위한 DP 테이블은 M[i][j]와 같이 구성된다. 이는 모드 j에서 끝난 i번째 문자까지 고려했을 때 누적 최소 비용을 의미한다. 이에 대한 DP 점화식은 아래와 같다:
	<math>M[i][j] = min(M[i-1,k]+</math>i번째 문자를 <math>k</math>에서 <math>j</math>로 인코딩한 비용		<math>M[i][j] = min(M[i-1][k]+</math>i번째 문자를 <math>k</math>에서 <math>j</math>로 인코딩한 비용
	이는 단순한 greedy 알고리즘보다 평균 8%이상 성능을 개선하는 효과를 가진다.		이는 단순한 greedy 알고리즘보다 평균 8%이상 성능을 개선하는 효과를 가진다.

Pinkgo: /* Limitations of Dynamic Programming */

2025-11-16T18:15:05Z

Limitations of Dynamic Programming

← 이전 판		2025년 11월 16일 (일) 18:15 판
86번째 줄:		86번째 줄:

	==Limitations of Dynamic Programming==		==Limitations of Dynamic Programming==
			동적 프로그래밍은 효율적이지만 항상 사용 가능한 것은 아니다. 동적 프로그래밍은 부분 문제의 결과를 테이블에 저장하여 전체 계산을 빠르게 하므로, 이를 효율적으로 구현하기 위해서는 부분 문제의 수가 작아야 한다. 예를 들어 순열(Permutations) 문제에 대해, n개의 원소를 순열로 나누면 n!개의 순열이 존재하므로 부분 문제의 수가 많아 이를 다 저장할 수 없다. 따라서 순열 기반 문제는 보통 동적 프로그래밍이 불가능하다. 이는 부분집합의 경우에도 n개의 원소를 가지는 집합에 대한 부분집합의 개수는 2<sup>n</sup>이므로 동적 프로그래밍이 불가능하다. 또한 TSP 문제도 동적 프로그래밍으로 기존 <math>O(n^2)</math> 알고리즘보다 더욱 효율적으로 구현할 수 있음에도 저장의 문제로 구현하지 못하는 예시이다. TSP의 점화식은 아래와 같다:
			<math>T(i;S)=\min_{j\in S}C[i,j]+T(j;S-\{j\})</math>
			이 경우 시간복잡도는 <math>n^22^n</math>이며, 기존 알고리즘보다 더욱 빠르지만 부분문제의 개수가 너무 많아 동적 프로그래밍으로 구현할 수 없다. 반대로 동적 프로그래밍이 적용될 수 있는 대표적인 예시가 문자열 관련 문제인데, 문자열의 substring의 개수는 <math>n(n+1)/</math>이므로 충분히 적용할 수 있다.

			또한 동적 프로그래밍는 선형 구조나, 왼쪽에서 오른쪽으로의 순서가 있는 구조와 같이 순서가 고정된 구조에서 강하다. 이는 예를 들어 트리 구조 관련된 문제, 문자열의 문자들, 행렬 chain, 다각형 boundary 위의 점들과 관련한 문제가 있다.

			동적 프로그래밍이 가능하기 위한 가장 중요한 이론적 조건은 Principle of Optimality이다. 이는 아래와 같다:
			어떤 문제의 최적 해가 존재하려면 그 해의 부분구성 요소(sub-solution)도 최적이어야 한다.
			즉, 전체 최적해의 앞부분이 최적이 아니라면 전체 최적해가 될 수 없다는 것이다. 이 원리가 깨지면 동적 프로그래밍이 불가능하다. 예를 들어 [[Shortest Paths#Dijkstra’s Algorithm\|Dijkstra’s Algorithm]]는 동적 프로그래밍 기반으로 작동한다. 이때 Dijkstra 알고리즘이 동적 프로그래밍으로 구현될 수 있는 이유는 어떤 노드 x까지의 최단 경로가 그 이전 노드까지의 경로가 최단거리를 포함한다는 원칙이 있기 때문이다. 즉, 이는 Principle of Optimality를 만족한다.

	==각주==		==각주==

Pinkgo: /* Book Partition Problem */

2025-11-16T17:46:12Z

Book Partition Problem

← 이전 판		2025년 11월 16일 (일) 17:46 판
83번째 줄:		83번째 줄:
	base case 1: <math>M[1][k]=s_1</math>: 원소 하나는 구간 합이 그 원소뿐		base case 1: <math>M[1][k]=s_1</math>: 원소 하나는 구간 합이 그 원소뿐
	base case 2: <math>M[n][1]=\sum^n_{i=1}s_i</math>: 한 구간만 있으면 전체 합		base case 2: <math>M[n][1]=\sum^n_{i=1}s_i</math>: 한 구간만 있으면 전체 합
	위 점화식을 그대로 구현하면, DP 테이블의 크기는 <math>n\times k=O(nk)</math>이고, 각 DP cell에 대한 계산은 <math>1\le i \le n</math>을 만족하는 <math>i</math>에 대해 전부 계산한다. 이에 따라 총 시간복잡도는 <math>O(nk)\~~timesO~~(n)=O(kn^2)</math>이다.		위 점화식을 그대로 구현하면, DP 테이블의 크기는 <math>n\times k=O(nk)</math>이고, 각 DP cell에 대한 계산은 <math>1\le i \le n</math>을 만족하는 <math>i</math>에 대해 전부 계산한다. 이에 따라 총 시간복잡도는 <math>O(nk)\times O(n)= O(kn^2)</math>이다.

	==Limitations of Dynamic Programming==		==Limitations of Dynamic Programming==

	==각주==		==각주==

Pinkgo: /* Book Partition Problem */

2025-11-16T17:45:57Z

Book Partition Problem

← 이전 판		2025년 11월 16일 (일) 17:45 판
70번째 줄:		70번째 줄:

	==Book Partition Problem==		==Book Partition Problem==
			책 분할 문제(Book Partition Problem)는 책들의 길이가 다를 때, 이를 k명의 작업자에게 공평하게 나누는 문제이다. 입력과 문제 상황을 구체화하면 아래와 같다:
			Input: 책들의 배열 <math>S=\{s_1,S_2,\cdots,s_n\}</math>, 작업자 <math>k</math>
			Problem: Partition <math>S</math> into <math>k</math> ranges, so as to minimize the maximum sum over all the ranges.
			예를 들어 <math>k = 3</math>이고 <math>S = \{100, 200, 300, 400, 500, 600, 700, 800, 900\}</math>과 같이 주어진다면, 아래와 같이 분할해야 하는 것이다.
			100 200 300 400 500 \| 600 700 \| 800 900
			위는 첫 번째 구간의 합은 1500이고, 두 번째 구간의 합은 1300이고, 세 번째 합은 1700이다. 이는 주어진 문자열에 대해 각 구간의 합을 가능한 한 비슷하게 만들어, 가장 큰 구간의 합을 최소화한 것이다. 이때 평균을 기준으로 나누는 방식은 항상 최적을 보장해주지 않기 때문에, 동적 프로그래밍이 해당 문제를 해결하기 위해 사용된다.

			점화식을 유도하기 위해, 마지막 partition을 (i+1)~n 구간으로 둔다고 가정하자. 이 경우 마지막 구간의 합은 아래와 같이 구해진다:
			<math>\sum^n_{j=i+1}s_j</math>
			그 이전 구간들(1 ~ i)은 k−1개의 구간으로 나눠져야 한다. 이에 따라 전체 partition의 cost(최대 구간 합)는 아래와 같이 구해진다:
			<math>M[n,k]=\min^n_{i=1} \max(M[i,k-1], \sum^n_{j=i+1}s_j)</math>
			base case 1: <math>M[1][k]=s_1</math>: 원소 하나는 구간 합이 그 원소뿐
			base case 2: <math>M[n][1]=\sum^n_{i=1}s_i</math>: 한 구간만 있으면 전체 합
			위 점화식을 그대로 구현하면, DP 테이블의 크기는 <math>n\times k=O(nk)</math>이고, 각 DP cell에 대한 계산은 <math>1\le i \le n</math>을 만족하는 <math>i</math>에 대해 전부 계산한다. 이에 따라 총 시간복잡도는 <math>O(nk)\timesO(n)=O(kn^2)</math>이다.

	==Limitations of Dynamic Programming==		==Limitations of Dynamic Programming==

	==각주==		==각주==

Pinkgo: /* Edit Distance */

2025-11-16T17:25:18Z

Edit Distance

@@ 53번째 줄: / 53번째 줄: @@
 ==[[Edit Distance]]==
 [[Edit Distance]]에 대한 자세한 설명은 해당 문서를 참조해 주십시오.
 ==각주==

Pinkgo: /* The Gas Station Problem */

2025-11-15T03:33:49Z

The Gas Station Problem

← 이전 판		2025년 11월 15일 (토) 03:33 판
50번째 줄:		50번째 줄:
	==[[The Gas Station Problem]]==		==[[The Gas Station Problem]]==
	[[The Gas Station Problem]]에 대한 자세한 설명은 해당 문서를 참조해 주십시오.		[[The Gas Station Problem]]에 대한 자세한 설명은 해당 문서를 참조해 주십시오.

			==[[Edit Distance]]==
			[[Edit Distance]]에 대한 자세한 설명은 해당 문서를 참조해 주십시오.

	==각주==		==각주==

Pinkgo: /* The Gas Station Problem */

2025-11-15T03:31:35Z

The Gas Station Problem

@@ 48번째 줄: / 48번째 줄: @@
 [[Binomial Coefficients|이항 계수(Binomial Coefficients)]]에 대한 자세한 설명은 해당 문서를 참조해 주십시오.
-==The Gas Station Problem==
+==[[The Gas Station Problem]]==
-Gas Station Problem은 아래와 같은 문제 정의를 가진다:
+[[The Gas Station Problem]]에 대한 자세한 설명은 해당 문서를 참조해 주십시오.
 ==각주==