계획법7 [백준 1943번] 동전 분배 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1≤N≤100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선 www.acmicpc.net DP를 통해 접근할 수 있는 문제입니다. 그리디로 왜 안 되는지는... 잘 모르겠네요 ㅠ 모든 동전의 값의 합을 먼저 구하고, 이것이 홀수라면 반으로 나눌 수 없으므로 0을 출력하고 넘어갑니다. 짝수라면, 총 값의 반을 최대 기준으로, 만들 수 있다면 해당 테이블에 1을 기록하며 진행합니다. 이전 인덱스의 값을 참조하여 진행하기 때문에 탑-다운 방식으로.. 2021. 9. 30. [백준 1823번] 수확 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 벼가 한 줄로 쭉 세워져 있고, 벼의 가치는 각각 입력으로 들어옵니다. 벼를 나중에 수확할수록 이익을 더 얻기 때문에, 끝까지 가 봐야 알 수 있으므로 그리디 방식으로는 해결할 수 없습니다. 이 문제의 경우, DP를 이용하여 접근할 수 있습니다. 보통 DP 문제의 경우 맨 마지막 값이 정답이 되는데, 이 문제의 경우 배열의 앞과 뒤를 좁혀 가며 탐색을 하므로, 중간의 어느 지점이 맨 마지막에 탐색하.. 2021. 9. 29. 세그먼트 트리 다음과 같은 문제를 생각해 봅시다. 배열 arr에는 수많은 int형 정수가 들어 있다. arr의 크기 n은 최대 10만이며, 각 정수는 1000 이하의 크기를 가진다. 배열이므로, 당연히 arr의 모든 원소는 인덱스가 정해져 있다. 인덱스는 0부터 시작한다. 총 m줄에 걸쳐 구간이 주어질 때, 주어진 구간합을 출력하는 코드를 작성하시오. (n 2021. 9. 25. [백준 3687번] 성냥개비 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 제가 느끼기에 이 문제는 DP와 그리디를 이용하는 부분으로 나뉩니다. 그리디를 이용하는 부분은 최댓값을 구하는 부분으로, 상대적으로 더 쉽습니다. 성냥개비가 짝수개 있을 때는, 모두 1을 만들면 됩니다 (자릿수를 크게 함). 1을 만드는 데 성냥개비가 2개 소모되므로, 총 (성냥개비 개수 / 2)개의 1을 출력합니다. 성냥개비가 홀수개 있을 때는, 맨 앞자리에 7을 출력하.. 2021. 9. 9. [백준 12865번] 평범한 배낭 난이도: 골드 5 문제 링크: www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 오늘 공부한 다이나믹 프로그래밍을 응용해 보기 위해 풀어 본 문제입니다. 얼핏 보면 간단해 보이지만, 두 개의 변수 W와 V를 고려해야 해서 쉽지 않습니다. 제가 예전에 풀었던 최소 편집 거리 문제와 비슷하다는 느낌을 받았습니다. 나름 유명한 문제인데, Google 등에 knapsack 문제라고 검색해 보시면 이 문.. 2021. 2. 6. 다이나믹 프로그래밍 프로그래밍은 대개 현실 세계의 문제를 전산적으로 접근하여 풀기 위하여 사용됩니다. 그 중 어떤 문제들은, 컴퓨터를 사용해도 매우 오래 걸리거나 해결하기 어렵기도 합니다. 컴퓨터 역시 현실 세계의 물건인 만큼, 저장 공간이나 연산 속도에 한계가 존재하며, 이러한 한계가 걸림돌이 되는 경우가 분명히 존재합니다. 만약 어떤 알고리즘이 O(2^N)의 시간 복잡도를 가진다면, N의 크기가 커질수록 처리 속도가 비약적으로 증가할 것입니다. 하지만, 메모리를 조금 더 사용하여 같은 문제를 O(N)의 시간 복잡도로 해결할 수 있다면, 이는 매우 효율적인 방법이 될 수 있습니다. 다이나믹 프로그래밍 (dynamic programming) 은 이렇게 연산 속도를 대폭 줄일 수 있는 대표적인 방법입니다. 다이나믹 프로그래밍.. 2021. 2. 5. 이전 1 2 다음
