Algorithms/DP 검색 결과

해당 글 24건

[BOJ 9465] 스티커(C++)

스티커 (Silver 2) 문제 전체 문제 보기 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 접근법 이 문제는 동적 계획법으로 풀 수 있습니다. 우선 점화식을 세워보겠습니다. 임의의 위치 n에서 우리는 두 가지 선택을 할 수 있습니다. 위쪽 스티커를 선택하거나, 아래쪽 스티커를 선택할 수 있습니다. (아무것도 선택하지 않을 필요는 없습니다.) 아래쪽 스티커 선택 만약 아래쪽 스티커를 선택하게 되면 바로 직전 위치에서는 위쪽 스티커를 선택할 수 있습니다. 하지만 아래의 그림처럼 직전 위치의 스티커..
Algorithms/DP 2021. 9. 20. 01:58

[BOJ 2407] 조합 (C++)

조합(Silver 2) 문제 전체 문제 보기 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 접근법 이 문제는 조합에 대한 이해를 바탕으로 점화식을 세워야 하며, 큰 수 덧셈을 구현할 수 있어야 합니다. 조합은 \(_{n}\mathrm{C}_{r} = _{n-1}\mathrm{C}_{r} + _{n-1}\mathrm{C}_{r-1} \)라는 성질이 있습니다. 이를 DP의 탑 다운 방식을 활용하여 구현할 수 있습니다. 그리고 계산 과정에서 나오는 수가 64bit 정수 크기를 넘기 때문에 문자열을 활용하여 큰 수 덧셈을 별도로 구현해야 합니다. 전체 구현 #include #include #include #include #defi..
Algorithms/DP 2021. 9. 19. 22:56

[BOJ 11053] 가장 긴 증가하는 부분 수열 (C++)

가장 긴 증가하는 부분 수열 (Silver 2) 문제 전체 문제 보기 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 접근법 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence) 문제는 동적 프로그래밍 문제 중에서 유명한 문제 중 하나이다. 두 가지의 풀이 방법이 존재하는데 상대적으로 이해하기 쉬운(상대 적으로 쉬운 것이지 결코 쉽지만은 않다.) \(O(N^2)\) 시간 복잡도를 가진 풀이와 직관적으..
Algorithms/DP 2021. 9. 8. 17:12

[BOJ 2579] (DP)계단 오르기(C++)

계단 오르기 (Silver 3) 문제 전체 문제 보기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 접근법 이 문제는 예전에 풀었던 BOJ 2156 포도주 시식 문제와 상당히 비슷하다.(포도주 시식 풀이) 포도주 시식 문제와의 차이점은 이 문제에서는 반드시 마지막 계단을 포함해야 한다는 점이다. 이번 문제에서도 3개의 계단을 연속으로 밟을 수 없다. 그래서 임의의 위치 \(n\)에서 점수의 최댓값을 \(f(n)\), \(n\)의 점수를 \(a(n)\)이라고 했을 때 \(f(n)\)은 아래의 두 가지 경우 중 큰 값이 이..
Algorithms/DP 2021. 8. 27. 17:29