본문 바로가기

동적 계획법34

[백준] 2631번 - 줄세우기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 줄세우기 -> https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 이미 정렬되어 있는 아이들 제외하고 정렬되지 않는 아이들을 옮긴다. 이때 옮겨지는 아이의 최소 수를 구해야 되므로 정렬되어 있는 아이들의 최대 수(Lis)를 구하여 전체 아이들의 수(n)에서 빼준다. C++ 소스코드) 2021. 9. 3.
[백준] 2186번 - 문자판 (C++) 문제 및 풀이 문졔) 백준 - 동적 계획법 (Dynamic Programming) - 문자판 -> https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net F(x, y, index): 점 (x, y)에서 index이후의 부분 문자열을 만들 수 있는 경로의 개수 점화식을 다음과 같이 설정 후, 모든 문자판을 순회하면서 F(x, y, index)의 값을 더한다. C++ 소스코드) 2021. 7. 27.
[백준] 1563번 - 개근상 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법(Dynamic Programming) - 개근상 -> https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net cache[ i ][ j ][ k ]를 길이가 i이고 지각(L)이 j번이면서 끝문자의 연속 결석 회수가 k번으로 정의한다. 가령, 'LOAA'는 cache[4][1][2]의 한 요소이고, 'OALAO'는 cache[5][1][0]의 한 요소이다. 결석은 세번 연속으로 하지 않는 이상 개근상에 영향을 주지 않기 때문에 끝에 연속된.. 2021. 7. 6.
[백준] 1351번 - 무한 수열 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법(Dynamic Programming) - 무한 수열 -> https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 친절(?)하게도 점화식이 주어졌다. N의 범위가 10^12까지이므로 배열로 memoization 하는 것은 불가능하다. 또한 N이 P와 Q로 계속 나누어지기 때문에 10^12까지 인덱싱 하는 것은 비효율적이다. 따라서 map을 이용하여 memoization을 통해 기존 Top-down 방식의 Dp를 구현했다. C++ 소스코드) 2021. 7. 6.
[백준] 2579번 - 계단 오르기(C++/파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 계단 오르기 -> www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net Python 코드는 바텀업(Bottom-Up), C++코드는 탑다운(Top-Down)으로 구현했다. C++ 소스 코드) Python 소스 코드) 2021. 4. 9.
[백준] 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.
반응형

티스토리툴바