본문 바로가기

Algorithm

 (143)
111. Grid & Flood Fill 그리드(격자, Grid)는 특수한 형태의 그래프로, $n$차원 좌표공간에 존재하는 점으로 표현되는 정점들과 정점들 사이를 잇는 간선으로 이루어져 있다. $n$은 대체로 $2$이며 가끔씩 $n$이 다른 값인 문제도 존재한다. 또한 점 대신 칸으로 이루어진 그리드가 등장하는 경우도 많은데, 각 칸을 그 중심점으로 바꾸면 정점과 간선으로 이루어진 그리드로 쉽게 변환이 가능하므로 이것은 별로 문제가 되지 않는다. 그리드의 좌표를 인덱스(Index)라고 하는 경우도 많다. 그리드에서 정점 사이를 잇는 간선은 보통 서로 인접한 칸들 사이에는 모두 존재한다. 일반적으로 그리드에서 두 칸이 인접하다는 것은 이렇게 이해할 수 있다: 정점 $\text{A}$의 좌표가 $(a_1, a_2, \ldots, a_n)$이고 정점..
110. Breadth First Search 너비 우선 탐색(Breadth First Search, BFS)은 노드를 탐색하고, 그 노드와 인접한 노드를 탐색하고, 그 노드들과 인접한 노드를 탐색하는 식으로 탐색을 시작한 노드에서 가까운 노드부터 차례로 탐색을 진행하는 탐색 방법이다. 이전에 탐색한 노드들과 인접해서 이후에 탐색할 예정이지만 아직 탐색하지 않은 노드들을 저장하기 위해 보통 큐가 사용된다. 탐색 과정에서 시작 노드에서 각각의 노드까지의 최단 경로의 길이를 알 수 있게 된다. DFS와 마찬가지로 인접한 노드가 여러 개 있을 경우 문제 상황에 맞게 탐색 순서를 정하면 된다. DFS를 설명한 글에 나온 그래프의 노드 $\text{D}$에서 BFS를 시작하면 BFS는 다음과 같이 진행된다.먼저 노드 $\text{D}$를 방문한다. 노드 $\..
109. Depth First Search 그래프 탐색(Graph Traversal)은 트리의 탐색과는 다르다. 서브트리와 같은 개념이 그래프에는 존재하지 않는데다 노드들 사이의 경로도 여러 개 존재할 수 있으므로 트리의 탐색 방법을 그래프에 그대로 적용하는 것은 무리이다. 그래서 그래프는 트리와 다른 탐색 방식을 사용하며, 대표적인 방식은 두 가지가 있다.깊이 우선 탐색(Depth First Search)은 노드를 탐색하고 그 노드와 인접한 노드을 차례로 탐색하는 과정을 재귀적으로 반복하는 탐색 방법이다. 현재 노드에서 탐색할 수 있는 노드를 최대한 탐색하는 방식이라고 생각하면 간단하다. 인접한 노드가 여러 개 있을 때 그 노드들의 탐색 순서에 대한 규칙은 따로 없으며 문제 상황에 맞게 정하면 된다.아래와 같은 그래프가 존재할 때 노드 $\te..
108. Postorder Traversal 트리의 후위 순회(Postorder Traversal)는 노드의 서브트리를 차례로 방문한 다음 노드를 마지막으로 방문하는 순회 방법이다. 트리의 전위 순회, 중위 순회, 후위 순회 결과 중 두 가지를 알면 나머지 한 가지 순회 결과도 알아낼 수 있다. 앞에서 설명한 트리의 후위 순회 결과는 다음과 같다.$\text{I F B G A J C H E D}$ 구현은 다음과 같다.// 인접 리스트를 사용한 경우#importusing namespace std;vectorv, e[100005];void postorder_traversal(int prev, int node){ for(auto &p: e[node])if(p != prev)postorder_traversal(p); v.push_back(nod..
107. Inorder Traversal 트리의 중위 순회(Inorder Traversal)는 노드의 왼쪽 서브트리를 먼저 방문한 다음 노드를 방문하고 노드의 오른쪽 서브트리들을 방문하는 순회 방법이다. 여기서 서브트리의 방향에 대한 내용이 등장하는데 이 방향은 단순히 트리의 구조를 나타내었을 때의 방향이라고 생각해도 무방하다. 만약 자식 노드가 $3$개 이상일 경우 서브트리들 중 하나를 왼쪽 서브트리로, 나머지를 오른쪽 서브트리로 간주한다. 하지만 그런 노드가 있는 트리에서는 서브트리의 방향이 별로 의미 없는 경우가 많기 때문에 일반적으로 중위 순회는 이진 트리에서 수행된다. 앞에서 설명한 트리의 중위 순회 결과는 다음과 같다.$\text{I G B F D A E J C H}$ 구현은 다음과 같다.// 인접 리스트를 사용한 경우#importu..
106. Preorder Traversal 트리의 순회(Tree Traversal)는 루트 있는 트리에 존재하는 각각의 노드를 일정한 규칙에 따라 한 번씩 방문하는 과정을 의미한다. 일반적으로 트리의 순회는 모든 노드가 최대 두 개의 자식 노드를 갖는 이진 트리(Binary Tree) 구조에서 다루어지지만, 이진 트리가 아닌 트리에서도 순회를 할 수 있다. 순회는 루트 노드에서 시작하며 자식 노드에는 순서가 있다고 가정한다. 노드를 방문하는 규칙은 크게 세 가지가 있으며 규칙에 따라 트리 순회의 이름도 달라진다.트리의 전위 순회(Preorder Traversal)는 노드를 먼저 방문하고 각각의 자식 노드를 루트로 하는 서브트리를 차례로 방문하는 순회 방법이다. 다음과 같은 트리가 있을 때 전위 순회는 다음과 같은 순서로 진행된다.루트 노드 $\t..
105. Trees & Graphs Intro 카테고리 H에서는 트리와 그래프에 대한 내용을 다룬다.PS에서 다루는 트리와 그래프는 이산수학적으로 정의된 개념으로 해석학에서 다루는 그래프와는 다르다. 이산수학에서의 그래프를 이해하려면 먼저 가장 기본적인 두 가지 개념에 대해서 알아야 한다.정점(Vertex, V) 또는 노드(Node)는 분할할 수 없는 객체 하나하나를 의미한다. '정점'과 '노드'는 모두 많이 사용되는 용어이며 의미 차이도 크게 두지 않는 편이다.간선(Edge, E) 또는 링크(Link)는 정점과 정점을 연결하는 선을 의미한다. 이쪽도 두 단어에 별다른 차이를 두지 않지만 PS에서는 '간선'이 '링크'에 비해 훨씬 많이 사용된다.정점과 간선이 그래프의 가장 기본적인 구성 요소가 되며, 정점과 간선으로 이루어진 집합을 그래프(Graph..
104. Voronoi Diagram & Delaunay Triangulation 보로노이 다이어그램(Voronoi Diagram)은 $2$차원 좌표평면에 점들이 존재할 때 평면을 그 위치에서 가장 가까운 점에 따라 분할한 것을 의미한다. 다음 그림은 점 $20$개가 있는 보로노이 다이어그램의 예시이다. 보로노이 다이어그램은 거리가 가까운 점들의 수직이등분선을 적절하게 이으면 그릴 수 있다. 들로네 삼각분할(Delaunay Triangulation)은 $2$차원 좌표평면에 점들이 존재할 때 점들을 이어서 여러 개의 삼각형을 만드는데 삼각형의 외접원이 삼각형의 세 꼭짓점 외의 다른 점을 포함하는 경우가 생기지 않게 하는 분할 방법이다. 다음 그림은 점 $10$개가 있는 들로네 삼각분할의 예시이다. 보로노이 다이어그램과 들로네 삼각분할은 쌍대 관계(Duality)에 있으며 둘 중 하나를 ..

티스토리툴바