용's

가장 먼저 Pivot을 배열에서 하나 선택해서 Pivot을 기준으로 왼쪽에는 Pivot보다 작은 수가, 오른쪽에는 Pivot보다 큰 수가 정렬되도록 한다. 이를 위해 배열의 인덱스 0을 가르키는 Low(또는 Left)를 시작으로 인덱스를 하나씩 증가시키며 Pivot보다 큰 수를 찾는다. Left가 찾고 난 뒤, Right가 배열의 끝에서 점점 감소하며 Pivot보다 작은 수를 찾는다. 그러면 현재 Left는 Pivot보다 큰 수, Right는 Pivot보다 작은 수를 가르키고 있으므로 이 둘을 Swap한다. (위의 그림에서는 두 수를 모두 찾고 나서 swap하는 것이 아닌, 빈칸(Vac)이 생기는 곳에 곧바로 찾은 수를 넣고 있다. 예를 들면, Pivot으로 선택된 45가 있던 자리에 Vac이 생기고, ..

이전 포스팅에서는 Change Making 문제를 다뤘다. 이번 동적 프로그래밍 문제에서는 '주어진 동전의 종류를 이용하여 목표치(W)를 만드는 경우의 수 카운트' 문제를 풀어보도록 한다. 알고리즘을 단번에 생각해내기가 상당히 어렵다. 차근차근 이 문제를 접근해보자 예를 들어 설명하는 것이 가장 빠를 듯 하다. 1원 2원을 이용하여 4원(W)을 만드는 경우의 수는 몇 가지인가? 1+1+1+1 = 4 2+1+1 = 4 2+2 = 4 이렇게 총 3가지가 된다. 1원 2원을 이용하여 5원(W)을 만드는 경우의 수는 몇 가지인가? 1+1+1+1+1 = 5 2+1+1+1 = 5 2+2+1 = 5 이렇게 총 3가지가 된다. 자세히 보면, 1원으로 W를 만드는 경우의 수 + 2원을 이용하여 W를 만드는 경우의 수로 ..

change making problem [https://en.wikipedia.org/wiki/Change-making_problem] 위키피디아에서 알 수 있듯이 이 문제는, '주어진 동전의 종류를 조합하여 목표 금액을 만들고자 할 때, 최소의 동전 개수를 구하는 문제' 예를 들면, 다음 문제와 같다. '1원 5원 10원을 가지고 15원을 만들고자 할 때, 15원을 만드는 조합 중 최소의 동전 개수는?' Greedy한 방식으로도 풀 수 있지만 이 문제는 가장 기초적인 동적 프로그래밍(Dynamic Programming)로 해결할 수 있는 문제 중 하나이다. 아이디어는 다음과 같다. 1원이 포함된 n가지 동전으로 W원을 만들고자 할 때, W원을 만드는 최소의 동전 개수는 다음 두가지 경우의 수 중 최소값..

최소값(또는 최대값)을 찾아서 계속해서 앞쪽(또는 뒤쪽)으로 두는 정렬방식... 123456789101112131415161718192021222324 int main(){ int a[10] = { 5, 2, 3, 10, 1, 7, 9, 8, 6, 4 }; for (int i = 0; i

기본적인 아이디어는 인근의 두 수를 비교해서 정렬하는 것. 1234567891011121314151617181920int main(){ int a[10] = { 10, 2, 3, 5, 1, 7, 9, 8, 6, 4 }; for (int i = 0; i