코딩 일기장

input: n (동전의 종류), k (만들어야 하는 동전 가치의 합) 각각의 동전의 가치 입력 output: 만들 수 있는 경우의 수 예제) 주요 해결 알고리즘: Dynamic Programming 예제의 경우를 가지고 생각해보자. i \ k 동전 0 1 2 3 4 5 6 7 8 9 10 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 2 2 3 3 4 4 5 5 6 3 5 1 1 2 2 3 4 5 6 7 8 10 한 줄씩 생각하면 쉽다. 이 표를 완전히 이해하는게 포인트다! k=0) k값이 0일때 의미하는 것은 , 0원으로 k원을 표현할 수 있는 방법을 의미한다. 0원으로는 나타낼 수 있는 방법이 없기 때문에 k=0을 제외하고는 모두 0이 들..

전형적인 divide-and-conquer 알고리즘이다. divide-and-conquer이란, 큰 문제를 작은 문제로 쪼개고 쪼개서, 작은 문제를 푼 후 결과를 병합하여 푸는 방법을 의미한다. #include #define max 6 //conquer void merge(int a[], int low, int mid, int high){ int b[1000]; // sort된 배열을 넣을 새로운 배열 int i=low, j=mid+1; //i는 왼쪽 배열의 시작, j는 오른쪽 배열의 시작 int k=0; //k는 새로 sorted된 array의 현재 위치 //한쪽이 다른 한쪽보다 완전히 작을때까지 while(i

insertion sort는 한 기준점을 중심으로 오른쪽에는 unsorted list, 왼쪽에는 sorted list가 있는 형식입니다. 오른쪽의 정렬되지 않은 element를 하나씩 왼쪽으로 옮기면서 부분적으로 리스트를 정렬하고, 결론적으로 기준점이 맨 끝에 갔을때 (오른쪽에 element가 없을 때) sorting이 완료됩니다. #include #include #define max 6 int main() { // sample input: 5 12 6 80 2 15 int key, now, temp; int A[] = { 5, 12, 6, 80, 2, 15}; printf("unsorted: "); for(int i=0 ; i key) { A[temp+1] = A[temp]; temp--; } A[te..