이 글은 풀이를 스스로 찾아내지 못한 문제들을 정리해놓은 글이다. 오답노트가 으레 그렇듯 나중에 다시 찾아와서 풀어볼 생각이다.

BOJ - 4386. 별자리 만들기

최소신장트리 문제인 것은 알고 풀기 시작. 이전에 비슷한 문제를 다익스트라로 풀어본 기억이 있어 다익스트라로 시도했다가 실패. 검색해보니 정점 중심의 다익스트라로는 풀 수 없고 간선 중심의 크루스칼 알고리즘이라는 것으로 푼다는 것을 알게 되었고, 해당 알고리즘을 사용했다.

그 와중에 우선순위큐로는 제대로 풀리지 않아서 (사실 엄밀히 말하면 필요 없는 상황이기도 했다. 다익스트라로 풀다가 수정한 코드라 남아있었을 뿐) 우선순위큐도 단순 배열로 바꾸고, 유니온파인드 알고리즘도 사용했다.

풀이 코드
닫기

풀이 참고

BOJ - 17472. 다리 만들기 2

풀이 방법 자체는 잘 생각해냈으나 예외 처리를 제대로 못해서 틀린 문제.

풀이 코드
닫기

풀이 참고

BOJ - 27172. 수 나누기 게임

"이중 for 문으로 풀면 되는 거 아닌가?" 했으나 당연히 시간 초과. 문제 분류를 확인해보니 '에라토스테네스의 체'가 보이기는 했는데, 어떻게 적용해야할지 감을 못잡고 풀이를 찾아봤다. 정확히는 어떻게 적용해야할지를 몰랐던 것보다 "'에라토스테네스의 체'를 쓰면 더 빠른 게 맞나?" 에서 헷갈린 게 더 컸다.

풀이 코드
닫기

풀이 참고

BOJ - 10942. 팰린드롬?

답변들을 캐시해둬서 풀었다. 잘 풀었지만 DP 로도 풀 수 있다는 글을 보고 풀이를 참고해 다시 풀어보았다.

풀이 코드 (캐싱 사용)
닫기
풀이 코드 (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 문제에서 채점 통과한 코드와 한땀한땀 비교해서 틀린 점을 찾아내서 통과했다.

풀이 코드
닫기

풀이 참고