1차 풀이 (2018-08-14, 2060 KB, 4 MS) |
부분 문제로 나눌 수 있을까?
K개의 포도주 잔이 있을 때, 한번에 해결하기 힘들다면
각 선택별로 부분 문제를 만들어 해결해보자고 생각했다.
각 문제에서 가능한 선택마다 부분 문제를 만들었을 때,
각 문제는 일정한 입력에 대해 일정한 결과만을 출력하며,
원래 문제와 부분 문제는 서로 독립적이고, (앞의 선택이 뒤의 선택에 영향을 주지 않음)
부분 문제가 최적일 때, 원래 문제도 최적으로 구해질 수 있으므로,
최적 부분 구조를 가진 동적 계획법으로 풀 수 있다.
제한을 올바르게 이해하고 있었나?
주어진 제한은 "연속으로 3잔 마시는 것은 안된다" 이지만,
연속으로 고르지 않아도 된다는 점에 유의해야 한다.
만약 위의 사항을 염두하지 못하고 알고리즘을 짜면,
다음의 테스트 케이스에서 오답을 낼 것 이다.
10 10 1 1 10 10
→ 최적은 1, 2, 5, 6 번째 잔을 선택하는 것.
각 경우마다 가능한 선택은 무엇인가?
동적 계획법으로 정확하게 문제를 풀기 위해서는
- 앞의 선택으로 인해 뒤의 선택에 영향이 있으면 안되고,
- 중복되거나 누락되는 선택방법이 있어서는 안된다.
위의 조건을 만족하는 선택방법은 다음과 같다.
- 0개 선택. 1개 건너뜀.
- 1개 선택. 1개 건너뜀.
- 2개 선택. 1개 건너뜀.
3개 이상을 선택하는 방법은 제약에 위반된다.
재귀로 풀까, 반복으로 풀까?
재귀는 큰 문제를 작은 문제로 쪼개면서 문제를 풀고, (해결한 작은 문제 조각들은 캐싱하여 중복계산을 방지한다.)
반복은 가장 처음부터 차근차근 문제를 푼다. (푼 문제의 답은 캐싱하여 다음 문제를 풀 때 활용한다.)
부분 문제가 비약적으로 많아지는 문제의 경우에는
함수 호출 스택에 오버헤드가 발생하므로,
왠만하면 재귀를 사용하지 않고 반복으로 풀고 싶었다.
10000개의 포도주가 주어졌을 때,
각 선택은 많아도 2개의 포도주 밖에 선택하지 못하지만,
생성되는 부분문제는 무려 3개다.
말로 설명하자니 잘 모를 수 있겠지만,
트리로 그리면 큰 숲이 펼쳐질 것 이다.
반복으로 문제를 풀려면,
반복으로 문제를 푸는 것은,
앞에서부터 차근차근 문제를 풀어나가는 대신,
앞선 문제의 답에서 다음 문제의 답을 도출하는 것 이다.
n번째부터 0, 1, 2개를 선택해야 할 때,
앞 뒤 문제의 연관성을 이해하면서 구현한다.
2차 풀이 (2018-08-16, 2060 KB, 0 MS) |
어디에서 시간이 오래걸릴까?
나름 최적화한 알고리즘(1차풀이)에서 4 MS의 오차가 발생한것에 의문을 품었다.
원인을 알기위해 다른 사람들이 어떻게 문제를 풀었는지 체크해봤는데,
별 다른 차이점을 알지 못했다.
가장 큰 차이점이라고 해봐야,
슬라이딩 윈도우 기법을 사용하여 배열의 크기를 3~5 정도로 줄인 것?
그렇다면 메모리 사용량에서만 차이가 나야지, 시간의 차이는 날 수 없다.
어디서 4 MS의 지연이 발생할까?
cin, cout은 동기화 과정이 포함되어 있다.
C++에서 사용하는 cin, cout은 stdio와 동기화 과정이 포함되어 있다.
즉, 입출력 과정에서 시간이 지연되었다고 생각할 수 있고,
대체로 10,000개의 입력당 4 MS 정도가 지연된다.
stdio와 동기화 과정을 풀어주는 명령어를 적어주면,
예상대로 0 MS로 줄어드는 결과를 확인할 수 있었다.
이에 대한 자세한 내용은 여기에 나와있다.
