Jupitor's Blog

저번 포스트에서 정확한 BFS방법은 아니지만 그와 흡사한 제가 혼자 생각한 알고리즘으로 PrimePath 문제를 풀어보았는데요. 굉장히 느렸고, Dijkstra 알고리즘이 궁금해서 이 알고리즘으로 한번 해볼까, 싶더군요. 결과를 먼저 말씀드리자면 제가 독자적으로 만들어낸 알고리즘은 Trash(...) 였습니다. 시간이 얼마나 걸렸는지를 먼저 보시죠. 위에가 Dijkstra 알고리즘, 아래가 저의 알고리즘을 이용한 결과입니다. 둘다 최단 경로를 찾아냈지만 시간 차이가 엄청납니다. Dijkstra는 139ms, 제 건 16252ms... 100배 이상이 차이납니다 =_=; Dijkstra는 유명한 알고리즘으로 알려져 있고 많은 응용이 된다고 합니다. 자세한 설명은 검색하면 정말 많이 나옵니다. (wikipe..

알고리즘 문제 중에 이런 문제가 있습니다. 특정한 4자리 숫자 2개 a, b가 있습니다. 숫자 a의 한 자리 숫자만을 변경해서 b를 만들되, 이 때 거쳐가는 숫자들은 모두 소수여야 합니다. 몇 번을 거쳐야만 숫자 b를 만들 수 있는지 구하는 문제입니다. 예를들면, 1033 에서 8179 로 바꾸는 경로를 생각해봅시다. 1033 1733 3733 3739 3779 8779 8179 이렇게 여섯 단계를 거쳐서 8179로 만들 수 있겠죠. 중간에 1733부터 8779는 모두 소수입니다. 이 문제를 처음 접하고 저는 어떻게든 해서 문제를 풀 수 있게 됬는데 다른 사람의 글을 보니 Breadth-first search 또는 Dijkstra’s algorithm algorithms 알고리즘을 사용해서 풀 수 있다고..