동적계획법

🗂️ 문제링크: https://www.acmicpc.net/problem/11051  💡 접근법이항 계수란 그냥 조합이다. 즉, (5, 2)란 5C2를 구하는 것이다.이항계수의 성질을 이용하여 동적계획법으로 문제를 풀었으며, 이항계수의 성질은 다음과 같다. nCk = nCn-knCk = n-1Ck + n-1Ck-1파스칼의 삼각형을 본다면 더 쉽게 이해가 가능할 것이다.  위 두 성질을 기반으로 세운 DP 점화식은 다음과 같다.dp[i][k] = dp[i-1][k] + dp[i-1][k-1] (i≥1, k≥1) 추가적으로 코드에서는 1번 성질을 이용해서 for문의 반복횟수를 줄일 수 있다.예시로, 5C2 == 5C3이므로 5//2까지만 순회한다면 5에 대한 모든 조합의 경우를 구할 수 있다.5C0 ==..

🗂️ 문제링크: https://www.acmicpc.net/problem/11726 💡 접근법n=1일 때 직사각형을 채우는 방법은 1가지다.n=2일 때 직사각형을 채우는 방법은 2가지다.n=3일 때 직사각형을 채우는 방법은 3가지다.n=4일 때 직사각형을 채우는 방법은 5가지다.n=5일 때 직사각형을 채우는 방법은 8가지다. 이를 점화식으로 나타내면 dp[i] = dp[i-1] + dp[i-2] (N>2)이다. 😎 내 코드import sysn = int(sys.stdin.readline())dp = [0] * 1001dp[1] = 1dp[2] = 2for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2]print(dp[n]%10007) ✅ 정답 확인

🗂️ 문제 링크: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 💡 접근법 1을 만드는 방법은 1가지이고, 2를 만드는 방법은 (1+1), (2)로 2가지이고, 3을 만드는 방법은 (1+1+1), (2+1)*2, (3)으로 4가지이고, 4를 만드는 방법은 (1+1+1+1), (1+1+2)*3, (1+3)*2, (2+2)로 7가지이고, 5를 만드는 방법은 (1+1+1+1+1), (1+1+1+2)*4, (1+2+2)*3, (3+1+1)*3, (3+2)*2로 13가지이다. 이를 점화식으로 나타내면 dp[i] = dp[i-1] + dp[i-2] +..

🗂️ 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 접근법 triangle[i][j]에 도달하는 방법은 두 가지 방법이 있다. 대각선 왼쪽에서 내려오는 경우에는 dp[i][j] = dp[i-1][j-1] + t 이다. 대각선 오른쪽에서 내려오는 경우에는 dp[i][j] = dp[i-1][j] + t 이다. 또한 인덱스가 0일 때(맨 왼쪽)는 오른쪽에서 내려오는 경우밖에 없고, -1일 때(맨 오른쪽)는 왼쪽에서 내려오는 경우밖에..

🗂️ 문제 링크: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 💡 접근법 계단을 어떻게 올라갈까?가 아니라 계단을 어떻게 올라왔을까? 라는 관점에서 접근해야 한다. n번째 계단에 올라오기 위해서는 두 가지 경우가 있다. n-1번째 계단으로 오는 경우와 n-2번째 계단으로 오는 경우이다. n-1번째 계단으로 오는 경우에는 dp[n] = dp[n-3] + stairs[n-1] + stairs[n] 이다. n-2번째 계단으로 오는 경우에는 dp[n] = dp..

🗂️ 문제 링크: https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 💡 접근법 DP로 풀 수 있는지 먼저 확인한다. 부분 문제가 반복적으로 나타나야 한다. 부분 문제의 최적 결과를 사용하여 전체 문제의 최적 결과를 낼 수 있다. DP 테이블을 초기화한다. 조건에 맞는 점화식을 구한다. 😎 내 코드 import sys def fib_recur(n): global recur_cnt if n == 1 or n == 2: recur_cnt..