1. 문제 7579번: 앱 (acmicpc.net) 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 2. 메모이제이션과 결정문제 배낭문제의 변형, 값어치의 최대화가 아닌 비용이 최소인 값 이 문제는 아래와 같은 일반적인 방법으로 메모이제이션하는것은 불가능하다 (메모리의 최대 크기가 10,000,000, N의 크기가 100이기 때문에 128 MB보다 더 많은 메모리가 필요하다) solve(i, mem) = mem만큼 메모리를 비웠을때, i번째 인덱스에서 시작하여 최소인 cost를 리턴 solve(i, mem) = mi..

1. 문제 2623번: 음악프로그램 (acmicpc.net) 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 2. 간략한 풀이 이 문제는 각각 PD들이 주는 목록들을 합쳐 트리로 만들고, 그 트리를 위상정렬하면 자연스럽게 모든 pd의 요구사항을 만족할 수 있다. 하지만, PD들 서로의 목록에 모순(순환, 사이클) 이 있는 경우 모든 pd들의 요구사항을 만족할 수 없으니. 위상정렬을 하면서 사이클 존재 여부 또한 검사해야한다. 3. 위상 정렬 맨 마지막 노드인 리프를 제일 끝에 두는 방법이 ..

1. 문제 2473번: 세 용액 (acmicpc.net) 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 2. 이진 탐색 일단 용액들을 정렬하고 난 뒤, 완전 탐색으로 두개의 용액을 합한다. 그리고 그 합과 합할 나머지 용액하나를 정렬된 배열에서 이진 탐색하는 방법으로 문제를 해결하였다. 총 수행시간은 O(N^2 lgN) 이 걸린다. 이 문제를 풀때 시도를 많이 했는데, 문제는 타입이였다. 이전 용액 문제에서는 두개의 용액으로, 합해도 20억이 넘지 않았지만 이 문제는 3개의 용액이므로 ..

1. 문제 1208번: 부분수열의 합 2 (acmicpc.net) 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 2. 풀이1 이 문제는 입력의 크기 때문에 메모이제이션과 완전탐색으로는 해결하지 못한다. 따라서 주어진 수열을 절반으로 쪼개 각각의 모든 조합의 합을 구한뒤 두개의 합이 S인 조합의 개수를 구해야한다. 각각 따로 조합의 합을 map의 key로, value에 가짓수를 담고 마지막에 right[ s - left[]] 와 left[] 를 곱하면 합이 s인 전체의 ..

1. 문제 1202번: 보석 도둑 (acmicpc.net) 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 2. 풀이 이 문제는 탐욕법으로 해결할 수 있다. 가장 값비싼 보석을 가능한 가방중 가장 용량이 작은것에 넣는 것이다. 하지만 배열을 사용하여 문제를 풀 시 시간초과가 나온다. 따라서 적절히 사용한 가방을 제외 하고, 빠르게 작은 가방을 찾을 수 있는 자료구조를 사용해야한다. map을 사용하면 빠르게 원소를 제외할 수 있고, 최소 원소 또한 찾..

1. 문제 12852번: 1로 만들기 2 (acmicpc.net) 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 2. 풀이 3가지 함수를 사용하여 1로 만드는 것 전형적인 dp문제로 모든 경우의 수를 따져 함수를 사용할때마다 1씩 더하면서 기저조건인 1이 나올경우 0을 리턴, 0이나올경우 max값을 리턴하도록 함수를 짜면 문제없이 잘 동작할것이다. 이 문제는 또 과정을 추적해야한다. 과정을 추적하는 단순한 방법은 함수의 번호를 최적값과 같이 저장하는 것 이다. 코드는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ..