𝘚𝘭𝘰𝘸 𝘣𝘶𝘵 𝘴𝘵𝘦𝘢𝘥𝘺

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. DP를 이용하여 푸는 문제. 앞서 풀었던 타일링 문제들과 동일하게 생각하면 쉽게 풀 수 있다. 1, 2, 3만으로 숫자 n을 만들기 위한 경우의 수는 다음과 같다. 1. (n..

문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. DP를 이용하여 푸는 문제. 앞서 풀었던 11726번인 2xn 타일링을 조금만 응용하면 바로 풀 수 있다. 가로 한 칸을 1x2 타일로 채우는 방법 한 가지, 가로 두 칸을 2x1 타일을 위아래로 쌓아 채우는 방법 하나, 2x2 타일로 채우는 방법 하나인 점을 고려하여 점화식을 세우면 다음과 같다. D[n] = D[n - 1] + 2 * D[n - 2] 이 문제 역시 초기값 설정과 매 연산..

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. DP를 이용하여 풀 수 있는 문제. 규칙을 생각하면 위 사진과 같다. 타일을 배치할 때 마다 가로 한 칸을 1x2 타일로 배치할 수 있는 방법 하나, 가로 두 칸을 2x1 타일을 위아래로 두개 쌓아 배치할 수 있는 방법 하나가 있어 점화식을 세워보면 다음과 같은 식이 나온다. D[n] = D[n - 1] + D[n- 2] 맞다. 그냥 피보나치 수열 문제다. 초기값 설정과 매 연..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. DP를 이용하여 풀 수 있는 문제. 1. N이 3으로 나누어 떨어지면, 3으로 나눈다 ➡️ D[N] = D[N/3] + 1 2. N이 2로 나누어 떨어지면, 2로 나눈다 ➡️ D[N] = D[N/2] + 1 3. 1을 뺀다 ➡️ D[N] = D[N - 1] + 1 그러나 ..

'코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 를 참고하여 작성하였습니다. 1. 동적 계획법 ; dynamic programming 1.1 개념 분할 정복 패러다임 개념을 확장한 것으로, 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말이다. 언뜻 문제를 보면 비슷하다 생각될 수 있지만, 분할 정복과 구분되는 동적 계획법만의 특성은 다음과 같다. 1. 중복되는 부분 문제(overlapping subproblem) 2. 최적 부분 구조(optimal substructure) 다음과 같은 속성을 만족해야 동적 계획법을 통해 문제를 해결할 수 있다. 전체 문제가 독립적인 부분 문제로 나뉘는 분할 정복 문제와 달리 동적 계획법에서는 중복되는 부분 문제가 반복적으로 등장한다. 또한 최적 부분 구..