코딩스타트

1. 다이나믹 프로그래밍 - 동전1 (백준 2293번)

2. 다이나믹 프로그래밍을 이용한 문제풀이

이 문제를 예를 들어 설명한다면, dp메소드에서 반복문에 들어가게 되면 우선 memo[0]=1 이라고 초기화를 한다. 이 것은 동전을 아무 것도 선택하지 않는 경우를 한 경우로 보고 1로 초기화하는 것이다.(확률에서 선택하지 않는 것도 하나를 1로 생각하는 것과 같다 보면된다.) 그리고 반복문을 들어가게 된다. 여기서 i=0 일때를 보면 j-coin[i]>=0 에서 j=1부터 성립을 하게 된다. 그래서 memo[1]=memo[1]+memo[0] 에서 memo[1]=1 이 되게 된다. 여기서는 coin[1]이 1이므로 k+1까지 모두 1가지 경우로 값이 대입되게 된다. 하지만 2,3 혹은 어느 값이 들어오더라도 그 값의 배수에만 경우의 수 1이 들어가게 된다. 예를 들어 coin[1]=2일때 j가 2부터 j-coin[i]>=0 이 성립하고 memo[j]=memo[j]+memo[j-coin[i]] 값은 2의 배수인 경우에만 1 값이 들어오게 된다. 여기서 보면 특이한 것이 coin[1]=2 이고 j=2면 memo[j-2=0] 의 경우를 더해주고 j=4 이면 memo[j-2=2]의 경우의 수를 더해주고 규칙이 보일 것이다. 그럼 문제의 조건으로 돌아와서 coin[2]일때를 보면 j=2 일경우부터 조건문이 성립하고 memo[2]=memo[2]+memo[2-2] 이 된다. 이 말은 1과 2를 이용해 2를 만드는 경우의 수는 1->2개(1을 2개이용) , 1->0 && 2->1(2를 1개이용) 두가지의 경우의 수가 나온다. 여기서 1->2는 i=0일때 1로 2를 만들수 있는 경우의 수(이전 경우의수,이값은 빨간색으로) 1->0 && 2->1은 1을 0개 선택하고 2를 하나 선택한 경우(파란색)이다. 이 경우의 수를 색으로 표현한다면 

memo[2]=memo[2]+memo[0] 이 된다. 여기서의 이해가 중요하다. 앞의 memo[2]는 현재의 동전이 아니라 이전의 동전으로 2를 만들수 있는 방법, memo[0]은 2라는 동전을 하나 선택해서 2라는 값을 만들었으므로 이전의 동전으로 0이라는 값을 만드는 경우의 수를 더하는 것이다. 그러면 더 나아가서 memo[6]=memo[6]+memo[4] 라는 값을 보자 앞의 memo[6]은 이전까지의 동전들로 6을 만드는 경우이다. 즉, 1 1 1 1 1 1, 그리고 나머지 경우를 보게되면 1 1 1 1 2, 1 1 2 2, 2 2 2 라는 경우가 남아있다. 여기서 맨위 2를 빼면 1 1 1 1, 1 1 2, 2 2라는 경우는 어느 경우인가? 2까지의 동전을 사용해 memo[4]를 만든 경우가 된다. 이런식으로 마지막 동전까지 반복을 하게 된다.

1.다이나믹 프로그래밍 - 다리 놓기 (백준 1010번)

2.다이나믹 프로그래밍 & 조합을 이용한 문제풀이

1)조합을 이용한 문제풀이

첫번째 풀이는 조합을 이용한 풀이입니다. 예제 입력에서 29개의 다리 중에서 13개의 다리를 겹치지 않고 놓을 경우의 수는 67863913개입니다. 겹치지 않는다? 단순히 그냥 29개의 다리중에 13개의 다리를 뽑는 경우의 수를 구하면 됩니다. 굳이 겹치는 경우를 고려하지 않아도 되는 것입니다. 13C29(13콤비네이션29) 의 값을 구해주는 로직만 짜주면 답은 쉽게 나오게 됩니다.

2)DP를 이용한 풀이

예를 들어 서쪽에는 3개의 사이트 동쪽에는 5개의 사이트가 있다고 가정한다면 bridge(3,5) 메소드를 호출하게 된다. 여기서 반복문이 뜻하는 바는 i==4부터 i==2까지 값을 감소시키며 bridge 함수를 호출시키는 것이다. 이것은? i==4라면 서쪽의 첫번째 사이트가 동쪽의 1번 사이트와 다리가 연결되어 남은 2개의 서쪽사이트와 4개의 동쪽사이트로 연결할 수 있는 다리의 경우를 구하면 되는 것이고, i==3이면 서쪽의 1번 사이트가 동쪽의 2번사이트와 연결되어 남은 2개의 서쪽사이트와 동쪽의 2번 밑의 3,4,5 3개의 사이트와 연결될 경우의 수를 구한다. 이렇게 쭉쭉가다가 서쪽과 동쪽의 남은 사이트 수가 같을 때까지 반복한다. 이런 것이 서쪽 사이트가 하나씩 줄어 가며 반복되는 것이다. 그리고 마지막 서쪽사이트가 함수에 들어 오게 된다면 초기화된 값을 바탕으로 memo[n][m]의 값을 구하게 되는 것이다. 

