모든답을 만들어 보고 그중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계합니다. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꿉니다. 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄입니다. 문제에 최적 부분 구조가 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수도 있습니다. 여기서 우리의 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것입니다. 입력의 종류가 줄어들면 줄어들 수록 더 많은 부분 문제가 중복되고, 따라서 메모이제이션을 최대한도로 활용할 수 있지요. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션할 수 있도록 합니다. 메모이제이션을 적용합니다.
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 ..
안녕하세요. 이번에 연구해 볼 과제는 Quick Sort(퀵 정렬)입니다. 이 정렬은 현재 존재하는 정렬 알고리즘 중에서 평균적인 상황일 때 최고의 성능을 보입니다. 평균적으로 시간복잡도 O(n log n)이 걸리고 최악의 경우 시간복잡도 O(n^2)이 됩니다. 퀵 정렬은 배열에서 피벗(기준)을 잡은 후에 피번 기준으로 작은 값은 왼쪽(오름차순이라면 오른쪽)으로, 큰 값은 오른쪽으로 이동시킵니다. 같은 알고리즘으로 피벗기준으로 왼쪽배열과 오른쪽 배열을 정렬합니다(재귀적으로).그림 출처 : (https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98) 제가 퀵 정렬을 구현하면서 알게된 것들을 포스팅 하려고합니다..1234567..
DFS란 (Depth-First Search)라고 해요. 해석하자면 깊이를 우선해서 탐색한다?라고 할 수 있습니다. 무조건 한 우물만 판다는 얘기라고 생각할 수 있습니다. 천천히 한번 봐볼게요. 일단 이런 그래프가 있다고 가정하겠습니다. 모든 간선은 양방향입니다.이 그래프를 DFS를 적용해서 탐색하는 순서는 작은 숫자를 먼저 탐색한다 하면 결과는 (1->2->3->4->5->4->6->4->3->2->1)입니다.그림으로 순서를 보겠습니다.먼저 1에 방문합니다. 그다음 1은 방문했다고 체크해둡니다. 1에서 갈 수 있는 곳은 2와 5입니다. 작은 수 먼저 탐색하기로 하였으니 다음은 2로 이동합니다.2에 방문합니다. 2는 방문했다고 체크해두고, 2에서 갈 수 있는 곳은 1, 3, 4, 5인데요, 1은 아까 방..