백준36 [C] 9095: 1, 2, 3 더하기 이 문제 역시 Dynamic Programming을 이용한 문제이다. Dynamic Programming의 특징은 첫째로 문제를 작게 나누어 최대한 연산을 반복하지 않도록 하는 것이고 둘째로는 배열에 값을 저장하여 점화식을 이용하여 푸는 문제가 많은 것이다. 이 문제 역시 점화식만 잘 알 수 있었다면 쉽게 풀 수 있다. 예를 들어 4의 경우 4=1+3, 2+2, 1+3 이런식으로 표현할 수 있는데 1+3은 1+cpy[3], 2+2=2+cpy[2], 1+3=cpy[3] 으로 생각하면 4를 1,2,3으로 표현하는 모든 경우의 수를 표현할 수 있다. 이를 일반화 하면 cpy[i]=cpy[i-1]+cpy[i-2]+cpy[i-3]으로 표현할 수 있고 max를 구한 이유는 물론 이 문제는 10까지만 표현하면 되므로.. 2023. 7. 21. [C] 1463: 1로 만들기 맨 처음에는 아예 모든 배열에 미리 수를 찾는 과정으로 만들려고 했고 이때 아래 소스 코드와 같은 방법으로 구현하려고 했지만 시간초과가 떠서 실패하였다. #include #include int arr[2][1000001]; void memory(int arr[2][1000001],int n,int cnt) { if(n>1000000) return; if(arr[1][n*3]>cnt ||arr[1][n*3]==0) { arr[0][n*3]=cnt; arr[1][n*3]=cnt; memory(arr,n*3,cnt+1); } if(arr[1][n*2]>cnt || arr[1][n*2]==0) { arr[0][n*2]=cnt; arr[1][n*2]=cnt; memory(arr,n*2,cnt+1); } if(ar.. 2023. 7. 20. [C] 11047: 동전 0 이 문제는 Greedy 알고리즘을 이용해서 푸는 문제로 직관적인 생각으로 바로 문제를 풀 수 있다. #include #include int main(void) { int n,k; scanf("%d %d",&n,&k); int arr[n]; for(int i=0;i=0;j--) { if(k/arr[j]!=0) //나눠질 수 있음 { cnt+=k/arr[j]; k-=(k/arr[j])*arr[j]; //몫*동전 } } printf("%d",cnt); } 2023. 7. 18. [C] Quicksort 정렬하기 백준 2751번 수정렬하기 2번을 푸는데 quicksort를 이용하여 풀려고 했다. 근데 quicksort는 최악의 경우 시간복잡도가 n^2이기때문에 시간초과가 떴다... 다음번에는 mergesort를 이용하여 다시 풀어봐야겠다. 아래의 소스코드는 quicksort를 이용해 시간이 정해져있지 않을때 맞는 코드이다.. 또 공부해야한다니.. #include #include void swap(int *a, int *b) //포인터를 써야지 값이 함수를 넘어가도 유지가 됨 { int tmp; tmp=*a; *a=*b; *b=tmp; } void quicksort(int arr[],int left,int right) { if(left==right) //탈출 조건(원소가 하나일때) return; int pivot=.. 2023. 7. 16. 이전 1 ··· 3 4 5 6 7 8 9 다음