다이나믹 프로그래밍 (1) - 부분집합의 합 / 문자열 시퀀스

0. 들어가며

분할 정복 패러다임 개념을 확장
매우 복합적이며 창의력과 인내심, 추상적 개념을 시각화하는 능력을 요구하는 경우가 많음
다이나믹 프로그래밍이 자주 사용되는 몇 가지 예
- 조합 (특정 기준을 만족하는 시퀀스의 조합 또는 순열의 개수 구하기)
- 문자열과 시퀀스 (편집 거리, 최장 공통 부분 시퀀스, 최장 증가 부분 시퀀스)
- 그래프 (최단 경로 문제)
- 머신러닝 (음성/얼굴인식)

1. 동적 계획법(Dynamic programming)이란?

피보나치 수열을 통한 동적 계획법 설명
- 피보나치의 재귀조건 : $F(n) = F(n-1) + F(n-2)$
- 피보나치의 기저조건 : $F(0) , F(1)$
하향식 방법 : 재귀 트리의 맨 꼭대기서 시작하여 기저 조건에 닿을 때까지 이동
- 피보나치의 경우 여러 개의 부분 문제가 나타나며
- 중복되는 부분 문제라는 특성을 가지고 있음
전체 문제에 대한 최적해가 부분 문제의 최적해의 조합으로 표현 → 최적 부분 구조

2. 메모이제이션 : 하향식 접근 방법

메모이제이션 (memoization) : 메모를 통해 접근
각 단계에서 부분 문제의 답을 찾을 경우 이를 배열 구조 캐시에 저장
캐시에 저장되어 있는지 확인 후
캐시에 저장되어 있으면 그 값만을 반환
→ 상당히 많은 중복 작업 제거 가능

3. 타뷸레이션 : 상향식 접근 방법

타뷸레이션 (tabulation) : 기저 조건 해답부터 시작하여 모든 부분문제에 대한 해답을 표에 저장한 후 재사용하는 방식
메모리 사용량 관점에서 매우 효율적
가능한 모든 상태를 나타내는 룩업 테이블 생성
문제에 대한 임의의 상태 참조 시에는 최선의 방법

4. 부분 집합의 합 문제

“음수가 아닌 정수로 이루어진 집합 S와 임의의 정수 x가 주어질 때, S의 부분집합 중에서 그원소의 합이 x와 같은 부분집합이 존재하는 가?”

1) 1단계 : 동적 계획법 필요조건 분석하기

중복되는 부분 문제 / 최적 부분 구조
부분집합의 합 문제의 경우
- 크기가 n인 부분집합은 크기가 n-1인 부분집합에 새로운 원소를 추가하여 생성 → 최적 부분 구조
- 서로 다른 부분지합이 더 작은 크기의 같은 부분집합으로부터 생성 → 중복되는 부분 문제

2) 2단계 : 기저 조건과 상태 정의하기

상태를 구성하기 위해 필요한 것이 무엇인지 파악
문제의 해를 구하기 위한 가장 직관적인 방법부터 구현해보기
전수 조사 / 백트래킹 / 메모이제이션 / 타뷸레이션의 4가지 접근 방법을 통해 구현

3) 2-(a)단계 : 전수 조사

전수 조사 방법을 구현하는 것은 필수적인 단계일 수도 있음
- 단순성 : 효율성에 대한 고려없이 단순한 방법으로 문제의 해를 구하는 작업을 통해 문제의 근본적인 속성 이해
- 정답 비교를 위한 수단 : 복잡한 동적 계획법의 경우, 주어진 문제를 충분히 이해하게 되면 상당히 많은 재설계 필요 → 동적 계획법으로 구한 해답과 비교
- 부분 문제를 시각화 : 올바른 해답이 형성되는 방식을 시각화하는 수단을 제공, 다른 풀이 방법에서 사용할 수 있는 필수 패턴을 찾을 수 있음

4) 연습 문제 36: 전수 조사 방식으로 부분집합의 합 문제 풀기

#include <iostream>
#include <vector>
#include <algorithm>

#define DEBUG 1

#if DEBUG
#define PRINT(x) cerr << x
#else
#define PRINT(x)
#endif

using namespace std;

void GetAllSubsets(vector<int> set, vector<int> subset,
	int index, vector<vector<vector<int>>>& allSubsets)
{
	// 집합 set의 끝에 도달한 경우
	if (index == set.size())
	{
		// 부분집합 크기를 인덱스로 사용하여 부분집합을 allSubsets에 추가
		allSubsets[subset.size()].push_back(subset);
		return;
	}

	// 원소를 추가하지 않고 재귀 호출
	GetAllSubsets(set, subset, index + 1, allSubsets);

	// 원소를 부분집합에 추가한 후 재귀 호출
	subset.push_back(set[index]);
	GetAllSubsets(set, subset, index + 1, allSubsets);
}

bool SubsetSum_BruteForce(vector<int> set, int target)
{
	vector<vector<vector<int>>> allSubsets(set.size() + 1);

	GetAllSubsets(set, {}, 0, allSubsets);

	for (int size = 0; size <= set.size(); size++)
	{
		PRINT("부분집합의 원소 개수: " << size << endl);

		for (auto subset : allSubsets[size])
		{
			PRINT("\\t{ ");

			int sum = 0;
			for (auto number : subset)
			{
				sum += number;
				PRINT(number << " ");
			}

			PRINT("} = " << sum << endl);

			if (sum == target)
				return true;
		}
	}

	return false;
}

int main()
{
	vector<int> set = {13, 79, 45, 29};
	int target = 58;

	bool found = SubsetSum_BruteForce(set, target);

	if (found)
	{
		cout << "원소 합이 " << target << "인 부분집합이 있습니다." << endl;
	}
	else
	{
		cout << "원소 합이 " << target << "인 부분집합이 없습니다." << endl;
	}
}

5) 2-(b)단계 : 최적화 적용하기 - 백트래킹

