목록동적계획법1 (12)
궤도
문제 풀이 동적계획법의 대표적인 문제 중 하나이다. 생각해보니 동적계획법은 대표하는 문제가 많은 것 같다...아무튼 이전까지의 문제들은 초기값을 받은 배열을 그대로 갱신하면서 값을 구했다. 하지만 이 문제는 그러면 안된다. i번째 계단을 밟는다고 생각하자. i번째 계단을 밟기 위해선 어떤 경로로 계단을 밟아야 했을까? i-3번째 계단을 밟고 i-1번째 계단을 밟은 뒤 i번째 계단을 밟거나(3번연속 계단을 밟을 수 없기 때문) i-2번째 계단을 밟고 i-1번째 계단을 건너뛰고 i번째 계단을 밟을 수 있을 것이다. 배열을 1개만 사용하면 안되는 이유가 이것이다. i번째의 계산을 할 때 i-1번째만 연속적으로 참조하던 지난 문제들과 달리 이건 불연속적으로? 지난 값들을 참고하기 때문에 초기 입력을 저장할 배열..
문제 풀이 이 문제도 동적계획법의 대표적인 문제 중 하나이다. 대표적인 풀이법에는 위에서 아래로 내려가는 방법과 아래에서 위로 올라가는 방법이 있는데, 후자가 훨씬 코드를 간단하게 짤 수 있다. i번째 줄을 계산한다고 하자. i번째 줄의 0번째(지금은 3)를 갱신하려면 i+1번째 줄의 0번째(7)와 더하거나 i+1번째 줄의 1번째(6)와 더하거나 이다. 둘 중 더 큰 값을 취하면 된다. 일반화하면 i번째 줄의 j번째 값을 갱신하려면 i+1번째 줄의 j번째 값과 i+1번째 줄의 j+1번째 값을 비교해 더 큰 값과 더하면 되는 것이다. 이를 n-1번째줄부터 1번째 줄까지 반복한 뒤 1번째 줄의 1번째 값을 리턴하면 된다. 소스코드 #include #include using namespace std; int ..
문제 풀이 이걸 이렇게 표현하는게 맞나? 싶지만 동적계획법 문제를 풀 때는 i번째가 ~라면 i-1번째는 뭐였을까? 라는 방법으로 접근하는 것이 좋다. 보통 문제를 풀 때 0번째가 이거라면 1번째는 이게 되고 2번째는...식으로 생각하기 마련인데 동적계획법은 반대 방향으로 가야한다. 이 문제도 마찬가지이다. 첫번째 두번째 집이 무슨 색인지는 궁금하지 않고, i번째 집을 빨간색으로 칠한다고 생각해보자. i번째 집이 빨간색이라면 i-1번째 집은 파란색(1번 경우)이나 초록색(2번 경우)일 것이다. 그렇다면 i번째 집을 빨간색으로 칠할 때의 최솟값은? 1번 경우와 2번 경우 중 더 작은 값을 택하면 될 것이다. 소스코드 #include #include using namespace std; int house[10..
문제 풀이 동적계획법의 입문(?) 문제이다. 정확히 말하자면 찐 입문은 재귀 함수로 구현된 피보나치 함수를 동적계획법으로 구현하는 것인데...거의 같은 구조이다. n>1 일 때 fib(n) = fib(n-1) + fib(n-2)이다. 그렇다면 fib(n)에서 0이 호출된 횟수는? 당연히 fib(n-1)에서 0을 호출한 횟수와 fib(n-2)에서 0을 호출한 횟수를 더한 값일 것이다. 1이 호출된 횟수 역시 마찬가지일 것이고... 소스코드 #include using namespace std; void fibo_cnt(int num) { int zero_cnt[41] = { 0, }; int one_cnt[41] = { 0, }; for (int i = 0; i