티스토리 뷰
DP 말고 평소에 심화 공부 해보고 싶었던 그리디도 일지를 쓸거다. 그리디 특성상 아이디어가 굉장히 중요하고 구현에는 큰 문제가 없기 때문에 비슷한 문제라도 일지에 되도록이면 일지에 남기는 방향으로 진행할거다. 또 증명도 되도록이면 해서 올릴거다. 증명을 함으로써 아이디어가 기억에 더 잘 남고 비슷한 성질을 이용하는 아이디어도 잘 떠올릴 수 있을 것이라 믿기 때문에 신박한 아이디어는 증명을 꼭 해볼 것이다.
그리디 알고리즘은 매 순간순간 최적의 길을 택하는 알고리즘이다. 예를 들어 A→C 경로와 A→B→C의 경로가 있고 A에서 C까지 최소비용으로 가는 문제가 있을 때 A→B→C 경로가 더 싼 경우는 A→B + B→C < A→C인 경우고, 이는 달리 말하면 A→B < A→C이다. 즉 A에서 봤을 때 가장 작은 비용으로 가는 길을 택하고 이를 반복하면 최소경로의 길을 택할 수 있다. 이것을 확장한 것이 유명한 Pathfinding 알고리즘인 다익스트라(Dijkstra) 알고리즘이다.
암튼 그리디 알고리즘은 특정 조건 하 에서만 매우 강력하다. 위에서 든 예시와 같은 경우 모든 경로에서의 비용이 양수라는 것이 보장되어있어야 그리디한 방법으로 경로를 선택했을 때 최적해가 보장된다. 따라서 이를 증명하고 반례를 잘 확인해주는 것이 문제풀이에 중요하다.
16496번: 큰 수 만들기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나
www.acmicpc.net
이문제 같은 경우 당연히 그리디를 써야할 것 처럼 생겼다. 9같은게 있으면 맨앞으로 보내고 아니면 뒤에 갖다붙이고 하면 깔끔하게 최대값이 튀어나올텐데, 이를 비교할 방법이 필요하다. 처음에 생각한 방법은 10 보다는 9가 더 앞에 와야되니까 자리수를 맞추기 위해 뒤에 0을 채우자는 방법인데, 구현하고 몇가지 테스트 케이스를 넣어보니 오류가 있었다. 71 하고 7 중에서 0을 채우면 71이 더 우선해야하는데 717보다는 771이 더 크다. 따라서 방법은 잘못됐고, 비슷한 이유로 9를 채우는거도 안된다. 그래서 다음으로 생각한게 76까지는 7이 먼저와야되는데 78부터는 78이 먼저와야하면 증가하는 걸로 판단할 수 있지 않을까? 하고 구현을 하는중에 더 좋은 생각이 났다.
어차피 78 > 7인 이유가 8이 7보다 커서인데, 이건 그럼 자리수가 같아질때까지 반복을 하면(78 > 77) 동일한 결과를 얻고, 구현하기도 쉽고 반례도 없을것 같다. 증가하는것으로 판단하면 342같은 경우를 보면 언제까지 증가하는걸 봐야할지도 모르겠고 생각할게 많아진다. 그래서 반복하는 방법으로 구현했더니 AC를 받았다. 구현을 편하게 하기 위해서 상한인 9자리로 통일시켰다.
참고로 파이썬 구현 날먹 된다... 그리고 문제를 잘읽자
18185번: 라면 사기 (Small)
라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i
www.acmicpc.net
아이디어 떠올리기도 어렵고 이게 최적인지 의심이 가서 계속 반례확인을 했던 문제다.
첨에는 그냥 세개 연속? 바로 구매 인줄 알았으나 1 2 1 1 같은건 보니까 세개 연속이라고 낼름 먹어버리면 0 1 0 1 돼서 안되고, 두개를 먼저 사고 0 1 1 1을 만들고 세개를 사야 최적이다. 이걸 정량화하면 ^ 모양, 즉 A[i] A[i+1] A[i+2]중에서 A[i+1]이 가장 큰 경우를 걸러서 따로 판단해줘야 한다는 것이다. 이때는 진행방향(i가 커지는 방향, 오른쪽으로 두겠다)으로 3연속이 터질수가 있으니 일단 A[i]랑 A[i+1]으로 두개묶음을 사서 A[i+1]이랑 A[i+2]랑 개수를 맞춘다. 그후에 세개묶음을 살 수 있으면 산다. 근데 이게 왜 최대지?? A[i+3]이 0이면 망하는거 아냐?
잘 보면 1 2 1 0 1 같은 경우 1 2 1에서 3개를 묶어서 사고 남는 1개를 사나 2개씩 묶어서 두번 사나 똑같은 비용이 든다. 저렇게 대칭이 아니더라도 3 4 2를 보면 3묶음 두번, 2묶음 한번, 1개 한번보다는 2묶음 두번, 3묶음 한번, 2묶음 다시 한번이 비용이 똑같다! 이게 성립하는 이유는 일단 묶을수록 개당 비용이 싸지고, 묶음에 라면을 하나 더 추가할 때 드는 비용이 2원으로 동일하므로 묶음의 개수가 똑같으면 결과적으로 답이 같다는 것이다. 그래서 A[i+3]에 뭔가 있을 경우를 대비해서 min(A[i+1], A[i+2])를 유지하는 방향으로 순차적으로 그리디하게 선택하면 AC를 받는다.
비슷한 문제로 다음 번호가 있는데, small을 완전히 이해하면 풀 방법이 바로 생각나기때문에 쉽게 풀 수 있다.
'코딩일지' 카테고리의 다른 글
| 9월 일지 (0) | 2023.09.30 |
|---|---|
| 백준 그리디 일지 (3) (0) | 2023.04.29 |
| 백준 DP 일지 2 (0) | 2023.04.20 |
| 백준 그리디 일지 (2) - 순열 사이클 분할 (0) | 2023.04.05 |
| 백준 DP 일지 (1) (0) | 2023.03.29 |