전수 조사의 경우 성능 면에서 가장 비효율적
모든 부분 문제 중에서 유효하지 않은 경우를 제거하는 백트래킹 기법
백트래킹 기법 구현 : 문제의 기저 조건 / 상태의 재귀적 표현
부분집합 합 문제의 기저 조건
- 만약 현재 부분 집합의 합이 target과 같다면 : True
- 그렇지 않다면 :
  - 만약 현재 부분집합의 합이 target보다 크면 : False
  - 만약 집합의 끝에 도달한 경우 : False
부분집합 합 문제의 상태 변화 방식
- 집합 set의 i번째 원소 set[i]와 부분집합 ss에 대해:
  - 만약 ss의 합에 set[i]를 더한 결과가 target보다 작거나 같으면:
    1. ss에 set[i] 추가
    2. i 증가
    → 다음상태 ( i = i+1 , ss = ss + set[i] )
  - 모든 경우에 대해:
    1. ss에 set[i]를 추가하지 않음
    2. i 증가
    → 다음상태 ( i = i + 1, ss = ss )
부분집합 합 문제의 상태 변화 의사 코드
- 집합 set의 i번째 원소 set[i]와 부분집합 합 sum에 대해:
  - 만약 sum에 set[i]를 더한 결과가 target보다 작거나 같으면:
    1. sum에 set[i] 더함
    2. i 증가
    → 다음상태 ( i = i+1 , sum = sum + set[i] )
  - 모든 경우에 대해:
    1. sum에 set[i]를 더하지 않음
    2. i 증가
    → 다음상태 ( i = i + 1, sum = sum )

6) 연습 문제 37: 백트래킹을 사용하여 부분집합의 합 문제 풀기

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <iomanip>

#define DEBUG 0

#if DEBUG
#define PRINT(x) cerr << x
#else
#define PRINT(x)
#endif

using namespace std;

const int UNKNOWN = -1;

void GetAllSubsets(vector<int> set, vector<int> subset,
	int index, vector<vector<vector<int>>>& allSubsets)
{
	// 집합 set의 끝에 도달한 경우
	if (index == set.size())
	{
		// 부분집합 크기를 인덱스로 사용하여 부분집합을 allSubsets에 추가
		allSubsets[subset.size()].push_back(subset);
		return;
	}

	// 원소를 추가하지 않고 재귀 호출
	GetAllSubsets(set, subset, index + 1, allSubsets);

	// 원소를 부분집합에 추가한 후 재귀 호출
	subset.push_back(set[index]);
	GetAllSubsets(set, subset, index + 1, allSubsets);
}

bool SubsetSum_BruteForce(vector<int> set, int target)
{
	vector<vector<vector<int>>> allSubsets(set.size() + 1);

	GetAllSubsets(set, {}, 0, allSubsets);

	for (int size = 0; size <= set.size(); size++)
	{
		PRINT("부분집합의 원소 개수: " << size << endl);

		for (auto subset : allSubsets[size])
		{
			PRINT("\\t{ ");

			int sum = 0;
			for (auto number : subset)
			{
				sum += number;
				PRINT(number << " ");
			}

			PRINT("} = " << sum << endl);

			if (sum == target)
				return true;
		}
	}

	return false;
}

bool SubsetSum_Backtracking(vector<int> set, int sum, int i)
{
	// 만약 현재 부분집합의 합이 target과 같다면
	if (sum == 0)
	{
		return true;
	}

	// 만약 현재 부분집합의 합이 target보다 크거나, 집합의 끝에 도달했다면
	if (i == set.size() || set[i] > sum)
	{
		return false;
	}

	// Case 1: sum에서 set[i]을 빼서 재귀 호출 (i번째 원소를 부분집합에 추가)
	// Case 2: sum을 그대로 전달하여 재귀 호출 (i번째 원소를 부분집합에 추가하지 않음)

	return SubsetSum_Backtracking(set, sum - set[i], i + 1)
		|| SubsetSum_Backtracking(set, sum, i + 1);
}

vector<string> types =
{
	"BRUTE FORCE",
	"BACKTRACKING",
	"MEMOIZATION",
	"TABULATION"
};

void GetTime(clock_t& timer, string type)
{
	// 현재 시간에서 timer를 빼서 경과 시간을 계산
	timer = clock() - timer;

	// 화면에 경과 시간 출력
	cout << type << " 방법 경과 시간: ";
	cout << fixed << setprecision(5) << (float)timer / CLOCKS_PER_SEC << endl;

	timer = clock(); // timer를 현재 시간으로 초기화
}

int main()
{
	vector<int> set = {16, 1058, 22, 13, 46, 55, 3, 92, 47, 7,
					   98, 367, 807, 106, 333, 85, 577, 9, 3059};
	int target = 6076;
	int tests = 2;

	sort(set.begin(), set.end());

	for (int i = 0; i < tests; i++)
	{
		bool found = false;

		clock_t timer = clock();

		switch (i)
		{
		case 0:
			found = SubsetSum_BruteForce(set, target);
			break;
		case 1:
			found = SubsetSum_Backtracking(set, target, 0);
			break;
		}

		if (found)
		{
			cout << "원소 합이 " << target << "인 부분집합이 있습니다." << endl;
		}
		else
		{
			cout << "원소 합이 " << target << "인 부분집합이 없습니다." << endl;
		}

		GetTime(timer, types[i]);
		cout << endl;
	}
}

7) 3단계 : 메모이제이션

캐시를 사용하여 저장
- 정수 인덱스를 사용하는 일반배열
- 문자열로 표현한 해시 테이블 또는 해시 맵
- 자체적으로 생성한 해시함수를 이용하여 해시 테이블 또는 해시 맵
캐시 사용 방법
- 유효성 : 캐시의 키 값은 서로 다른 상태에 대해 충돌 발생 x
- 유용성 : 캐시에 저장된 값을 참조하는 경우가 아예 발생하지 않으면 아무 의미 없음

8) 연습 문제 38: 메모이제이션을 이용하여 부분집합의 합 문제 풀기

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <iomanip>

#define DEBUG 0

#if DEBUG
#define PRINT(x) cerr << x
#else
#define PRINT(x)
#endif

using namespace std;

const int UNKNOWN = -1;

