알고리즘 오답노트 (~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. 친구 네트워크
유니온 파인드 알고리즘 + 집합 별 카운트까지 구하는 문제. 풀이를 몰라서 못풀었다기 보다는 디테일을 놓쳐서 헤맸다고 보는 게 맞겠다.