동적계획법 검색 결과

해당 글 25건

[BOJ 2616] 소형기관차 (C++)

소형 기관차 (Gold 4) 문제 전체 문제 보기 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 접근법 문제를 보고 처음 접근할 때는 완전 탐색이 가능한지를 먼저 살펴보는 것이 좋을 때가 많습니다. 완전 탐색으로도 쉽게 풀릴 수 있는 문제를 어렵게 고민하는 경우가 생길 수도 있기 때문입니다. 그리고 완전 탐색으로 답을 구할 수 없더라도, 완전 탐색으로 접근한 방법을 최적화하여 문제를 해결하는 경우도 많습니다. 이번 문제도 완전 탐색으로 먼저 접근해 보았습니다. 소형 기차는 총 3대입니다. 기차의 전체 ..
Algorithms/DP 2021. 11. 4. 12:25

[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