void GetAllSubsets(vector<int> set, vector<int> subset,
	int index, vector<vector<vector<int>>>& allSubsets)
{
	// 집합 set의 끝에 도달한 경우
	if (index == set.size())
	{
		// 부분집합 크기를 인덱스로 사용하여 부분집합을 allSubsets에 추가
		allSubsets[subset.size()].push_back(subset);
		return;
	}

	// 원소를 추가하지 않고 재귀 호출
	GetAllSubsets(set, subset, index + 1, allSubsets);

	// 원소를 부분집합에 추가한 후 재귀 호출
	subset.push_back(set[index]);
	GetAllSubsets(set, subset, index + 1, allSubsets);
}

bool SubsetSum_BruteForce(vector<int> set, int target)
{
	vector<vector<vector<int>>> allSubsets(set.size() + 1);

	GetAllSubsets(set, {}, 0, allSubsets);

	for (int size = 0; size <= set.size(); size++)
	{
		PRINT("부분집합의 원소 개수: " << size << endl);

		for (auto subset : allSubsets[size])
		{
			PRINT("\\t{ ");

			int sum = 0;
			for (auto number : subset)
			{
				sum += number;
				PRINT(number << " ");
			}

			PRINT("} = " << sum << endl);

			if (sum == target)
				return true;
		}
	}

	return false;
}

bool SubsetSum_Backtracking(vector<int> set, int sum, int i)
{
	// 만약 현재 부분집합의 합이 target과 같다면
	if (sum == 0)
	{
		return true;
	}

	// 만약 현재 부분집합의 합이 target보다 크거나, 집합의 끝에 도달했다면
	if (i == set.size() || set[i] > sum)
	{
		return false;
	}

	// Case 1: sum에서 set[i]을 빼서 재귀 호출 (i번째 원소를 부분집합에 추가)
	// Case 2: sum을 그대로 전달하여 재귀 호출 (i번째 원소를 부분집합에 추가하지 않음)

	return SubsetSum_Backtracking(set, sum - set[i], i + 1)
		|| SubsetSum_Backtracking(set, sum, i + 1);
}

bool SubsetSum_Memoization(vector<int>& set, int sum, int i,
	vector<vector<int>>& memo)
{
	// 만약 현재 부분집합의 합이 target과 같다면
	if (sum == 0)
	{
		return true;
	}

	// 만약 현재 부분집합의 합이 target보다 크거나, 집합의 끝에 도달했다면
	if (i == set.size() || set[i] > sum)
	{
		return false;
	}

	// 현재 상태가 캐시에 있는지 확인
	if (memo[i][sum] == UNKNOWN)
	{
		// 현재 상태에 대한 솔루션을 구하여 캐시에 저장
		bool append = SubsetSum_Memoization(set, sum - set[i], i + 1, memo);
		bool ignore = SubsetSum_Memoization(set, sum, i + 1, memo);

		memo[i][sum] = append || ignore;
	}

	// 캐시에 저장된 값을 반환
	return memo[i][sum];
}

vector<string> types =
{
	"BRUTE FORCE",
	"BACKTRACKING",
	"MEMOIZATION",
	"TABULATION"
};

void GetTime(clock_t& timer, string type)
{
	// 현재 시간에서 timer를 빼서 경과 시간을 계산
	timer = clock() - timer;

	// 화면에 경과 시간 출력
	cout << type << " 방법 경과 시간: ";
	cout << fixed << setprecision(5) << (float)timer / CLOCKS_PER_SEC << endl;

	timer = clock(); // timer를 현재 시간으로 초기화
}

int main()
{
	vector<int> set = {16, 1058, 22, 13, 46, 55, 3, 92, 47, 7,
					   98, 367, 807, 106, 333, 85, 577, 9, 3059};
	int target = 6799;
	int tests = 3;

	sort(set.begin(), set.end());

	for (int i = 0; i < tests; i++)
	{
		bool found = false;

		clock_t timer = clock();

		switch (i)
		{
		case 0:
			found = SubsetSum_BruteForce(set, target);
			break;
		case 1:
			found = SubsetSum_Backtracking(set, target, 0);
			break;
		case 2:
		{
			// 메모이제이션 테이블 초기화
			vector<vector<int>> memo(set.size(), vector<int>(7000, UNKNOWN));

			found = SubsetSum_Memoization(set, target, 0, memo);
			break;
		}
		}

		if (found)
		{
			cout << "원소 합이 " << target << "인 부분집합이 있습니다." << endl;
		}
		else
		{
			cout << "원소 합이 " << target << "인 부분집합이 없습니다." << endl;
		}

		GetTime(timer, types[i]);
		cout << endl;
	}
}

9) 4단계 : 타뷸레이션

하향식 로직
- 부분집합의 합 목표치와 집합의 첫 번쨰 인덱스에서 시작
- 입력 집합 전체에 대해 반복:
  - 만약 부분집합의 합이 0이 되면 True
  - 만약 입력 집합의 끝에 도달했다면 False
  - 그렇지 않으면 부분집합의 합에서 현재 인덱스의 집합 원소를 빼거나 또는 그대로 유지
- 만약 부분집합의 합 x와 인덱스 i로 표현되는 상태 S에서 목표치를 찾을 수 있다면, 상태 S로이어질 수 있는 모든 이전 상태에서도 목표치를 찾을 수 있음
상향식 로직
- 부분집합의 합과 인덱스를 0으로 설정
- 입력 집합 전체에 대해 반복:
  - 만약 인덱스가 0에서 i 사이일 때 x와 같은 부분집합의 합을 찾을 수 있다면, 인덱스가 0에서 i+1사이에서도 x와 같은 부분 집합을 찾을 수 있음
  - 만약 인덱스가 0에서 i 사이일 때 x와 같은 부분집합의 합을 찾을 수 있다면, 인덱스가 0에서 i+1사이에서도 x + set[i]와 같은 부분 집합을 찾을 수 있음
- 상태 S1에서 부분집합의 합이 x와 같고 인덱스가 i인 경우, 하나라도 성립하면 memo(i,x) = true
  - 부분집합의 합이 x-set[i]이고 인덱스가 i+1인 상태 S2에서 목표치가 발견될 경우
  - 부분집합의 합이 x이고 인덱스가 i+1인 상태 S3에서 목표치가 발견될 경우
  → 그렇지 않으면 memo(i,x) = false

