C++ Programming/알고리즘 정리8 [C++] 깊이 우선 탐색(DFS : Depth First Search) 이번 시간에는 깊이 우선 탐색에 대해 알아보도록 하겠다. 깊이 우선 탐색(DFS)는 탐색을 할 때 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다. 이러한 깊이 우선 탐색은 맹목적으로 각 노드를 탐색할 때 주로 사용된다. 이전에 배웠던 너비 우선 탐색에서는 큐를 사용하였고, 이번 깊이 우선 탐색에서는 스택을 사용한다. 컴퓨터는 항상 스택의 원리를 사용하기 때문에 사실 스택을 사용하지 않아도 된다. 맨 처음에 시작 노드(Start Node)를 스택에 넣어주고 시작 노드를 방문했음을 알리는 방문 표시를 한다. 그 다음에는 다음의 알고리즘을 반복한다. 1. 스택의 최상단 노드를 확인한다. 2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드.. 2020. 5. 7. [C++] 너비 우선 탐색(BFS : Breath First Search) 이번 시간에는 너비 우선 탐색에 대해 알아보도록 하겠다. 너비 우선 탐색(BFS)은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. '맹목적인 탐색'을 할 때 사용할 수 있는 탐색 기법으로, '최단 경로'를 찾아준다는 점에서 '최단 길이'를 보장해야할 때 많이 사용한다. 큐를 사용한다. 시작점에서부터 가까운 것부터 탐색을 하겠다는 것이다. 맨 처음에 시작 노드(Start Node)를 큐에 삽입하면서 시작한다. 시작 노드를 방문했다고 표시를 해놓고, 그 이후부터 다음의 알고리즘을 반복한다. 1. 큐에서 하나의 노드를 꺼낸다. 2. 해당 노드에 연결된 노드들 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다. stl queue를 사용해서 구현해본 코드이다. #include #.. 2020. 5. 7. [C++] 큐(Queue) 이번 시간에는 큐(Queue)에 대해 알아보도록 하겠다. 큐(Queue)는 스택과 달리 선입선출(FIFO, First In First Out) 구조이다. stl queue의 함수들을 살펴보도록 하겠다. 함수 이름 함수 기능 push(element) 큐의 맨 뒤에 원소를 추가 pop() 큐의 맨 앞의 원소를 삭제 front() 큐의 맨 앞의 원소를 반환 back() 큐의 맨 뒤의 원소를 반환 empty() 큐가 비어있으면 1, 큐가 비어있지 않으면 0 반환 size() 큐에 들어있는 원소의 개수를 반환 stl queue를 사용한 코드를 살펴보도록 하겠다. #include #include using namespace std; int main() { queue q; q.push(7); q.push(5); q... 2020. 5. 7. [C++] 스택(Stack) 이번 시간에는 스택에 대해 알아보도록 하겠다. 스택(Stack)과 큐(Queue)는 컴퓨터 공학에서 가장 기본이 되는 자료구조이다. 스택은 택배 상하차, 큐는 은행 창구에 비유되기도 한다. 이번 시간에는 stl stack을 쓰는 방법을 알아보겠다. stack을 직접 구현하는 것은 다음에 추가하도록 하겠다. #include #include using namespace std; int main() { stack s; s.push(7); s.push(5); s.push(4); s.pop(); s.push(6); while (!s.empty()) { cout 2020. 5. 7. 이전 1 2 다음