알고리즘 오답노트 (~23.7.30)
이 글은 풀이를 스스로 찾아내지 못한 문제들을 정리해놓은 글이다. 오답노트가 으레 그렇듯 나중에 다시 찾아와서 풀어볼 생각이다.
BOJ - 2110. 공유기 설치
이진 탐색을 어떻게 적용해야 하지? 하는 부분에서 막혔다. 뭔가 약간의 힌트만 있으면 풀 수 있을 것 같아 구글링한 글을 앞부분만 살며시 읽어보고 풀었다.
풀이 참고
BOJ - 1300. K번째 수
이걸 대체 어떻게 이진 탐색으로 구한다는 것이지? 라고 당황했다가 풀이를 보고 감탄했다.
풀이 참고
BOJ - 12015. 가장 긴 증가하는 부분 수열 2
이 문제와 거의 동일한 문제인 가장 긴 증가하는 부분 수열 문제는 이미 풀어봤다. 해당 문제는 DP 로 풀었기 때문에 (이 문제는 이진 탐색으로 풀어야 한다는 걸 알고 있음에도) 다시 DP 로 풀어보았다. 당연히 로컬에서 간단한 문제는 잘 풀리지만 채점에 들어가면 1 ≤ N ≤ 1,000,000 범위를 감당하지 못하고 시간초과로 터져버린다.
DP 풀이법에 이진 탐색을 조합해서 푸는 것일 거라 생각하고 계속 생각해봤지만 답은 나오지 않았고, 결국은 풀이를 찾아보았다. 언제나 그렇듯 풀이에 감탄.
풀이 참고
BOJ - 11279. 최대 힙
"완전 이진 트리를 배열로 만들어 푸는 것이다" 라는 건 떠올렸지만 그 다음이 떠오르지 않아서 결국 찾아봤다. 최대 힙을 설명하는 글의 앞부분을 보자 마자 기억이 나서 후다닥 풀고는 "이 정도면 오답노트에 안 써도 되지 않나?" 라고 망설였으나, 여튼 혼자서 풀지 못한 건 맞으므로 (나는 전혀 모르지는 않았다는 구구절절한 사연과 함께) 오답노트에도 작성해 두기로 한다.
풀이 참고
BOJ - 11066. 파일 합치기
누적합과 삼중 반복문 DP 의 조합이라니.. 풀이글들마저 다 이해하기 어려워서 고생했다. 하단에 첨부한 링크가 그 중 제일 이해하기 쉬운 풀이글이다.
풀이 참고
BOJ - 18111. 마인크래프트
브루트포스로 풀어야 한다. 복잡하게 생각할 것 없이 최하층부터 최상층까지 훑어보면 된다. 아래 풀이 참고를 보니 시간 복잡도를 볼 줄 아는 것도 문제 풀이에 도움이 되겠구나 하고 새삼 깨달았다. 시간 복잡도는 신경 안 쓰는 편이었는데 신경써보자.
풀이 참고
BOJ - 1520. 내리막 길
DP 로 푸는 문제인 걸 뻔히 알고 풀기 시작했는데 자꾸 그냥 비효율적인 DFS 로만 풀려고 해서 풀지를 못한 문제. DP 는 점화식!