10) 연습 문제 39: 타뷸레이션을 이용하여 부분집합의 합 문제 풀기

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <iomanip>

#define DEBUG 0

#if DEBUG
#define PRINT(x) cerr << x
#else
#define PRINT(x)
#endif

using namespace std;

const int UNKNOWN = -1;

void GetAllSubsets(vector<int> set, vector<int> subset,
	int index, vector<vector<vector<int>>>& allSubsets)
{
	// 집합 set의 끝에 도달한 경우
	if (index == set.size())
	{
		// 부분집합 크기를 인덱스로 사용하여 부분집합을 allSubsets에 추가
		allSubsets[subset.size()].push_back(subset);
		return;
	}

	// 원소를 추가하지 않고 재귀 호출
	GetAllSubsets(set, subset, index + 1, allSubsets);

	// 원소를 부분집합에 추가한 후 재귀 호출
	subset.push_back(set[index]);
	GetAllSubsets(set, subset, index + 1, allSubsets);
}

bool SubsetSum_BruteForce(vector<int> set, int target)
{
	vector<vector<vector<int>>> allSubsets(set.size() + 1);

	GetAllSubsets(set, {}, 0, allSubsets);

	for (int size = 0; size <= set.size(); size++)
	{
		PRINT("부분집합의 원소 개수: " << size << endl);

		for (auto subset : allSubsets[size])
		{
			PRINT("\\t{ ");

			int sum = 0;
			for (auto number : subset)
			{
				sum += number;
				PRINT(number << " ");
			}

			PRINT("} = " << sum << endl);

			if (sum == target)
				return true;
		}
	}

	return false;
}

bool SubsetSum_Backtracking(vector<int> set, int sum, int i)
{
	// 만약 현재 부분집합의 합이 target과 같다면
	if (sum == 0)
	{
		return true;
	}

	// 만약 현재 부분집합의 합이 target보다 크거나, 집합의 끝에 도달했다면
	if (i == set.size() || set[i] > sum)
	{
		return false;
	}

	// Case 1: sum에서 set[i]을 빼서 재귀 호출 (i번째 원소를 부분집합에 추가)
	// Case 2: sum을 그대로 전달하여 재귀 호출 (i번째 원소를 부분집합에 추가하지 않음)

	return SubsetSum_Backtracking(set, sum - set[i], i + 1)
		|| SubsetSum_Backtracking(set, sum, i + 1);
}

bool SubsetSum_Memoization(vector<int>& set, int sum, int i,
	vector<vector<int>>& memo)
{
	// 만약 현재 부분집합의 합이 target과 같다면
	if (sum == 0)
	{
		return true;
	}

	// 만약 현재 부분집합의 합이 target보다 크거나, 집합의 끝에 도달했다면
	if (i == set.size() || set[i] > sum)
	{
		return false;
	}

	// 현재 상태가 캐시에 있는지 확인
	if (memo[i][sum] == UNKNOWN)
	{
		// 현재 상태에 대한 솔루션을 구하여 캐시에 저장
		bool append = SubsetSum_Memoization(set, sum - set[i], i + 1, memo);
		bool ignore = SubsetSum_Memoization(set, sum, i + 1, memo);

		memo[i][sum] = append || ignore;
	}

	// 캐시에 저장된 값을 반환
	return memo[i][sum];
}

vector<vector<bool>> SubsetSum_Tabulation(vector<int>& set)
{
	int maxSum = 0;

	for (int i = 0; i < set.size(); i++)
	{
		maxSum += set[i];
	}

	vector<vector<bool>> DP(set.size() + 1, vector<bool>(maxSum + 1, 0));

	for (int i = 0; i < set.size(); i++)
	{
		DP[i][0] = true;
	}

	for (int i = 1; i <= set.size(); i++)
	{
		for (int sum = 1; sum <= maxSum; sum++)
		{
			if (sum < set[i - 1])
			{
				DP[i][sum] = DP[i - 1][sum];
			}
			else
			{
				DP[i][sum] = DP[i - 1][sum]
					|| DP[i - 1][sum - set[i - 1]];
			}
		}
	}

	return DP;
}

vector<string> types =
{
	"BRUTE FORCE",
	"BACKTRACKING",
	"MEMOIZATION",
	"TABULATION"
};

void GetTime(clock_t& timer, string type)
{
	// 현재 시간에서 timer를 빼서 경과 시간을 계산
	timer = clock() - timer;

	// 화면에 경과 시간 출력
	cout << type << " 방법 경과 시간: ";
	cout << fixed << setprecision(5) << (float)timer / CLOCKS_PER_SEC << endl;

	timer = clock(); // timer를 현재 시간으로 초기화
}

int main()
{
	vector<int> set = {16, 1058, 22, 13, 46, 55, 3, 92, 47, 7,
					   98, 367, 807, 106, 333, 85, 577, 9, 3059};
	int target = 6076;
	int tests = 4;

	sort(set.begin(), set.end());

	for (int i = 0; i < tests; i++)
	{
		bool found = false;

		clock_t timer = clock();

		switch (i)
		{
		case 0:
			found = SubsetSum_BruteForce(set, target);
			break;
		case 1:
			found = SubsetSum_Backtracking(set, target, 0);
			break;
		case 2:
		{
			// 메모이제이션 테이블 초기화
			vector<vector<int>> memo(set.size(), vector<int>(7000, UNKNOWN));

			found = SubsetSum_Memoization(set, target, 0, memo);
			break;
		}
		case 3:
		{
			int total = 0;
			for (auto number : set)
				total += number;

			vector<vector<bool>> DP = SubsetSum_Tabulation(set);
			found = DP[set.size()][target];

			vector<int> subsetSums;
			for (int sum = 1; sum <= total; sum++)
			{
				if (DP[set.size()][sum])
				{
					subsetSums.push_back(sum);
				}
			}

			cout << "다음과 같이 " << subsetSums.size() << "가지의 부분집합의 합이 가능합니다:" << endl;

			for (auto sum : subsetSums)
				cout << sum << " ";
			cout << endl;

			break;
		}
		}

		if (found)
		{
			cout << "원소 합이 " << target << "인 부분집합이 있습니다." << endl;
		}
		else
		{
			cout << "원소 합이 " << target << "인 부분집합이 없습니다." << endl;
		}

		GetTime(timer, types[i]);
		cout << endl;
	}
}

