알고리즘 오답노트 (~24.4.6)
이 글은 풀이를 스스로 찾아내지 못한 문제들을 정리해놓은 글이다. 오답노트가 으레 그렇듯 나중에 다시 찾아와서 풀어볼 생각이다.
BOJ - 2162. 선분 그룹
CCW 와 유니온파인드를 조합하여 푸는 문제. 접근은 올바르게 했으나 CCW 에서 케이스를 하나 놓치고, 유니온파인드도 올바르게 적용하지 못해서 틀렸다. 풀이를 찾아보지는 않고 반례를 통해서 잘못된 점을 직접 찾은 것이 그나마 위안거리다.
풀이 참고
BOJ - 25308. 방사형 그래프
삼각함수! 이차원 방정식! ...수학 기초를 다시 공부해야 하는 것인가...?
풀이 참고
BOJ - 7869. 두 원
제2코사인법칙! 부채꼴의 넓이! ...나 수학 공부 하고 있는 것인가...?
풀이 참고
BOJ - 2252. 줄 세우기
위상정렬! 새로운 걸 배웠다.
풀이 참고
BOJ - 1311. 할 일 정하기 1
[단계별로 풀어보기] 를 통해 문제에 접근하면 설명에 "선택한 열의 상태를 비트마스크로 저장하여 DP를 진행하는 문제" 로 되어있다. 언뜻 볼 때는 "비트마스킹은 결국 데이터를 저장하는 한 방법일 뿐인데 강조할 필요가 있나?" 라고 생각했는데, 풀어보니 "강조할 필요가 있구나" 라고 감탄하게 되었다.
풀이 참고
BOJ - 2098. 외판원 순회
기본적인 로직은 바로 위 문제 할 일 정하기 1 에서 사용했던 풀이를 참고했다. 당연히 그대로 사용하면 안 되고 "출발 도시로 돌아온다" 는 부분을 위해 로직을 수정해줘야 한다.
풀이 참고
BOJ - 2749. 피보나치 수 3
2차원 행렬과 분할 정복을 사용한 거듭제곱! 분명 이전에 비슷한 문제를 풀어본 적이 있었는데.. 아쉽다.
풀이 참고
BOJ - 2482. 색상환
재귀로 풀 수 있을 줄 알았는데.. 2차원 배열을 사용한 DP 방식이 주류인 것 같다.
풀이 참고
BOJ - 1786. 찾기
KMP 알고리즘으로 풀어야 한다. 이 알고리즘은 접두사(prefix) 접미사(suffix)를 조합하는 방식인데, 이 조합이 회문(Palindrome)이랑 헷갈려서 이해하는 데 혼났다. 여튼 어찌어찌 풀었는데, 여전히 헷갈린다.