개발윗미

이진 트리는 데이터의 탐색 속도 증진을 위해 사용하는 구조이다. 완전 이진 트리가 아닌 이진 트리는 배열로 표현하기 어렵기 때문에 포인터(Pointer)를 사용하는데, 포인터를 통해 특정한 Root에서 자식 노드로 접근할 수 있다. 이진트리 데이터 탐색 순회 방식은 전위순회, 중위순회, 후위순회 총 3가지가 존재한다. 1. 전위순회 (Preorder Traversal) (1) 자기 자신을 처리한다. (2) 왼쪽 자식을 방문한다. (3) 오른쪽 자식을 방문한다. 2. 중위순회 (Inorder Traversal) (1) 왼쪽 자식을 방문한다. (2) 자기 자신을 처리한다. (3) 오른쪽 자식을 방문한다. 3. 후위순회 (Postorder Traversal) (1) 왼쪽 자식을 방문한다. (2) 오른쪽 자식을..

깊이 우선 탐색은 특정한 데이터를 탐색할 때 깊이를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. 즉, 깊이 우선 탐색은 데이터를 보다 깊은 것을 우선으로 하여 탐색한다. 깊이 우선 탐색은 스택을 이용하는데, 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문에 스택을 사용하지 않고 단순히 재귀함수만을 사용해서도 구현이 가능하다. 그림과 같이 스택의 최상단 노드를 확인하고 해당 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 넣고 방문처리한다. 그림에 대해 구체적으로 설명하자면, (1) 먼저 스택에 시작 노드인 1을 삽입하고 방문처리한다. (2) 1과 인접한 노드 중 방문하지 않은 2를 스택에 삽입하고 방문처리한다. (3) 2와 인접한 노드 중 방문하지 않은 3을 스택에 삽입하고 방문처리한다. ..

너비 우선 탐색은 특정한 데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. 즉, 어떠한 시작점이 있을 때 그 시작점과 가까운 것을 우선으로 탐색을 한다. 너비 우선 탐색은 큐를 이용하는데, 큐는 먼저 들어온 데이터가 먼저 나간다는 점에서 너비 우선 탐색이 가능하도록 해준다. 그림과 같이 큐에서 하나의 노드를 꺼내고 해당 노드와 인접한 노드 중 방문하지 않은 노드를 방문한다. 그 후 순서대로 큐에 값을 삽입하는 과정을 반복한다. 그림에 대해 구체적으로 설명하자면, (1) 먼저 큐에서 1을 꺼낸다. (2) 1과 인접한 노드 중 방문하지 않은 2와 3을 방문처리한다. (3) 2를 꺼내고 2와 인접한 노드 중 3은 이미 방문했기 때문에 넘어가고 방문하지 않은 4와 5를 방문처리한다. ..

큐 또한 스택과 같이 자료를 표현하고 처리하는 방법인데 큐는 입구와 출구가 다르기 때문에 은행 창구와 같이 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조이다. 빈 큐가 있다고 가정하고, push(1) --> 1 --> 맨 처음 1을 삽입한다. push(2) --> 1 2 --> 2를 삽입한다. push(7) --> 1 2 7 --> 7을 삽입한다. pop() --> 2 7 --> 가장 먼저 들어간 1이 나간다. push(4) --> 2 7 4 --> 4를 삽입한다. pop() --> 7 4 --> 가장 먼저 들어간 2가 나간다. [예제] #include #include using namespace std; int main() { queue q; q.push(7); q.push(5); q.push(4)..

스택은 자료를 표현하고 처리하는 방법인데 입구와 출구가 하나밖에 없는 상태이기 때문에 택배 상하차와 같이 가장 나중에 들어온 데이터가 가장 먼저 나온다. 빈 스택이 있다고 가정하고, push(1) --> 1 --> 맨 처음 1을 삽입한다. push(2) --> 1 2 --> 2를 삽입한다. push(7) --> 1 2 7 --> 7을 삽입한다. pop() --> 1 2 --> 가장 마지막에 들어간 7이 나간다. push(4) --> 1 2 4 --> 4를 삽입한다. pop() --> 1 2 --> 가장 마지막에 들어간 4가 나간다. [예제] #include #include using namespace std; int main() { stack s; s.push(7); s.push(5); s.push(4)..