11) 실습 문제 18: 여행 경로

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

typedef long long LL;

const LL MOD = 1000000007;

LL TravelItinerary(int n, vector<int> distance)
{
	reverse(distance.begin(), distance.end());

	vector<LL> DP(n + 1, 0);
	vector<LL> sums(n + 2, 0);

	DP[0] = sums[1] = 1;

	for (int i = 1; i <= n; i++)
	{
		int dist = distance[i - 1];
		LL sum = sums[i] - sums[i - dist];

		DP[i] = (DP[i] + sum) % MOD;
		sums[i + 1] = (sums[i] + DP[i]) % MOD;
	}

	return (DP[n] < 0) ? DP[n] + MOD : DP[n];
}

vector<int> Generate(int n)
{
	vector<int> distance(n);
	LL val = 1;

	for (int i = 0; i < n; i++)
	{
		val = (val * 1103515245 + 12345) / 65536;
		val %= 32768;

		distance[i] = ((val % 10000) % (n - i)) + 1;
	}

	return distance;
}

int main()
{
	int n;
	cin >> n;

	vector<int> distance(n);

	if (n == 1e7)
	{
		distance = Generate(n);
	}
	else
	{
		for (int i = 0; i < n; i++)
		{
			cin >> distance[i];
		}
	
		cout << endl;
	}

	LL result = TravelItinerary(n, distance);
	cout << result << endl;
}

5. 문자열과 시퀀스에 대한 동적 계획법

1) 최장 공통 부분 시퀀스

두 개의 데이터 시퀀스가 주어질 때, 두 시퀀스에 공통으로 나타나는 가장 긴 부분 시퀀스는 무엇인가?
해당 문제의 상태를 표현하기 위해
- 만약 i가 A의 길이보다 커지거나 또는 j가 B의 길이보다 커지면:
  - 재귀를 종료하고, 부분 시퀀스 반환
- 만약 A[i]=B[j]이면:
  - 부분 시퀀스 길이 1 증가
  - i와 j 각각 1씩 증가
- 그렇지 않으면 :
  1. (i+1)번째와 j번째 문자에 대해 검사 진행
  2. i번째와 (j+1)번째 문자에 대해 검사 진행
최적 부분 구조는 명확하지 않음

2) 연습 문제 40: 전수 조사 방식으로 최장 공통 부분 시퀀스 문제 풀기

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>

#define DEBUG 1

#if DEBUG
#define PRINT(x) cerr << x
#else
#define PRINT(x)
#endif

using namespace std;

vector<vector<pair<int, int>>> found;

int LCS_BruteForce(string A, string B, int i, int j, 
	               vector<pair<int, int>> subsequence)
{
	// 만약 i가 A의 길이보다 커지거나 또는 j가 B의 길이보다 커지면:
	if (i >= A.size() || j >= B.size())
	{
		found.push_back(subsequence);

		// 재귀를 종료하고 부분 시퀀스의 길이를 반환합니다.
		return subsequence.size();
	}

	// 만약 A[i] = B[j] 이면:
	if (A[i] == B[j])
	{
		// 부분 시퀀스 길이를 1만큼 증가합니다.
		subsequence.push_back({i, j});

		// i와 j를 각각 1씩 증가합니다.
		return LCS_BruteForce(A, B, i + 1, j + 1, subsequence);
	}

	/* 그렇지 않으면:
	
	   옵션 1) (i + 1)번째와 j번째 문자에 대해 검사를 진행합니다.
	   옵션 2) i번째와 (j + 1)번째 문자에 대해 검사를 진행합니다.

	   이 상태의 LCS는 옵션 1 및 옵션 2의 최댓값과 같습니다.
	 */

	return max(LCS_BruteForce(A, B, i + 1, j, subsequence),
		LCS_BruteForce(A, B, i, j + 1, subsequence));
}

void PrintSubsequences(string A, string B)
{
	// 람다 함수를 이용한 정렬
	sort(found.begin(), found.end(), [](auto a, auto b)
		{
			// 부분 시퀀스 길이를 기준으로 정렬
			if (a.size() != b.size())
			{
				return a.size() < b.size();
			}

			// 두 부분 시퀀스 길이가 같다면 인덱스의 사전 순서로 정렬
			return a < b;
		});

	// 중복 제거
	found.erase(unique(found.begin(), found.end()), found.end());

	int previousSize = 0;

	for (auto subsequence : found)
	{
		if (subsequence.size() != previousSize)
		{
			previousSize = subsequence.size();
			PRINT("SIZE = " << previousSize << endl);
		}

		// 밑줄을 이용하여 문자의 자리를 표현
		string a_seq(A.size(), '_');
		string b_seq(B.size(), '_');

		for (auto pair : subsequence)
		{
			// 빈칸을 부분 문자열 문자로 채우기
			a_seq[pair.first] = A[pair.first];
			b_seq[pair.second] = B[pair.second];
		}

		PRINT("\\t" << a_seq << " " << b_seq << endl);
	}
}

int main()
{
	string A, B;
	cin >> A >> B;

	int LCS = LCS_BruteForce(A, B, 0, 0, {});
	cout << A << "와 " << B << "의 최장 공통 부분 시퀀스 길이: " << LCS << endl;

#if DEBUG
	PrintSubsequences(A, B);
#endif
}

3) 최적화 첫 단계 : 최적 부분 구조 찾기

만약 두 문자열 중 하나라도 빈 문자열이면:
- LCS = 0
그렇지 않으면:
- A의 부분 문자열과 B의 부분 문자열의 마지막 문자가 같으면:
  - A와 B의 부분 문자열에서 구한 LCS 길이는 각 부분 문자열에서 마지막 한 문자를 제외한 문자열의 LCS 길이에 1을 더한 것과 같음