1.다이나믹 프로그래밍 - 계단 오르기 (백준 2579번)

2.다이나믹 프로그래밍을 이용한 풀이

이 문제 풀이의 핵심은 각 계단을 마지막 계단으로 보는 것입니다. 예를 들어 가장 마지막 계단을 오르는 경우의 수는 이전 계단을 밟는 경우와 전전계단을 밟는 경우 총 2가지입니다. 여기에서 이전 계단을 밟는 경우에서 upStair(n-3) 재귀호출까지 더해주는 이유는 3번 연속된 계단을 밟을 수 없기 때문입니다. 이 두가지 경우 중에서 큰수를 Math 클래스의 max 메소드를 이용해서 구합니다. 그래서 이 두가지의 경우로 재귀호출을 통해 다시 함수에 들어가게 되면 그 계단을 다시 마지막 계단으로 보고 다시 위의 두 가지 경우로 나뉘어서 재귀 호출을 반복하게 됩니다. 이 과정을 반복하다가 초기화된 값까지 다다르게 되면 모든 값이 메모된 값을 이용하여 총합을 구할 수 있게 됩니다. 여기에서 2번째 계단을 밟은 가장 큰 경우의 수는 1번째 계단을 밟는 경우이므로 stairArr[1]+stairArr[2] 를 통해 초기화를 해줍니다.

1. 다이나믹프로그래밍- 2xn타일링(백준 11726번)

2. 다이나믹프로그래밍을 이용한 풀이

다이나믹 프로그래밍으로 풀기 전에 이 문제의 점화식을 먼저 구해보면 간단히 n=2,n=3,n=4 만 비교해보면 n=2는 2가지 n=3일떄는 3가지 n=4 일때는 5가지라는 경우의 수가 나온다. 즉, 이 문제의 점화식은 2x4=2x3 + 2x2 라는 점화식이 나온다. ->memo[n]=( tiling(n-1)+tiling(n-2) )%10007 하지만 문제의 전제에서 값에 10007의 나머지 값을 구하므로 % 10007을 해준다.(마지막에 결과에만 하는 것이 아니라 모든 경우에 % 10007이 적용되어야 한다.) 여기서 n-2 라는 수가 있다는 것을 주목하면 2번째 전까지의 수의 배열을 확인한다. 즉, 0과 1 두가지의 수를 초기화 시켜놔야 한다. 그래야 tiling(2)를 호출할때 tiling(1)+tiling(0) 을 호출했을때 배열의 있는 값을 이용해 이후의 값을 구할 수 있다.

1. 다이나믹프로그래밍(dynamic programming) 초콜릿 자르기(백준 2163번)

2. 다이나믹프로그래밍을 이용한 문제풀이

이 문제의 예를 들면 초콜릿이 (1,N) 모양이라면 이 초콜릿을 자를 수 있는 최소한의 수는 N-1 이라는 경우의 수가 나온다. 즉, 1,N(1<=N<=300) 의 초콜릿의 자를 수 있는 최소한의 수를 초기값으로 memo 배열에 넣어준다. (다이나믹 프로그래밍은 큰 문제를 잘게 쪼개가다가 맨 마지막 가장 작은 문제의 값을 이용하여 인접한 배열에 수를 채워가 마지막 결과값을 구하는 것이다.) 만약 초콜릿이 (3,4) 라면 cutting(3,4) 라는 함수에 들어간다.(이전에 memo배열을 초기화해주는 함수를 실행시켜준다.) 그러면 이 함수는 memo[3][3]=cutting(2,3)+memo[1][3]+1 가 된다. 이 뜻은 (3,3) 초콜렛을 (2,3)과 (1,3) 으로 쪼개주는 것이다. 여기에서 (2,3) 과 (1,3) 을 쪼개는 경우의 수 1을 더해주는 것이다. 그다음 (2,3) 은 앞의 N값이 2 이므로 한번더 쪼개기 위해 재귀호출을 한다. 하지만 (1,3) 은 이미 위의 memo배열에 초기화를 시켜줬으므로 재귀호출이 아니라 바로 값을 리턴해주는 것이다.(초기화 값을 이용해 재귀호출을 하는 것이 아니라 바로 결과값을 구할수 있다. 그러므로 불필요한 계산을 중복으로 하지 않는다.) 이런식으로 N값이 1이 될때까지 재귀호출을 반복하면 결과적으로 memo(3,3)에 결과값이 들어가게 되고 그 값을 리턴하게 된다.