백준 | 9461 파도반 수열 Swift - DP

이전 게시글에서 다이나믹 프로그래밍을 맛볼 수 있었는데, 한 발짝 더 나아가서 효율적으로 풀 수 있는 방법을 고민하는 문제가 여기 있다. 이전 게시글 보러가기 ⬇️ 2023.07.18 - [공부하자!/알고리즘] - 백준 | 9095 1, 2, 3 더하기 Swift - DP 우선, 점화식을 구해보자! 문제에서 P(1)부터 P(10)까지 제공해주었다 1 2 3 4 5 6 7 8 9 10 1 1 1 2 2 3 4 5 7 9 그림에서 보면 알 수 있듯이, 11번째 삼각형의 한 변의 길이는 9+3, 즉 P(10)+P(6)인 12이다. 10번째 삼각형의 한 변의 길이는 P(9)+P(5)인 9이다. 즉 점화식을 구하면 다음과 같다 P(n) = P(n-1) + P(n-5) 하지만 이걸 그대로 코드로 구현하면 시간 초과..

• format_list_bulleted 공부하자!/알고리즘
• · 2023. 7. 18.
• textsms

백준 | 9095 1, 2, 3 더하기 Swift - DP

다이나믹 프로그래밍이란? 다이나믹 프로그래밍, 동적 계획법이라고 불리는 알고리즘은 하나의 커다란 문제를 작은 문제들로 나누어 값을 구하는 방법이다. 점화식을 구하고 나면 쉽게 풀 수 있지만 이런 사고방식에는 연습이 필요하다. 이 문제에서는 1, 2, 3만을 이용해 숫자를 나타낼 때, 그 경우의 수를 구해야 한다. 작은 것부터 차례대로 생각해보자. n = 1 1 1개 n = 2 1+1 2 2개 n = 3 1+1+1 1+2 2+1 3 4개 n = 4 1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 7개 n=1일 때는 1, n=2일 때는 2, n=3일 때는 4 그리고 n=4일 때는 7개의 경우의 수가 나온다. 이 때 n=4를 자세히 살펴보자. 1+3이라는 큰 틀을 구할 때, 오른쪽 피연산자..

• format_list_bulleted 공부하자!/알고리즘
• · 2023. 7. 18.
• textsms

백준 2579 계단오르기 파이썬 - 다이나믹 프로그래밍(DP), 동적 계획법

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 다이나믹 프로그래밍이라 점화식부터 정하고 풀기 시작했다. N번째 계단까지의 최댓값 = max( (N-1)번째 계단까지의 최댓값(단, (N-2)번째는 포함되지 않아야 함) + N번째 계단의 값, (N-2)번째 계단까지의 최댓값(단, (N-3)번째 포함 여부는 상관 없음) + N번째 계단의 값) 직전 값의 전 값도 중요하기 때문에 dp 리스트 요소를 (0, 0) 형태로 잡았다. 점화식: dp[N] = (dp..

• format_list_bulleted 공부하자!/알고리즘
• · 2022. 2. 26.
• textsms

백준 1463 1로 만들기 파이썬 - 다이나믹 프로그래밍(DP), 동적 계획법

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 (동적 계획법) 다이나믹 프로그래밍이란, 한 번 계산한 부분을 메모리에 저장해두어 일일이 다시 계산하지 않고, 필요할 때마다 불러오면서 계산을 빠르게 할 수 있는 알고리즘이다. 1로 만들기 점화식 dp[N] = min(dp[N-1], dp[N//2], dp[N//3]) + 1 # 1로 만들기 N = int(input()) dp = [0] * (N+4) dp[1] = 0 dp[2] = 1 dp[3] = 1 # 점화식 dp[N] = min(dp[N-1], dp[N//2], dp[N//3]) + ..

• format_list_bulleted 공부하자!/알고리즘
• · 2022. 2. 26.
• textsms