- 그렇지 않으면:
  - LCS 길이는 다음 두 경우의 최댓값과 같음:
    1. A의 부분 문자열에서 마지막 문자를 제외한 것과 B의 부분 문자열에서 구한 LCS 길이
    2. B의 부분 문자열에서 마지막 문자를 제외한 것과 A의 부분 문자열에서 구한 LCS 길이

4) 실습 문제 19: 메모이제이션을 이용하여 최장 공통 부분 시퀀스 찾기

#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <time.h>
#include <iomanip>
#include <iostream>

#define DEBUG 0

#if DEBUG
#define PRINT(x) cerr << x
#else
#define PRINT(x)
#endif

using namespace std;

vector<vector<pair<int, int>>> found;

int LCS_BruteForce(string A, string B, int i, int j, 
	               vector<pair<int, int>> subsequence)
{
	// 만약 i가 A의 길이보다 커지거나 또는 j가 B의 길이보다 커지면:
	if (i >= A.size() || j >= B.size())
	{
		found.push_back(subsequence);

		// 재귀를 종료하고 부분 시퀀스의 길이를 반환합니다.
		return subsequence.size();
	}

	// 만약 A[i] = B[j] 이면:
	if (A[i] == B[j])
	{
		// 부분 시퀀스 길이를 1만큼 증가합니다.
		subsequence.push_back({i, j});

		// i와 j를 각각 1씩 증가합니다.
		return LCS_BruteForce(A, B, i + 1, j + 1, subsequence);
	}

	/* 그렇지 않으면:
	
	   옵션 1) (i + 1)번째와 j번째 문자에 대해 검사를 진행합니다.
	   옵션 2) i번째와 (j + 1)번째 문자에 대해 검사를 진행합니다.

	   이 상태의 LCS는 옵션 1 및 옵션 2의 최댓값과 같습니다.
	 */

	return max(LCS_BruteForce(A, B, i + 1, j, subsequence),
		LCS_BruteForce(A, B, i, j + 1, subsequence));
}

void PrintSubsequences(string A, string B)
{
	// 람다 함수를 이용한 정렬
	sort(found.begin(), found.end(), [](auto a, auto b)
		{
			// 부분 시퀀스 길이를 기준으로 정렬
			if (a.size() != b.size())
			{
				return a.size() < b.size();
			}

			// 두 부분 시퀀스 길이가 같다면 인덱스의 사전 순서로 정렬
			return a < b;
		});

	// 중복 제거
	found.erase(unique(found.begin(), found.end()), found.end());

	int previousSize = 0;

	for (auto subsequence : found)
	{
		if (subsequence.size() != previousSize)
		{
			previousSize = subsequence.size();
			PRINT("SIZE = " << previousSize << endl);
		}

		// 밑줄을 이용하여 문자의 자리를 표현
		string a_seq(A.size(), '_');
		string b_seq(B.size(), '_');

		for (auto pair : subsequence)
		{
			// 빈칸을 부분 문자열 문자로 채우기
			a_seq[pair.first] = A[pair.first];
			b_seq[pair.second] = B[pair.second];
		}

		PRINT("\\t" << a_seq << " " << b_seq << endl);
	}
}

const int UNKNOWN = -1;

int LCS_Memoization(string A, string B, int i, int j, 
	                vector<vector<int>>& memo)
{
	// 기저 조건 - 빈 문자열에 대해서는 0을 반환
	if (i == 0 || j == 0)
	{
		return 0;
	}

	// 두 문자열의 부분 문자열에 대해 결과가 저장되어 있으면 반환
	// Have we found a result for the prefixes of the two strings?
	if (memo[i - 1][j - 1] != UNKNOWN)
	{
		return memo[i - 1][j - 1];
	}

	// A와 B의 두 부분 문자열에서 맨 마지막 문자가 같은지 확인
	if (A[i - 1] == B[j - 1])
	{
		// 이 경우 A와 B의 부분 문자열에서 구한 LCS 길이는 각 부분 문자열에서 
		// 마지막 한 문자를 제외한 문자열로부터 구한 LCS 길이에 1을 더한 것과 같음

		memo[i - 1][j - 1] = 1 + LCS_Memoization(A, B, i - 1, j - 1, memo);

		// 테이블에 저장된 결과를 반환
		return memo[i - 1][j - 1];
	}

	// A와 B의 두 부분 문자열에서 맨 마지막 문자가 같지 않다면
	// A의 부분 문자열에서 마지막 문자를 제외한 것과 B의 부분 문자열에서 구한 LCS 길이,
	// B의 부분 문자열에서 마지막 문자를 제외한 것과 A의 부분 문자열에서 구한 LCS 길이 중
	// 최댓값을 선택하여 지정

	memo[i - 1][j - 1] = max(LCS_Memoization(A, B, i - 1, j, memo),
		LCS_Memoization(A, B, i, j - 1, memo));

	return memo[i - 1][j - 1];
}

vector<string> types =
{
	"BRUTE FORCE",
	"MEMOIZATION",
	"TABULATION"
};

void GetTime(clock_t& timer, string type)
{
	// 현재 시간에서 timer를 빼서 경과 시간을 계산
	timer = clock() - timer;

	// 화면에 경과 시간 출력
	cout << type << " 방법 경과 시간: ";
	cout << fixed << setprecision(5) << (float)timer / CLOCKS_PER_SEC << endl;

	timer = clock(); // timer를 현재 시간으로 초기화
}

int main()
{
	string A, B;
	cin >> A >> B;

	int tests = 2;

	for (int i = 0; i < tests; i++)
	{
		int LCS;

		clock_t timer = clock();

		switch (i)
		{
		case 0:
		{
			LCS = LCS_BruteForce(A, B, 0, 0, {});

#if DEBUG
			PrintSubsequences(A, B);
#endif
			break;
		}
		case 1:
		{
			vector<vector<int>> memo(A.size(), vector<int>(B.size(), UNKNOWN));
			LCS = LCS_Memoization(A, B, A.size(), B.size(), memo);
			break;
		}
		}

		cout << A << "와 " << B << "의 최장 공통 부분 시퀀스 길이: " << LCS << endl;

		GetTime(timer, types[i]);
		cout << endl;
	}
}

