본문 바로가기

동적계획법27

[Programmers] 연속 부분 수열 합의 개수 https://school.programmers.co.kr/learn/courses/30/lessons/131701 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 길이가 $n$인 원형 수열이 주어졌을 때, 각각의 요소에 대하여 길이가 1, 2, $\cdots, n$ 인 부분 수열의 합을 동적계획법(dynamic programming)을 활용해 구한 다음 중복되지 않는 합들의 갯수를 센다. 구현 중복되지 않는 부분 수열의 합들의 갯수를 세기 위해 std::unordered_set 클래스를 활용하였다. [스포 주의] 아래 '더보기'를 누.. 2023. 12. 31.
[Baekjoon] 1890번: 점프 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 문제 해결 과정 착안 가장 왼쪽 위의 칸에서 시작하여 이동할 때, 각 칸마다 오른쪽 또는 아래쪽으로 이동할 수 있는 두 가지의 경우가 있기 때문에 재귀를 통해 문제를 해결하면 문제에 따라 최대 지수 시간의 시간 복잡도($O(2^n)$)를 나타내게 될 수 있으므로, 이동할 수 있는 경우의 수를 누적하여 계산하는 동적계획법(dynamic programming)에 기반하여 문제를 해결하고자 .. 2023. 12. 21.
[Programmers] 등굣길 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 동적계획법(dynamic programming)을 활용해 문제를 해결하기 위해 시작점으로부터 $i$행 $j$열까지 도달하는 최단경로의 갯수를 저장할 배열 DP[$i$][$j$]을 사용하면, 오른쪽과 아래쪽으로만 이동 가능하므로 DP[$i$][$j$]에 도달하는 방법은 DP[$i$][$j - 1$]이 웅덩이가 아니면 왼쪽 칸에서 오른쪽 방향으로 이동하여 도달하는 경우가 존재한다.. 2023. 12. 19.
[Baekjoon] 2629번: 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 문제 해결 과정 착안 추의 갯수가 $n$개일 때, 각각의 추를 사용하거나 사용하지 않고 무게를 만들 수 있는 경우의 수를 모두 계산하면 지수 시간($=O(2^n)$)의 시간 복잡도를 가지므로 동적계획법(dynamic programming)을 활용하여 문제를 해결하고자 하였다. 추가 하나씩 새로 주어질 때마다, 기존에 잴 수 있던 무게와 더불어 추가적으로 잴 수 있는 무게들은 다음과 같다. 새로 추가.. 2023. 12. 15.
[Baekjoon] 9084번: 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어진 서로 다른 $n$ 가지 동전의 가치를 $c_1, c_2, \cdots, c_n$, 특정한 금액 $m$을 만들기 위한 경우의 수는 1) $c_1$ 짜리 동전만 사용하여 만드는 경우 (가능하다면) 2) $c_2$ 짜리 동전을 추가로 사용하여 만드는 경우 (가능하다면) 3) $c_3$ 짜리 동전을 추가로 사용하여 만드는 경우 (가능하다면) $\cdo.. 2023. 12. 7.
[Programmers] 연속 펄스 부분 수열의 합 https://school.programmers.co.kr/learn/courses/30/lessons/161988 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 동적계획법(dynamic programming)을 통해 부분 수열의 합을 구하는 알고리즘을 응용하여 펄스 부분 수열의 합을 구한다. 구현 이전 포스트에서 사용한 방법을 동일하게 적용하되, 원래 수열에 곱할 수 있는 펄스 수열은 1 또는 -1로 시작하는 두 가지의 경우가 있으므로, 원래 수열에 1과 -1로 시작하는 각각의 펄스 수열을 길이만큼 곱한 수열에 대해 부분 수열의 합.. 2023. 9. 7.

티스토리툴바