문제 해결 알고리즘 기초/동적 계획 (9) 썸네일형 리스트형 [알고스팟] Triangle Path 문제의 경로 개수 세기 - 동적 계획 Triangle path 문제의 경로 개수 세기(링크) #include using namespace std; vector triangle; int cache[100][100]; int n; int trianglePathMemoization(int y, int x) { // Base case if (y == triangle.size() - 1) return triangle[y][x]; // Memoization int& ret = cache[y][x]; if (ret != -1) return ret; return ret = triangle[y][x] + max(trianglePathMemoization(y + 1, x), trianglePathMemoization(y + 1, x + 1)); } int c.. [알고스팟] 타일링 방법의 수 세기 - 동적 계획 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 타일링 방법의 수 세기(링크) 완전 탐색으로 생각한 후 메모이제이션을 적용하자. 각 작업 조각마다 2 x n 사각형의 맨 왼쪽 세로줄을 덮어 나간다. 맨 왼쪽 세로줄을 덮는 방법은 타일 하나를 세워서 놓거나, 두 개의 타일을 가로로 놓으면 된다. 타일 하나를 세워서 놓으면 가로의 길이가 n - 1 인 사각형이 남고 두 개의 타일을 가로로 놓으면 가로의 길이가 n - 2 인 사각형이 남는다. 2 x 2 인 사각형을 생각해보면 타일 하나를 세워 놓으면 2 x 1 인 사각형이 남고 타일 두개를 놓으면 사각형이 모두 채워진다. 따라서, 가로 길이가 1 혹은 0 인 경우에 (세로 타일 한 개를 놓으면 되거나 이미 사각형을 모두 채웠으므로 사각형을 채운.. [알고스팟] 원주율 외우기 - 동적 계획, 최적 부분 구조 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 원주율 외우기(링크) 먼저 완전 탐색의 방식으로 생각해보면 3개, 4개, 5개로 나눌 수 있는 모든 경우에 대해 나눠진 조각의 난이도를 계산하고 이를 비교해 가장 낮은 결과를 선택한다. 직관적으로 최적 부분 구조가 성립함을 알 수 있다. 어떤 위치에 있던지 남은 숫자들에 대해서는 가장 낮은 난이도 점수를 받을 수 있도록 나누어야 한다. (그 이전 수들은 어떻게 나누었는지 고려할 필요 없다.) 그러므로 현재 작업 중인 조각에 대해 계산한 난이도 점수와 재귀 호출할 다음 작업 조각의 점수를 더해 반환하는 방식으로 부분 문제를 정의한다. #include #include #include using namespace std; const int INF .. 최적해 문제를 동적 계획법으로 구하는 순서 1. 완전 탐색 알고리즘 작성. 주어진 최적해 문제를 완전 탐색 알고리즘으로 해결하는 코드를 작성한다. 2. 부분 문제의 정의를 변경. 부분 문제가 현재까지 거쳐 온 전체 답을 반환하는 것이 아닌, 앞으로 남은 선택들에 해당하는 값을 반환하도록 부분 문제의 정의를 바꾼다. 기존의 부분 문제가 현재 단계의 문제를 해결한 결과를 변수에 누적하여 다음 단계로 재귀 했다면, 현재 단계를 해결한 값에 다음 단계의 값(재귀 호출) 들을 더한 값을 반환하는 것이다. 이전에 작성한 Triangle path 문제를 예로 들면, 완전 탐색으로 구현한 경우 현재 단계의 점수인 try[y][x] 를 sum 에 누적해 그 값으로 다음 선택을 재귀호출 했다. path(y, x, sum) = max(path(y+1,x,sum+tr.. [알고스팟] 최대 증가 부분 수열 - 동적 계획, 최적해, 최적 부분 구조 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 최대 증가 부분 수열(링크) 각 원소로부터 출발한 재귀함수에서 해당 원소보다 뒤에 있는 원소 중 더 큰 것들만 골라 다시 재귀에 진입한다. 부분 수열을 가지고 재귀하지 않고 현재 Index 를 함수의 입력으로 한다. 즉, 현재 원소보다 큰 다음 원소의 Index 를 재귀로 입력한다. (다음에 선택될 원소는 항상 이전 원소보다 크므로 항상 모든 큰 값을 가지는 부분 수열을 재귀의 입력으로 줄 필요 없다.) 어떤 위치의 원소에 대해 다음으로 선택할 원소는 이전에 선택했던 원소와 관계없이 일정하므로 최적 부분 구조를 가지는 문제이다. (어떤 위치에서의 최적의 결과는 이전의 선택과 무관하게 일정.) 따라서, 현재 함수에 진입하는 Index 에 대한 .. 동적 계획과 최적화 문제, Triangle Path(알고스팟) ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 동적 계획법으로 최적해 찾기 동적 계획법은 일반적으로 최적화 문제의 해결을 위해 사용된다. 최적화 문제는 가능한 여러 답 중 가장 좋은 답을 찾는 문제로, 최적화 문제의 동적 계획 역시 완전 탐색에서 시작하지만 어떤 조건이 만족하면 좀 더 효율적으로 구현 가능하다. 최적 부분 구조 완전 탐색의 어떤 부분 문제에 대해 어떤 경로로 해당 부분 문제에 도달했건 남은 부분 문제는 항상 최적으로 풀어도 상관 없는 문제를 최적 부분 구조를 가진다고 말한다. 이런 문제는 각 부분 문제의 최적해를 통해 전체 문제의 최적해를 쉽게 얻어낼 수 있다. 예를 들어, 서울에서 부산까지의 최단 경로를 구할 때 최단 경로가 대전을 지난다면, 서울-대전과 대전-부산의 각.. [알고스팟] Wild Card - 동적 계획 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 와일드 카드(링크) 문자열을 대조해서 찾는데 * 는 모두 대응 되므로 * 의 다음 문자와 일치하는 부분 문자열을 하나씩 잘라가며 찾는다. 메모이제이션을 활용할 때는 저장 공간을 reset 하는 시점을 잘 확인해야 한다. #include #include #include #include using namespace std; // -1: initial state, 0: false, 1: true int cache[101][101]; string wildCard, fileName; int findMatch(int w, int f) { int& ret = cache[w][f]; if (ret != -1) return ret; // Increase id.. [알고스팟] Jump Game - 동적 계획, 메모이제이션 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 점프 게임(링크) 게임판의 각 지점에 적힌 숫자대로 오른쪽 또는 아래로 이동할 수 있으므로 대략 2^(격자 개수) 가지의 경우의 수가 있다.최대 100 x 100개의 칸이 있으므로 모든 칸에서의 도달 가능 여부를 검사하기는 무리다. 그런데 어떤 지점들은 여러 경로로 도달할 수 있다. 즉, 중복으로 계산되는 경로가 있으므로 한번 계산한 경로는 저장하고 필요할 때 꺼내서 사용한다. #include #include using namespace std; // Initial state: -1, NO: 0, YES: 1 int cache[100][100]; int jumpGame(vector board, int y, int x) { int goal = .. 이전 1 2 다음