5) 하향식에서 상향식으로 바꾸기: 메모이제이션을 타뷸레이션으로

만약 i = 0 또는 j = 0 :
- LCS(i,j) = 0
그렇지 않으면:
- 만약 두 부분 문자열이 같다면 :
  - LCS(i,j) = LCS(i-1,j) + LCS(i,j-1) + 1
- 그렇지 않으면 :
  - LCS(i,j) = LCS(i-1,j) , LCS(i,j-1) 둘 중의 최댓값

6) 실습 문제 20: 타뷸레이션을 이용하여 최장 공통 부분 시퀀스 찾기

#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <time.h>
#include <iomanip>
#include <iostream>

#define DEBUG 0

#if DEBUG
#define PRINT(x) cerr << x
#else
#define PRINT(x)
#endif

using namespace std;

vector<vector<pair<int, int>>> found;

int LCS_BruteForce(string A, string B, int i, int j, 
	               vector<pair<int, int>> subsequence)
{
	// 만약 i가 A의 길이보다 커지거나 또는 j가 B의 길이보다 커지면:
	if (i >= A.size() || j >= B.size())
	{
		found.push_back(subsequence);

		// 재귀를 종료하고 부분 시퀀스의 길이를 반환합니다.
		return subsequence.size();
	}

	// 만약 A[i] = B[j] 이면:
	if (A[i] == B[j])
	{
		// 부분 시퀀스 길이를 1만큼 증가합니다.
		subsequence.push_back({i, j});

		// i와 j를 각각 1씩 증가합니다.
		return LCS_BruteForce(A, B, i + 1, j + 1, subsequence);
	}

	/* 그렇지 않으면:
	
	   옵션 1) (i + 1)번째와 j번째 문자에 대해 검사를 진행합니다.
	   옵션 2) i번째와 (j + 1)번째 문자에 대해 검사를 진행합니다.

	   이 상태의 LCS는 옵션 1 및 옵션 2의 최댓값과 같습니다.
	 */

	return max(LCS_BruteForce(A, B, i + 1, j, subsequence),
		LCS_BruteForce(A, B, i, j + 1, subsequence));
}

void PrintSubsequences(string A, string B)
{
	// 람다 함수를 이용한 정렬
	sort(found.begin(), found.end(), [](auto a, auto b)
		{
			// 부분 시퀀스 길이를 기준으로 정렬
			if (a.size() != b.size())
			{
				return a.size() < b.size();
			}

			// 두 부분 시퀀스 길이가 같다면 인덱스의 사전 순서로 정렬
			return a < b;
		});

	// 중복 제거
	found.erase(unique(found.begin(), found.end()), found.end());

	int previousSize = 0;

	for (auto subsequence : found)
	{
		if (subsequence.size() != previousSize)
		{
			previousSize = subsequence.size();
			PRINT("SIZE = " << previousSize << endl);
		}

		// 밑줄을 이용하여 문자의 자리를 표현
		string a_seq(A.size(), '_');
		string b_seq(B.size(), '_');

		for (auto pair : subsequence)
		{
			// 빈칸을 부분 문자열 문자로 채우기
			a_seq[pair.first] = A[pair.first];
			b_seq[pair.second] = B[pair.second];
		}

		PRINT("\\t" << a_seq << " " << b_seq << endl);
	}
}

const int UNKNOWN = -1;

int LCS_Memoization(string A, string B, int i, int j, 
	                vector<vector<int>>& memo)
{
	// 기저 조건 - 빈 문자열에 대해서는 0을 반환
	if (i == 0 || j == 0)
	{
		return 0;
	}

	// 두 문자열의 부분 문자열에 대해 결과가 저장되어 있으면 반환
	// Have we found a result for the prefixes of the two strings?
	if (memo[i - 1][j - 1] != UNKNOWN)
	{
		return memo[i - 1][j - 1];
	}

	// A와 B의 두 부분 문자열에서 맨 마지막 문자가 같은지 확인
	if (A[i - 1] == B[j - 1])
	{
		// 이 경우 A와 B의 부분 문자열에서 구한 LCS 길이는 각 부분 문자열에서 
		// 마지막 한 문자를 제외한 문자열로부터 구한 LCS 길이에 1을 더한 것과 같음

		memo[i - 1][j - 1] = 1 + LCS_Memoization(A, B, i - 1, j - 1, memo);

		// 테이블에 저장된 결과를 반환
		return memo[i - 1][j - 1];
	}

	// A와 B의 두 부분 문자열에서 맨 마지막 문자가 같지 않다면
	// A의 부분 문자열에서 마지막 문자를 제외한 것과 B의 부분 문자열에서 구한 LCS 길이,
	// B의 부분 문자열에서 마지막 문자를 제외한 것과 A의 부분 문자열에서 구한 LCS 길이 중
	// 최댓값을 선택하여 지정

	memo[i - 1][j - 1] = max(LCS_Memoization(A, B, i - 1, j, memo),
		LCS_Memoization(A, B, i, j - 1, memo));

	return memo[i - 1][j - 1];
}

string ReconstructLCS(vector<vector<int>> DP, string A, string B, int i, int j)
{
	if (i == 0 || j == 0)
	{
		return "";
	}

	if (A[i - 1] == B[j - 1])
	{
		return ReconstructLCS(DP, A, B, i - 1, j - 1) + A[i - 1];
	}
	else if (DP[i - 1][j] > DP[i][j - 1])
	{
		return ReconstructLCS(DP, A, B, i - 1, j);
	}
	else
	{
		return ReconstructLCS(DP, A, B, i, j - 1);
	}
}

string LCS_Tabulation(string A, string B)
{
	vector<vector<int>> DP(A.size() + 1, vector<int>(B.size() + 1));

	for (int i = 0; i <= A.size(); i++)
	{
		for (int j = 0; j <= B.size(); j++)
		{
			if (i == 0 || j == 0)
			{
				DP[i][j] = 0;
			}
			else if (A[i - 1] == B[j - 1])
			{
				DP[i][j] = DP[i - 1][j - 1] + 1;
			}
			else
			{
				DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
			}
		}
	}

	string lcs = ReconstructLCS(DP, A, B, A.size(), B.size());

	return lcs;
}

