반응형 동적계획법11 [C/C++] 백준 #2718 타일 채우기(동적계획법) 경우의 수를 알아내라는 문제들 상당수는 동적계획법(Dynamic Programming)으로 해결할 수 있습니다.하지만 동적계획법을 사용하기 위해서는 문제를 올바르게 이해하는 것이 선행되어야 합니다. 2xn일 때에는 피보나치 수열과 비슷한 점화식을 얻을 수가 있습니다. 하지만 3xn, 4xn 과 같이 수가 늘어나면 조금 더 복잡한 점화식이 필요합니다. 일단 제가 모델링한 것은 조금 복잡합니다.이전값에 대해서 4개값까지 참고를 하니까요. 문제는 다음 링크와 같습니다.https://www.acmicpc.net/problem/2718 프로그램 설명: 1. 함수 solve(int n) • 이 함수는 주어진 n 크기의 바닥을 채우는 방법의 수를 계산하고 출력합니다. • 이 문제에서는 특이한 점이 있는데, 점화.. 2024. 8. 10. [C/C++] 백준 #2698 인접한 비트의 개수(동적 계획법) 동적 계획법(Dynamic Programming)으로 문제를 풀기 위해서는, 해당 문제에 대한 모델링을 해주어야 합니다. 모델링(modeling)을 할 때에는 N의 문제를 그보다 크기가 작은 N-1이나 N/2의 문제 등 보다 작은 형태로 나누어 주어야 하죠. 보통 N-1 문제로 표현할 수 있는 경우에는 시간 복잡도가 \(O(N)\)이 되며, N/2 문제로 표현할 수 있는 문제는 \(O(\log N)\) 또는 \(O(N \log N)\) 문제로 표현될 수 있습니다. 예를 들어서 피보나치 수열의 경우에는 N의 문제를 N-1 문제와 N-2 문제로 해결하며, 이 것을 그대로 적용하면 \(O(N)\)이 되며, 보다 적극적인 방법으로 이분 탐색을 진행한다면, \(O(\log N)\) 복잡도로 해결할 수 있습.. 2024. 8. 9. [C/C++] 백준 #2624 동전 바꿔주기(동적계획법) 동전 바꿔주기 문제는 여러 종류의 동전을 가지고 원하는 액수의 금액을 맞추어주는 경우의 수 문제입니다.실생활에서는 크게 도움이 되지 않겠지만, 동적계획법을 이용한 알고리즘 문제로는 매우 유명합니다. 동적계획법을 사용할 때에는 보통 다차원 배열을 이용하게 되는데, 다차원 배열 대신에 맵(map) 또는 딕셔너리(dictionary) 자료를 이용해서도 문제를 풀 수 있습니다. 중간에 생기는 상태값의 갯수에 비해서 키(key)의 범위가 매우 큰 경우에는 다차원 배열보다는 맵 자료형을 사용하는 것이 좋습니다. 이것은 대략적인 감에 의존할 수밖에 없습니다. 다차원 배열이나 정렬되지 않은 맵(unordered map) 모두 \(O(1)\) 검색 알고리즘이지만, 정렬되지 않은 맵을 처리하기 위해서는 오버로드가 .. 2024. 5. 10. [C/C++] 백준 #2225 합분해(동적 계획법) #2225 합분해 문제는 경우의 수를 찾는 문제입니다. 경우의 수를 찾는 문제들의 특성은 동적 계획법하고 상당히 잘 맞습니다. 문제는 동적 계획법을 어떻게 구성할 것인가죠. 그리고 꽤 많은 경우 간단하게 한번에 계산할 수 있는 경우의 수를 찾을 수도 있습니다. 물론 그것이 계승(factorial) 형태로 나오면 큰 의미도 없습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 요구사항은 간단합니다. 0부터 N까지의 수중에 K개를 뽑아서 합이 N을 만드는 경우의 수입니다. 중복된 수도 허용하고, 더하는 순서가 다르면 서로 다른 경우로 봅니다... 2023. 4. 17. [C/C++] 백준 #2133 타일 채우기(동적 계획법) #2133 타일 채우기 문제는 동적 계획법을 이용해서 풀 수가 있습니다. 하지만 원리만 알면 조금 더 쉬운 방법으로도 해결할 수가 있습니다. https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제는 3xn 공간을 2x1 타일로 채우는 경우의 수를 구하라는 문제입니다. 아주 간단하지만 n이 홀수인 경우에는 채울 수 있는 방법이 없습니다. n이 짝수인 경우에만 채울 수 있는 경우가 발생하죠. 저는 동적 프로그래밍을 하기 위해서 다음과 같은 경우를 생각했습니다. 마지막 칸에 나올 수 있는 패턴들입니다. 마지막 칸의 패턴은 아무것도 없는 상태, 맨 위에만 한칸 채.. 2023. 4. 8. [C/C++] 백준 #1563 개근상(동적계획법) 개근상 문제는 동적계획법을 이용하는 문제이지만, 조건이 조금 까다롭습니다. 연속결석이 3번 이어지면 안 되기 때문에 당연히 동적 계획법을 사용하는 것이 바람직합니다. 그런데 지각 정보도 있으니까요. 출석은 O, 결석은 A, 지각은 L로 표현했을 때, 5일간 출석 정보를 가지고 개근상을 따진다면, OOOOO와 같은 경우는 당연히 되겠죠. AALAL 과 같이 지각을 두번 이상한 경우에는 개근상을 받지 못합니다. AALAA와 같이 4번 결석에 1번 지각의 경우는 개근상을 받겠죠. https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 .. 2022. 9. 6. 이전 1 2 다음 728x90
