알고리즘 오답노트 (~24.1.14)
이 글은 풀이를 스스로 찾아내지 못한 문제들을 정리해놓은 글이다. 오답노트가 으레 그렇듯 나중에 다시 찾아와서 풀어볼 생각이다.
BOJ - 9252. LCS 2
LCS와 매우 비슷한 문제로, 푸는 방법도 매우 비슷하다. 일단 최장 공통 부분 길이를 구하는 로직은 동일한데, 문제는 최장 공통 문자열 그 자체를 찾는 것. 최장 공통 부분 길이를 구할 때 썼던 DP 테이블을 활용하면 된다. ...여기까지는 나도 직접 추론했지만, DP 테이블을 잘못된 방법으로 활용해서 답을 찾지는 못했다.
풀이 참고
BOJ - 1865. 웜홀
문제를 보자마자 플로이드-워셜이겠구 나 하고 풀었다.
그런데 전에 분명 풀었음에도 잘 기억이 나지 않아서 떠듬대다가 이전에 푼 문제와 검색해서 나온 글을 참고해서 풀었다.
...그런데 벨만-포드로도 풀 수 있다고 한다. 오히려 더 적합하다고 한다. 이 방법으로도 나중에 풀어보자.
풀이 참고
BOJ - 11780. 플로이드 2
플로이드와 매우 유사한 문제로, 각 도시간 이동 시 최소 비용을 구해야 한다는 점은 동일하다. 단지 이 문제는 거기에서 더해, 각 도시간 이동 시 최소 비용으로 이동할 수 있는 경로까지 찾아야 한다는 점이 다르다.
이 문제에서 추가로 요구하는 "이동 경로"를 찾는 것은 사실 큰 어려움 없이 했다. 하지만 플로이드-워셜 알고리즘 자체가 헷갈려서 (어째 풀 때마다 헷갈릴까..) 다시 살펴보기도 했고, 나중에 복습할 때 풀어보면 좋을 것 같아서 기록해둔다.
BOJ - 2263. 트리의 순회
이진트리의 inorder 와 postorder 를 갖고 preorder 를 만드는 문제. leetcode 를 열심히 풀던 시절 풀어본 기억이 있기도 해서 자신감 넘치게 풀었지만 결과는 "메모리 초 과". 함수 콜스택을 줄여야 하나보다 싶어서 while 문으로 풀었지만 역시 "메모리 초과". 결국 다른 사람의 풀이를 찾아서 비교해봤는데 순회하는 과정에서 비효율적인 인덱싱이 있었다. 풀이 없이 풀 수 있었는데 아쉽다.
풀이 참고
BOJ - 4803. 트리
정점과 간선이 주어질 때 트리는 몇 개인지 찾는 문제. 나름 순회를 돌면서 검증하려 했으나 로직이 잘못되어서 1차 실패. 이후 너무 복잡하게만 생각하다가 방법을 알아내지 못하고 다른 사람의 풀이를 찾아본 뒤 풀었다. 답이 생각보다 단순해서 그걸 직접 생각해내지 못한 게 아쉽다.
풀이 참고
BOJ - 1717. 집합의 표현
그냥 map 두 개를 조합해서 풀어보려다가 메모리 초과로 실패. 유니온 파인드 알고리즘만 찾아보고 직접 코드를 짰다가 root 노드를 찾는 로직에서 갱신도 같이 해줘야 하는 걸 놓쳐서 또 실패. 결국 다른 사람의 풀이까지 참고했다.
풀이 참고
BOJ - 4195. 친구 네트워크
유니온 파인드 알고리즘 + 집합 별 카운트까지 구하는 문제. 풀이를 몰라서 못풀었다기 보다는 디테일을 놓쳐서 헤맸다고 보는 게 맞겠다.