vector<string> types =
{
	"BRUTE FORCE",
	"MEMOIZATION",
	"TABULATION"
};

void GetTime(clock_t& timer, string type)
{
	// 현재 시간에서 timer를 빼서 경과 시간을 계산
	timer = clock() - timer;

	// 화면에 경과 시간 출력
	cout << type << " 방법 경과 시간: ";
	cout << fixed << setprecision(5) << (float)timer / CLOCKS_PER_SEC << endl;

	timer = clock(); // timer를 현재 시간으로 초기화
}

int main()
{
	string A, B;
	cin >> A >> B;

	int tests = 3;

	for (int i = 0; i < tests; i++)
	{
		int LCS;

		clock_t timer = clock();

		switch (i)
		{
		case 0:
		{
			LCS = LCS_BruteForce(A, B, 0, 0, {});

#if DEBUG
			PrintSubsequences(A, B);
#endif
			break;
		}
		case 1:
		{
			vector<vector<int>> memo(A.size(), vector<int>(B.size(), UNKNOWN));
			LCS = LCS_Memoization(A, B, A.size(), B.size(), memo);

			break;
		}
		case 2:
		{
			string lcs = LCS_Tabulation(A, B);

			LCS = lcs.size();

			cout << A << "와 " << B << "의 최장 공통 부분 시퀀스: " << lcs << endl;
			break;
		}
		}

		cout << A << "와 " << B << "의 최장 공통 부분 시퀀스 길이: " << LCS << endl;

		GetTime(timer, types[i]);
		cout << endl;
	}
}

7) 실습 문제 21: 멜로디 순열

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

int CountMelodicPermutations(vector<int> melody, vector<int> set)
{
	unsigned int target = 0;

	for (auto note : set)
	{
		target |= note;
	}

	vector<vector<int>> DP(melody.size() + 1, vector<int>(4096, 0));

	// 기저 조건 -> 공집합
	DP[0][0] = 1;

	for (int i = 1; i <= melody.size(); i++)
	{
		for (unsigned int subset = 0; subset < 4096; subset++)
		{
			// (i-1)에서의 결과 더하기
			DP[i][subset] += DP[i - 1][subset];

			// melody[i-1]를 포함한 부분집합을 고려
			DP[i][subset | melody[i - 1]] += DP[i - 1][subset];
		}
	}

	// 최종 해답
	return DP[melody.size()][target];
}

vector<int> ConvertNotes(vector<string> notes)
{
	map<string, int> M =
	{
		{"A", 0},
		{"A#", 1},
		{"Bb", 1},
		{"B", 2},
		{"Cb", 2},
		{"B#", 3},
		{"C", 3},
		{"C#", 4},
		{"Db", 4},
		{"D", 5},
		{"D#", 6},
		{"Eb", 6},
		{"E", 7},
		{"Fb", 7},
		{"E#", 8},
		{"F", 8},
		{"F#", 9},
		{"Gb", 9},
		{"G", 10},
		{"G#", 11},
		{"Ab", 11}
	};

	vector<int> converted;

	for (auto note : notes)
	{
		converted.push_back(1 << M[note]); // 2의 승수로 매핑
	}

	return converted;
}

int main()
{
	int melodyLength;
	int setLength;

	cin >> melodyLength;

	vector<string> melody(melodyLength);

	for (int i = 0; i < melodyLength; i++)
	{
		cin >> melody[i];
	}

	cin >> setLength;

	vector<string> set(setLength);

	for (int i = 0; i < setLength; i++)
	{
		cin >> set[i];
	}

	int count = CountMelodicPermutations(ConvertNotes(melody), ConvertNotes(set));

	cout << count << endl;

	return 0;
}

출처 : 코딩 테스트를 위한 자료 구조와 알고리즘 with C++ (길벗)

'Computer Science > Data Structure & Algorithm' 카테고리의 다른 글

존슨 알고리즘 (1)	2023.08.17
다이나믹 프로그래밍 (2) - P/NP,플로이드-워셜 알고리즘 (0)	2023.07.06
그래프 알고리즘(2) - 벨만포드, 존슨, 코사리주 알고리즘 (0)	2023.07.04
그래프 알고리즘 (1) - BFS, DFS, 다익스트라 알고리즘 (0)	2023.07.03
그리디 알고리즘 (0)	2023.07.02

0. 들어가며

1. 동적 계획법(Dynamic programming)이란?

2. 메모이제이션 : 하향식 접근 방법

3. 타뷸레이션 : 상향식 접근 방법

4. 부분 집합의 합 문제

1) 1단계 : 동적 계획법 필요조건 분석하기

2) 2단계 : 기저 조건과 상태 정의하기

3) 2-(a)단계 : 전수 조사

4) 연습 문제 36: 전수 조사 방식으로 부분집합의 합 문제 풀기

5) 2-(b)단계 : 최적화 적용하기 - 백트래킹

6) 연습 문제 37: 백트래킹을 사용하여 부분집합의 합 문제 풀기

7) 3단계 : 메모이제이션

8) 연습 문제 38: 메모이제이션을 이용하여 부분집합의 합 문제 풀기

9) 4단계 : 타뷸레이션

10) 연습 문제 39: 타뷸레이션을 이용하여 부분집합의 합 문제 풀기

11) 실습 문제 18: 여행 경로

5. 문자열과 시퀀스에 대한 동적 계획법

1) 최장 공통 부분 시퀀스

2) 연습 문제 40: 전수 조사 방식으로 최장 공통 부분 시퀀스 문제 풀기

3) 최적화 첫 단계 : 최적 부분 구조 찾기

4) 실습 문제 19: 메모이제이션을 이용하여 최장 공통 부분 시퀀스 찾기

5) 하향식에서 상향식으로 바꾸기: 메모이제이션을 타뷸레이션으로

6) 실습 문제 20: 타뷸레이션을 이용하여 최장 공통 부분 시퀀스 찾기

7) 실습 문제 21: 멜로디 순열

'Computer Science > Data Structure & Algorithm' 카테고리의 다른 글

티스토리툴바