본문 바로가기
반응형

dynamic programming20

[C/C++] 백준 #2293 동전 1(동적 계획법) 동전들을 가지고 만들 수 있는 돈의 액수의 경우의 수는 동적 계획법을 이용하는 대표적 문제 중 하나입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 주어진 K원을 만들기 위해서는 동전의 종류를 먼저 조절해야 합니다. 서로 다른 동전의 종류가 n개가 있다면, 우리는 동적 계획법의 변수 \(d_{n, k}\)를 정의하도록 합니다. n개의 동전을 가지고 k 금액을 만드는 경우의 수로 정의토록 합니다. 이렇게 하면 다음과 갈은.. 2023. 4. 20.
[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++] 백준 #2169 로봇 조종하기(동적 계획법) #2169 문제는 동적 계획법을 이용했지만, 일반적인 동적 계획법은 한방향으로만 진행되는 경우에 주로 사용됩니다. 이 문제에서는 한곳의 값을 결정하기 위해서는 왼쪽, 오른쪽, 그리고 위라는 3군데 방향을 고려해야 하므로 좀 까다롭습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 문제는 나사(NASA)의 로봇이 화성을 돌아다닐때, 최대한의 가치를 얻으면서 지역을 탐사하는 것입니다. 처음에 어떻게 짜야할까 고민하.. 2023. 4. 12.
[C/C++] 백준 #2156 포도주 시식(탐욕 알고리즘) 이번 문제는 탐욕 알고리즘의 범주로 놓아야할 것 같아서, 탐욕 알고리즘이라고 적기는 했지만, 문제에서 추천하는 알고리즘은 동적 계획법입니다. 동적 계획법이 더 맞을 수도 있겠죠. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 제가 생각한 알고리즘은 다음과 같습니다. \(fc_0\)은 현재 와인을 선택하지 않았을 때, 최대값입니다. \(fc_1\)은 이전 와인은 선택하지 않았지만, 현재 와인은 선택한 경우입니다. .. 2023. 4. 10.
[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++] 백준 #2096 내려가기(동적 계획법) 내려가기 문제는 간단한 형태의 동적 계획법(Dynamic Programming)을 사용하면 됩니다. 동적 계획법을 사용하지 않고, DFS나 BFS를 이용해서 풀 수는 있지만, 그렇게 하면 시간이 많이 걸립니다. 다익스트라 알고리즘을 사용해도 동적 계획법을 적용한 것과 같은 효과를 낼 수 있습니다. https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 처음에는 설명을 이해하기 어려웠습니다. 주어진 N이 주어지면, 3xN 형태의 공간이 발생합니다. 맨 위층에서는 3칸.. 2023. 3. 30.
728x90

티스토리툴바