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

BOJ - 1753. 최단경로

처음에는 가중치 합산만 고려한 BFS 로 풀려다가 실패. 제대로 풀려면 우선순위큐에 가중치를 적용해 풀어야 한다는 것을 찾아보고는 풀었다. 우선순위큐/힙은 분명 예전에 문제들을 풀어본 적이 있음에도 약간의 응용과 생각이 필요해지니 쉽게 풀지 못하고 헤맸다.

풀이 코드
닫기

풀이 참고

BOJ - 9375. 패션왕 신혜빈

조합을 사용해 푸는 문제. 함점 하나만 피하면 쉽다. 복잡하게 생각하지 말자!

풀이 코드
닫기

BOJ - 1504. 특정한 최단 경로

다익스트라 알고리즘을 다섯 번 써야 한다고 착각한다데가, 그 착각 때문에 알고리즘을 잘못 작성한 것이 패인. 올바르게 세 번만 적용하면 된다.

풀이 코드
닫기

풀이 참고

BOJ - 13549. 숨바꼭질 3

다익스트라 순회의 종료 조건을 어떻게 잡을 것인가? 에서 잘못 생각해 틀렸다.

풀이 코드
닫기

풀이 참고

BOJ - 9370. 미확인 도착지

다익스트라 알고리즘을 적용하되 같은 가중치에 대해 모든 경우의 수를 저장하고 그 중에 g,h 를 거쳐간 곳이 있는지 찾으려고 하였으나, 로컬에서는 잘 되지만 제출하면 "메모리 초과"로 실패한다. 메모리 초과를 보는 순간 그럴 수도 있겠다고 납득하고 더 고민하다가 결국 풀이를 찾아봤다.

a - t[n] 의 최단 거리 === a - g/h 의 최단 거리 + g - h 거리 + h/g - t[n] 의 최단 거리

가 존재하는지 찾는 문제였다.

위에서 푼 1504 번과 비슷한 아이디어의 문제였는데 풀이를 떠올리지 못해서 아쉽다.

풀이 코드
닫기

풀이 참고

BOJ - 6064. 카잉 달력

나는 수학에 너무 약하다.

풀이 코드
닫기

풀이 참고

BOJ - 7662. 이중 우선순위 큐

처음에는 우선순위 큐를 두 개 사용하되 어느 한 쪽에서 pop 이 되면 다른 한 쪽에서도 해당 값을 찾아 pop 하는 것으로 구현했다. 결과는 "메모리 초과". "다른 한 쪽에서도 해당 값을 찾아 pop 하는" 것이 비효율적이라 생긴 문제 아닐까 싶었다. (그런데 그렇다면 "시간 초과"였어야 할 것 같은데...)

여튼 구글링해서 풀이를 찾아보니 우선순위 큐 두 개를 사용하는 것 까지는 맞았지만, 대부분의 사람들이 큐에 들어있는 값들의 갯수를 객체에 체크해놓는 방식으로 문제를 해결했다. 나도 같은 방식으로 풀었다. 그런데 여전히 "메모리 초과", 혹은 "시간 초과" 혹은 "틀렸습니다" 가 떴다. 반례들을 계속 찾아서 로직들을 수정하면서 "틀렸습니다" 는 안 뜨게끔 고쳤는데 결국 "메모리 초과" 를 통과하지 못했다.

뭔가 이상하다 싶어서 검색해서 찾았던 풀이를 그대로 복붙했음에도 이상하게 채점 결과가 "메모리 초과"가 떴다. 내가 찾은 풀이가 이상한 것이든 백준 시스템에 문제가 생긴 것이든 여튼 nodejs 로 풀면 끝이 없겠다는 생각이 들었다.

그래서 결국 파이썬으로 풀었다.

시도 (Nodejs)
닫기
풀이 (Python)
닫기