해나의 컴공생존기

1. 동전 거스름 돈 N원의 거스름 돈을 돌려줄 때, 최소 개수의 동전을 사용하여 거스름 돈을 돌려주는 방법을 구해보자. 1.1 idea 8월을 거슬러준다고 가정해보면 아래 경우중 하나가 일어날 것이다. 동전은 1원, 4원, 6원짜리가 있다고 가정해보자. 1원 동전 한개 + 7원 최적해 4월 동전 한개 + 4원 최적해 6원 동전 한개 + 2원 최적해 위처럼 작은 사건으로 나눌 수 있다. 식으로 나타내면 아래와 같다. C(i, j)를 크기 Di 동전으로 j원을 거슬러 줄 때의 동전 개수라고 가정하자. C(i, j-Di) + 1 : Di 원을 거슬러 준 경우 동전 하나 추가 C(i-1, j) :거슬러 주지 않고 다음 돈으로 스킵(i원짜리 동전이 없을 때,1원 내기) 2. 바둑 돌 가져가기 완전 정보 게임 :..

1. 문제정의 모든 노드 쌍들마다의 최단경로 구하기 (path까지는 어렵기 때문에 길이만 구할 것이다) undirect 그래프라고 가정. 가장 쉬운방법은 다익스트라 알고리즘을 n번 돌리는 것이다. 2. Floyd Warshall Alg 각 노드별로 번호를 부여했다고 가정하자. i → j로 가는 최단경로를 구할 건데, {1, 2, ..., k}번 노드 중에서만 거쳐가는 최단 경로를 찾으면 된다. 이 과정을 k가 0부터 N까지 반복한다. (k가 n일 때가 최종 답이된다,) 즉, 구하고자 하는 것은 모든 (i, j) 쌍에 대하여 1번부터 k번 노드 중에서만 거쳐서 갈 수 있는 최단경로이다. k=0이라면 {공집합}이고 i와 j를 연결하는 것은 direct edge밖에 없다. direct edge가 없다면 답은 ..

정의해준 재귀함수를 분석해보겠다. 인자로 a,b,c 가 들어오고 이 값에 따라 재귀호출을 하는 것 같다. a,b,c 중 하나라도 0이하가 되면 1을 리턴한다. a,b,c 중 하나라도 20이상이 되면 a,b,c에 20을 넣고 재귀호출한다. a> b >> c; if (a == -1&&b==-1&&c==-1) break; //종료조건 cout

알고리즘시간에 배운 동적프로그래밍 문제를 하나 가져와봤다. 의사코드를 한번 보면 재귀호출은 들어온 숫자(n)이 1이나 2가 아니라면 n-1과 n-2를 인자로 재귀호출하여 더해준다. 만약 6이 들어온다면 f(6) → f(5) + f(4) → ( f(4)+f(3) ) + ( f(3)+f(2) ) → ( ( f(3)+f(2) ) + ( f(2)+f(1) ) ) + ( ( f(2)+f(1) )+1 ) → ( ( ( f(2)+f(1) )+1 ) + ( 1+1 ) ) + ( (1+1 )+1 ) → ( ( ( 1+1 )+1 ) + 2 ) + 3 → 8 동적프로그래밍 의사코드를 보면 인자로 들어온 n만큼 배열을 만들어서 인덱스 1,2, 에는 1을 넣어주고 나머지 인덱스에는 앞에 두자리를 더한 값을 넣어준다. 하지만 '..