프로그래밍/Algorithm & Data Structure10 [Algorithm] DFS, BFS 트리 혹은 그래프를 탐색할 때, 두 가지 방법이 있다. 하나는 깊이 우선 탐색(DFS, Depth-First Search), 나머지 하나는 너비 우선 탐색(BFS, Breadth-First Search)이다. DFS 노드 혹은 그래프를 탐색할 때, 두 가지 이상 갈래 길(Branch)이 있을 경우, 한 길을 우선적으로 끝까지 탐색하여 탐색을 완료한 뒤, 다른 길을 탐색하는 알고리즘이다. 핵심은 한 길이다. 쉽게 설명하기 위해 트리로 나타낸 그림을 확인하면 다음과 같다. 그림으로 확인이 가능하듯이 탐색을 할 때 하나의 길을 우선적으로 탐색하고, 완료한 다음 다음 길을 탐색하는 알고리즘이다. 장점 단순하게 현 경로상의 노드만 기억하면 되기 때문에 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을.. 2023. 4. 28. [Data Structure] BST(Binary Search Tree) 이진 트리는 한 노드의 자식 노드가 최대 2개로 이뤄진 트리를 의미한다. 그 중 이진 탐색 트리는 노드가 트리에 추가가 될 때, 자동으로 데이터들의 값을 비교하여 노드의 위치를 정하는 트리를 의미한다. 기본적인 원리는 다음과 같다. 1. 추가되는 노드는 루트 노드에서부터 비교가 된다. 2. 루트 노드의 데이터 보다 크면 오른쪽, 작으면 왼쪽 자식 노드로 간다. 3. 루트 노드의 자식 노드와 데이터를 비교하여 역시나 크면 오른쪽, 작으면 왼쪽 자식으로 향한다. 4. 3의 과정을 반복해서 더 이상 자식 노드가 없을 때까지 이동한 다음, 해당 노드의 자식 노드로 등록이 된다. 위와 같은 과정으로 데이터 20을 가진 노드는 24를 가진 노드의 왼쪽 자식으로 등록이 된다. 밑에는 데이터를 삽입할 때 사용하는 함수.. 2023. 4. 27. [Data Structure] Stack 스택 박스에 물건을 쌓듯이 먼저 들어간 물건이 가장 나중에 나오는 것처럼, 스택의 구조는 위와 같다. 후입선출, 나중에 들어간 데이터가 제일 먼저 밖으로 빠져 나오는 구조이다. 때문에 스택은 Push와 Pop이 핵심 연산이다. class Stack { public: Stack() { stackArr = new int[5];; capacity = 5; top = 0; }; private: int* stackArr; // 스택 배열 int capacity; // 허용량 int top; // 현재 상위 위치 public: void Push(int data); void Pop(); int Top() { return stackArr[top - 1]; } int Size() { return top; } privat.. 2023. 4. 22. [Data Structure] Linked List 링크드 리스트, 연결형 리스트라고 부르는 자료구조이다. 사실 자료구조라고 하기엔 애매한 감이 있지만 배열과 더불어 후에 서술할 다른 자료구조들의 바탕이 되는 자료구조이기 때문에 개념을 집고 넘어가야 할 필요성이 있다. 구조 데이터와 주소를 담는 공간으로 이뤄진 노드들의 연결이다. 주소는 자신의 뒤에 오는 노드의 주소를 담고 있고 때문에 노드를 하나 하나 거쳐서 순차적으로 접근하는 구조를 가지고 있다. 배열은 시작 주소로부터 일정한 크기의 데이터 나열로 된 구조이지만 연결형 리스트는 메모리 주소가 이어진 구조가 아니라 메모리 내에 여러 곳에 분산적으로 퍼져 있는 구조이다. 자신의 뒤로만 접근이 가능하면 싱글, 앞뒤로 접근이 가능하면 더블 링크드 리스트라고 한다. 링크드 리스트의 가장 앞 부분을 헤드/머리 .. 2023. 4. 21. 이전 1 2 3 다음
