Algorithms/DP 검색 결과

해당 글 24건

[BOJ 2229] 조 짜기 (C++)

조 짜기 (Gold 5) 문제 전체 문제 보기 2229번: 조 짜기 알고스팟 캠프에 N(1≤N≤1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 학 www.acmicpc.net 접근법 이번 문제는 동적 계획법을 활용하여 \(O(n)\) 시간 복잡도로 풀 수 있는 문제입니다. 동적 계획 법으로 문제를 풀기 위해서는 일반화하는 과정이 필요합니다. 먼저 동적 계획법에서 사용할 dp[i]은 i번째 사람까지 조를 짰을 경우 최댓값으로 정의할 수 있습니다. 그리고 초기값은 다음과 같이 설정할 수 있습니다. dp[0]은 0번 사람 한 명만 들어오기 때문에 최대 값은 0일 수밖에 없습니다. dp[1]은..
Algorithms/DP 2021. 10. 27. 10:12

[BOJ 11066] 파일 합치기(C++)

파일 합치기(Gold3) 문제 전체 문제 보기 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 접근법 이번 문제는 동적 계획법으로 풀 수 있는 문제입니다. 동적 계획법의 주요한 두 가지 개념은 다음과 같습니다. 큰 문제를 작은 문제로 나눠서 문제를 해결한다. 한번 푼 문제를 저장하여 불필요한 연산을 줄인다. 우선 큰 문제를 작은 문제로 나눠 봅시다. 문제의 첫 번째 예시 (40 30 30 50) 인경우를 살펴보겠습니다. 장의 수가 총 4개일 때 마지막으로 파일을 합쳐서 하나로 만들 때는 다음과 같이 3..
Algorithms/DP 2021. 10. 20. 10:31

[BOJ 14501] 퇴사 (C++)

퇴사(Silver 3) 문제 전체 문제 보기 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 접근법 이 문제는 동적 계획법으로 풀 수 있는 문제입니다. 문제에서 주어진 예시는 아래와 같습니다. 백준이가 1일에 상담을 진행하게 되면 3일 뒤인 4일 상담부터 진행할 수 있습니다. 2일에 상담을 진행하게 되면 5일 뒤인 7일부터 다시 상담을 진행할 수 있습니다. 이를 일반화해서 설명하면 다음과 같습니다. 임의의 날 n일에 상담을 진행하게 되면 n + Tn일에 다시 상담을 진행할 수 있는 것입니다. 그리고 어떤 날은 n일에 상담을 하지 않는 것이 더 많은 금액을 얻을 수도 있습니다. 만약 n일에 상담하지 않는다면 다음날인 n+1일의 최대 금액과 동일합니다..
Algorithms/DP 2021. 9. 30. 23:56

[BOJ 17626] Four Squares (C++)

Four Squares (Silver 4) 문제 전체 문제 보기 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 접근법 이 문제는 완전탐색 혹은 DP로 풀 수 있습니다. 여기서는 DP로 접근하여 풀었습니다. DP로 풀기 위해서 점화식은 다음과 같이 정리할 수 있습니다. \[f(n) = \mbox{min}(f(1 * 1) + 1 , f(2 * 2) + 1, ... ,f(\sqrt{n} * \sqrt{n} + 1)\] 전체 구현 아래와 같이 구현하여 문제를 해결할 수 있습니다. ..
Algorithms/DP 2021. 9. 23. 10:38