알고리즘 오답노트 (~24.2.16)
이 글은 풀이를 스스로 찾아내지 못한 문제들을 정리해놓은 글이다. 오답노트가 으레 그렇듯 나중에 다시 찾아와서 풀어볼 생각이다.
BOJ - 4386. 별자리 만들기
최소신장트리 문제인 것은 알고 풀기 시작. 이전에 비슷한 문제를 다익스트라로 풀어본 기억이 있 어 다익스트라로 시도했다가 실패. 검색해보니 정점 중심의 다익스트라로는 풀 수 없고 간선 중심의 크루스칼 알고리즘이라는 것으로 푼다는 것을 알게 되었고, 해당 알고리즘을 사용했다.
그 와중에 우선순위큐로는 제대로 풀리지 않아서 (사실 엄밀히 말하면 필요 없는 상황이기도 했다. 다익스트라로 풀다가 수정한 코드라 남아있었을 뿐) 우선순위큐도 단순 배열로 바꾸고, 유니온파인드 알고리즘도 사용했다.
풀이 참고
BOJ - 17472. 다리 만들기 2
풀이 방법 자체는 잘 생각해냈으나 예외 처리를 제대로 못해서 틀린 문제.
풀이 참고
BOJ - 27172. 수 나누기 게임
"이중 for 문으로 풀면 되는 거 아닌가?" 했으나 당연히 시간 초과. 문제 분류를 확인해보니 '에라토스테네스의 체'가 보이기는 했는데, 어떻게 적용해야할지 감을 못잡고 풀이를 찾아봤다. 정확히는 어떻게 적용해야할지를 몰랐던 것보다 "'에라토스테네스의 체'를 쓰면 더 빠른 게 맞나?" 에서 헷갈린 게 더 컸다.
풀이 참고
BOJ - 10942. 팰린드롬?
답변들을 캐시해둬서 풀었다. 잘 풀었지만 DP 로도 풀 수 있다는 글을 보고 풀이를 참고해 다시 풀어보았다.
풀이 참고
BOJ - 17404. RGB거리 2
RGB거리 에서 조건이 더 붙은 문제. 접근 자체는 옳게 했고 (= DP), 예제와 게시판 반례들도 모두 통과하게 코드를 짰으나 채점은 통과하지 못했다.
- 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
이 두 조건을 해결하기 위한 로직을 어렵게 생각해서 코드를 복잡하게 짜놨더니, 엣지 케이스가 있는 것 같다. 다른 사람 풀이를 보니 코드가 정말 간단했다.
풀이 참고
BOJ - 2166. 다각형의 면적
"삼각형으로 쪼개서 합을 구한 뒤 합치면 될 것 같은데.." 라는 생각까지는 했지만 적절히 쪼갤 수 있는 방법이 생각나지 않아 결국 풀이를 찾아보았다. 벡터의 외적, CCW 라는 개념을 알면 쉽게 풀 수 있는 문제였다. 보다보니 중고생때 배웠던 것 같다 벡터의 외적..
풀이 참고
BOJ - 17386. 선분 교차 1
CCW 를 활용하는 문제다. 중/고등학교 수학 수업 시간으로 돌아간 기분이다.
풀이 참고
BOJ - 20149. 선분 교차 3
CCW 를 활용하는 문제다. 중/고등학교 수학 수업 시간으로 돌아간 기분이다. (복붙아님)
한 점으로 교차할 경우 교차점 좌표를 찍는 것이 생각보다 까다로워서 여기서 좀 헤맸다.
그런데 웃긴 건 채점 통과를 두 번이나 실패하게 만든 건 좌표를 찾는 코드가 아니었다는 것이다. 결국 선분 교차 2 문제에서 채점 통과한 코드와 한땀한땀 비교해서 틀린 점을 찾아내서 통과했다.