DFS(Depth-First Search)
DFS(Depth-First Search) 깊이 우선 탐색. 이름 그대로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘을 말한다. 정확하게는 DFS는 깊은 부분을 끝까지 탐색하다가, 막히면 다시 돌아와서, 다른 부분을 깊게 탐색한다. DFS의 탐색 순서 DFS는 A에서 출발해서 B를 선택하여 탐색을 시작하고, B에서 이미 A는 탐색했으니, D로 넘어간다. 그리고 D에서는 이미 B를 탐색했으니, H로 넘어가게 되고, 이제 더 이상 방문할 인접 노드가 없는 H에서는 자신의 앞전 노드인 D로 돌아가고, 방문할 수 있는 노드인 I로 이동한다. 그리고 I는 거꾸로 D로 돌아가고, 이제 더 이상 방문할 노드가 없으니, B로, 그 다음은 A로 거슬러 올라간다. 그리고 A에서는 이제 반대편 노드를 탐색하기 시작하..
2023. 5. 19.
[선형구조] 큐(Queue), 덱(Deque)
큐(Queue) 큐는 FIFO(First In, First Out) 선입선출의 형태를 가지는 자료구조이다. 스택처럼 끝부분에서 삽입, 삭제 연산이 이루어지지만 스택은 삽입, 삭제가 같은 쪽에서만 이루어지고 큐는 서로 다른 쪽에서 이루어진다는 차이를 가진다. 큐의 입구를 Rear, 출구를 Front라고 한다. 그리고 데이터를 삽입되는 연산을 Enqueue, 데이터를 삭제되는 연산을 Dequeue라고 한다. 큐는 BFS를 구현할 때, 아주 유용하게 쓰인다. 또한 큐 역시 스택과 마찬가지로 연결 리스트를 사용하여 구현하며, 삽입, 삭제 연산은 O(1)이다. 덱(Deque) 덱은 큐의 변형판으로, Double-Ended-Queue의 약자이다. 즉, 말뜻처럼 큐가 양쪽에서 가능하다는 것인데, 양쪽 끝에서 데이터의..
2023. 5. 18.
