모든답을 만들어 보고 그중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계합니다. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꿉니다. 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄입니다. 문제에 최적 부분 구조가 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수도 있습니다. 여기서 우리의 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것입니다. 입력의 종류가 줄어들면 줄어들 수록 더 많은 부분 문제가 중복되고, 따라서 메모이제이션을 최대한도로 활용할 수 있지요. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션할 수 있도록 합니다. 메모이제이션을 적용합니다.
Tail Call Recursion제가 이번에 설명할 것은 제가 검색하다가 발견한! Tail Call Recursion 이라는 새로운 재귀?적인 방법의 코딩입니다. 기존의 재귀함수와 비교하면서 설명하도록 하겠습니다.IDE : Visual Studio 2017언어 : C++ 1. 기존의 재귀함수먼저 기존의 재귀함수를 보도록합니다. 여기서는 가장 대표적인 피보나치 수열을 이용한 재귀함수를 살펴보겠습니다. 뭐.. 설명할 것이 많이 없네요. f라는 함수는 피보나치 수열의 n번째 항을 값으로 리턴해주는 함수입니다. 0번째 항은 0으로 정의 하겠습니다. f(4)를 호출하게 되면 피보나치수열의 4번째 값인 '3'이 잘 출력되는 프로그램입니다. 여기서! f(4)가 호출되었을 때, 일어나는 과정을 살펴보면.f(4) 호출..
1. 선택정렬 (1) 배열에서 가장 작은 값을 선택한다.(오름차순인 경우)(2) 배열맨 앞원소와 swap하면서 채워나간다. 12345678910111213#define swap(x, y, t) ((t) = (x), (x) = (y), (y) = (t))void selectionSort(int list[], int n) { int temp; for (int i = 0; i 0; gap >>= 1) { if (not (gap & 1)) { gap++; } for (int i = 0; i 1); int* left = mergeSort(arr, from, mid); int* right = mergeSort(arr, mid, to); int* merge = (int*)malloc(sizeof(int) * (to ..
https://www.acmicpc.net/problem/14953 백준 14953번 Game Map 문제입니다. dfs로 탐색하고 dp배열에 최대로 갈 수 있는 노드의 합을 저장해 놓습니다. 한번 계산한 최대값은 변하지 않으므로 다른 노드에서 계산할 때 이용합니다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include using namespace std; int dfs(vector& graph, vector& neighbor, vector& dp, int cur) { if (dp[cur]) return dp[cur];//이미 계산한 경우예요 int cnt = 1;//나 자신 for ..
https://www.acmicpc.net/problem/3653 백준 3653번 영화 수집문제입니다. 세그먼트 트리를 활용해서 트리에 선택한 DVD위에 놓여있는 DVD의 갯수를 합으로 저장해 놓습니다. DVD를 뽑았다면 맨위에 두는 것을 업데이트 해가면서 문제를 풀면됩니다. 배열을 n+m(DVD갯수 + 옮길 DVD갯수)로 만들고 세그먼트트리도 같은 갯수로 만듭니다. 각 DVD의 위치를 저장해놓을 배열도 만듭니다. 각DVD의 값을 1로하는 세그먼트 트리를 만듭니다. DVD를 뽑을 때마다 세그먼트트리의 값을 갱신합니다. 참고한 블로그 (https://lyzqm.blogspot.com/2017/07/segment-tree-3653.html) (http://jaimemin.tistory.com/712) 123..