Crat

7-5. 동적 계획법 예제 문제 - #4. 강화하기

1. 강화하기 +1, +2, +3 만큼 강화되는 아이템이 +N강에 도달하는 경우의 수를 구하는 문제이다. 2. 코드 분석 #include #include #include using namespace std; // 강화하기 // +1, +2, +3 중 하나씩 강화되어 +N에 도달하는 경우의 수 구하기 int cache[100]; int N; // num에서 시작해서 +N 까지 가는 경우의 수 int Enchant(int num) { // 예외 사항 if (num > N) return 0; if (num == N) return 1; // 캐시 확인 int& ret = cache[num]; if (ret != -1) return ret; // 문제 풀이 return ret = Enchant(num + 1) +..

7-4. 동적 계획법 예제 문제 - #3. Tic-Tac-Toe(틱택토)

1. Tic-Tac-Toe (틱택토) 3 x 3 사이즈의 보드에서 X 또는 O의 표시로 가로 or 세로 or 대각선으로 한 줄을 이으면 승리하는 게임이다. 2. 코드 분석 #include #include #include using namespace std; // Tic-Tac-Toe // 특정 상태의 보드판 상태에서 승리 여부를 판단하기 int HashKey(const vector& board) { int ret = 0; for (int y = 0; y < 3; y++) { for (int x = 0; x < 3; x++) { ret = ret * 3; if (board[y][x] == 'o') ret += 1; else if (board[y][x] == 'x') ret += 2; } } return r..

7-3. 동적 계획법 예제 문제 - #2. TRIANGLE_PATH(삼각형 위의 최대경로)

1. TRIANGLEPATH ex) 5행 TRIANGLEPATH 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 맨 위 꼭지점부터 시작하여 한 단계씩 아래로 내려가며 경로를 선택한다 이 때 바로 아래의 숫자 혹은 아래 오른쪽의 숫자로만 이동이 가능하다. 맨 아래 줄까지 내려가면 경로가 완성되고 선택한 경로의 숫자를 더하여 최종 결과를 얻는다. 이 문제의 목표는 숫자 합이 최대가 되는 값을 찾는 것이다. 2. 코드 분석 #include #include #include using namespace std; // 6 // 1 2 // 3 7 4 // 9 4 1 7 // 2 7 5 9 4 int N = 5; vector board; // N x N size vector cache; vector nex..

7-2. 동적 계획법 예제 문제 - #1. LIS(최장 증가 부분 수열)

1. LIS(최장 증가 부분 수열 ; Longest Increasing Subsequence) 부분 수열은 수열의 일부 숫자를 지우고 남은 수열이다. (단, 수열의 순서가 변경되면 안됨) 순 증가 부분 수열은 수열의 배열이 증가하는 형태인 수열이다. (ex. 1, 3, 5는 순 증가 부분 수열, 1, 3, 7, 4는 순 증가 부분 수열이 아니다) LIS는 제일 긴 순 증가 부분 수열을 뜻한다. 즉 수열에서 가장 긴 순 증가 부분 수열의 길이를 찾는 것이 목표이다. 2. 코드 분석 #include #include #include using namespace std; int cache[100]; vector seq = { 1,9,2,5,7 }; // 문제가 요구하는 정답을 반환한다 int LIS(int po..

7-1. 동적 계획법(Dynamic Programming)

1. 이항 계수(조합 ; Combination), 경우의 수 (1) 5개의 공 중에서 2개를 뽑는 경우의 수는? (2) 코드로 구현하기 #include #include using namespace std; int combination(int n, int r) { if (r == 0 || n == r) return 1; return combination(n - 1, r - 1) + combination(n - 1, r); } int main() { __int64 start = GetTickCount64(); int num = combination(45, 6); __int64 end = GetTickCount64(); cout