본문 바로가기

dynamic programming7

[백준] 11726번 - 2xn 타일링 (파이썬/C++) 문제 및 풀이 문제) 백준 - 동적 계획법(Dynamic Programming) - 2xn 타일링 -> www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 점화식을 다음과 같이 작성할 수 있다. f(n) = f(n - 1) + f(n - 2) 파이썬 소스 코드는 위 점화식을 이용해서 작성했고, C++에서는 기저 사례(n = 1, n =2)의 설정과 재귀를 통해 답을 계산한다. 파이썬 소스코드) C++ 소스코드) 2021. 3. 30.
[백준] 9251번 - LCS (파이썬) 문제) 백준 - 동적 계획법 (Dynamic Programming) - LCS -> www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net dp를 해당 문자 이전까지 만들 수 있는 LCS라 하자. dp를 업데이트 해가며 만약 문자열이 같을 경우(string1[i] == strring2[j]), 이전 LCS의 길이(dp[i - 1][j - 1])에 1을 더해준다. 문자가 같지 않을 경우, 이전에 만든 LCS중 최대값을 그대.. 2021. 3. 29.
[백준] 12865번 - 평범한 배낭 (파이썬, C++) 문제) 백준 - 동적 계획법 (Dynamic Programming) - 평범한 배낭 -> www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1 2 3 4 5 6 7 ( 6, 13 ) 0 0 0 0 0 13 13 ( 4, 8 ) 0 0 0 8 8 13 13 ( 3, 6 ) 0 0 6 8 8 13 14 ( 5, 12 ) 0 0 0 0 12 13 14 (물건 무게, 가치)가 (3, 4)인 경우를 주목.. 2021. 3. 11.
[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic programming) - 가장 긴 바이토닉 부분 수열 -> www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net (백준 - 11053번)가장 긴 증가하는 부분 수열 문제와 (백준 - 11722번) 가장 긴 감소하는 부분 수열 문제를 합치면 풀 수 있다. 가장 긴 증가하는 부분 수열의 아이디어를 채택해 우리는 1~n까지 탐색( i )하면서 그 이전까지 i번째 숫자보다 작으면서도 가장 긴 증가하는 부분 수열의 길이를 저장한다. 가장 긴 증가.. 2021. 3. 9.
[백준] 11722번 - 가장 긴 감소하는 부분 수열 (C++, 파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 가장 긴 감소하는 부분 수열 -> www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 참고) 2021.03.02 - [Algorithm_note/틀린 문제] - [백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬) [백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬) 문제) 백준 - 동적 계획법 .. 2021. 3. 9.
[백준] 1890번 - 점프 (파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 점프 -> www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 오른쪽이나 아래로 점프가 가능한 경우 dp 리스트에 +1 해준다. (0, 0)부터 시작해 (n - 1, n - 1)까지 재귀로 완전 탐색하며 (n - 1, n - 1)일 때 기저 사례를 처리해 1을 반환한다. 소스 코드) import sys sys.setrecursionlimit(1000000) input = sys.s.. 2021. 3. 9.
[백준] 1520번 - 내리막 길 (C++, 파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 내리막 길 -> www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 각 지점까지 이동할 수 있는 경로의 수를 저장한 2차원 리스트(dist)에 메모이제이션을 적용한다. dist 리스트의 초기값을 -1로 선언해 방문 여부를 판단한다. 각 지점까지 이동할 수 있는 경우의 수는 dfs를 이용하여 경로가 겹치는 지점에서 서로의 경로 수를 합친다. Python 소스 코드) C++ 소스 코드) Python .. 2021. 3. 9.
반응형

티스토리툴바