kakasoo

질문에 있는 글인데, 너무나 잘 정리되어 있어서 가지고 왔다. (*이런 것에는 저작권이 없겠지?) 1. 가중치가 없는 최단 경로, 한 마디로 다익스트라 알고리즘을 써야 하는 게 아니면 무조건 bfs라는 것. 2. 모든 칸을 0으로 하나씩 바꿔보는 브루트 포스는, 최악의 경우 (1000 * 1000)^2의 반복이 된다. (map size = 1000 * 1000, 이고 각각의 칸이 모두 1인 경우가 있을 수 있기 때문에 1000000000000 번이다.) 3. 칸마다 방문 체크를 하는 방식으로는 풀 수 없다. 이거 참 중요한 이야기인데, 벽을 부수지 않은 세계와 벽을 부순 적 있는 세계가 있다고 가정해보자. 벽을 부수지 않은 세계를 0번 세계, 그리고 부순 세계를 1번 세계라고 할 때, 0번 세계에서 0번..

그리디 알고리즘 (탐욕 알고리즘)이라고 하는데, 비슷한 종류의 문제들 중에 이게 가장 수준이 높았던 거 같다. 그리디 알고리즘은, 솔직히 나는 이런 거에 알고리즘이라는 말을 붙일 필요가 있나 싶을 정도로 간단했다. 그 순간 순간의 최적해를 쫓아 가서, 근사값을 구하는 방식의 알고리즘이라는 건데, 당연 그 순간의 최적해를 쫓을 때 최종적인 답안이 최적해가 아닐 수도 있다. 말하자면, 지금 알고리즘 조건에 따라서, 이렇게 설명할 수 있겠다. 2일 간격으로만 음식을 먹을 수 있고, 더 적은 음식을 먹어야할 때, 첫날 음식을 먹느냐 둘째날 음식을 먹느냐, 첫날과 둘째날을 비교해서 작은 쪽을 먹는다는 게 그리디의 방식이지만, 만약 셋째날이 무한대에 수렴한다면 다시 처음으로 돌아가 두번째를 먹는 것을 고르는 것이 ..