지난번에 Dijkstra 알고리즘에 대해서 제가 이해한 방식대로 설명해봤었는데, 이번에는 Mo's 알고리즘을 제가 이해한대로 한 번 설명해보고자 합니다. 물론, 지난번과 같이 이건 제가 이해한대로 설명한 것이기 때문에 정확한 설명이 아닐 수 있습니다. 그래도 Mo's 알고리즘이 무엇인지를 이해하는데에는 도움이 되지 않을까 해서 글을 올려봅니다. 그 전에 Mo's 알고리즘이 무엇인지와 어떤 문제들을 해결할 수 있는지에 대해서 설명해보겠습니다. Mo's 알고리즘은 무엇인가? 후술하겠지만 Mo's 알고리즘은 Sqrt-Decomposition(평방분할)의 아이디어를 차용해서 특이한 구간 쿼리들을 계산하는 테크닉 입니다. 구간 쿼리라면 Segment Tree를 주로 떠올리실텐데, 이 알고리즘의 시간복잡도는 Seg..

이번 글에서는 Dijkstra 알고리즘을 역추적하는 방법에 대해서 설명해보고자 합니다. Dijkstra 관련 문제들을 풀다보면 가끔씩 최단 경로를 출력하라는 문제들을 볼 수 있습니다. 이럴 때에는 도착 노드부터 시작 노드까지 역으로 추적하는 방법으로도 최단 경로를 찾을 수 있습니다. 그러면 어떻게 역추적을 하면 될까요? 일단 최단 경로의 특성에 대해서 알아보도록 합시다. 노드 A, B가 각각 시작 노드와 도착 노드라 합시다. 그리고 A와 B간의 최단 경로에 K라는 노드가 속할 수 있다고 합시다. 그렇다면 다음과 같은 식이 성립합니다. A -> B의 최단 거리 = (A -> K의 최단 거리) + (K -> B의 최단 거리) 이러한 식은 A -> B의 최단 경로에 속하는 모든 노드들에 대해서 적용할 수 있습..

이번에는 Dijkstra 알고리즘에 대해서 설명을 해볼건데, 제가 이해한 방식으로 한 번 설명을 해보려고 합니다. 따라서 이게 옳은 설명인지에 대해서는 엄청 확신이 들지는 않지만 그래도 알고리즘 기본적인 작동방식을 이해하기는 쉽지 않을까 생각해봅니다. (그래서 정확한 증명보다는 이해하는데에 좀 더 집중을 하면 좋을 것 같습니다!) 그 전에 앞서서 일단 BFS 알고리즘의 특성에 대해서 설명해보도록 하겠습니다. BFSBFS(Breadth First Search)는 그래프 탐색 방법 중 하나인데, 특정 노드부터 시작해서 근처에 있는 순서대로 탐색을 하는 방법입니다. 구현을 할 때에는 주로 Queue로 구현을 하는데, Queue에 나오는 순서는 시작한 노드에 근처에 있을 수록 더 빨리 나옵니다. 이러한 특징 때..

제가 코드포스 블루를 달았을 때 사용했던 알고리즘이기도 하고, 이걸 변형해서 제가 문제도 냈었기 때문에 한 번 설명해보고자 합니다. (정확한 설명은 아닐 수 있지만, 최대한 직관적이게 적어볼려고 하니 컨셉만 잘 전달되었으면 합니다.) Trie(트라이)는 문자열을 트리 형태로 저장하는 자료구조입니다.  아래 사진을 보면 이해하기 쉬우실 겁니다. 보면은 해당 트라이에 삽입된 단어들은 "A", "to", "tea", "ted", "ten", "i", "in", and "inn" 인데, prefix가 겹친다면 같은 노드를 타고 내려가도록 트리가 생성되어 있습니다. 트라이의 특징으로는 Insertion / Deletion / Search 하는데 전부 O(|S|) 만에 가능합니다.  그런데 이러한 자료구조의 특징을..