본문 바로가기

CS

(46)

[ 자료구조 ] 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree)는 이진 트리의 특수 케이스로 아래와 같은 특징을 가진다. 1. 각 노드는 고유한 값을 가진다. 2. 모든 노드의 왼쪽 서브트리는 자신보다 작은 값을 가지고, 오른쪽 서브트리는 자신보다 큰 값을 가진다. 개념 자체는 매우 간단하다. 그런데 구현은 생각보다 까다롭다. 내가 공부하는 책에서는 좀 가볍게 넘어가는 부분이 있어서 대학 강의자료를 참고했다. 손으로 먼저 이진 탐색 트리를 만들어보고, 구현까지 해보는게 목표다. 포인터에 대한 이해가 확실하게 되어있지 않으면 구현 코드를 이해하기 어려울 수 있다. 손으로 직접 해보기 J , E , T , A , H , M , V , P , N 을 순서대로 트리에 삽입해보자. 루트 노드부터 시작 1) 삽입 값이 현재 노..

[ 자료구조 ] 이진 트리와 순회 이진 트리는 모든 노드가 최대 두 개의 자식 노드를 갖는 트리다. 아래와 같은 특징을 갖는다. 1. 각 노드는 최대 2개의 자식을 갖는다. 2. 각 노드의 자식은 왼쪽 자식과 오른쪽 자식으로 구분된다. 이진 트리는 왼쪽 자식과 오른쪽 자식을 엄격하게 구분한다. 이게 무슨 뜻이냐 하면 원소가 같아도 위치에 따라 다른 트리로 분류될 수 있다는 뜻이다. 예를 들어 아래 두 개의 트리는 서로 다른 이진 트리다. 이진 트리는 그 구조에 따라 다섯 가지 유형으로 나뉜다. 하나씩 살펴보자. 이진 트리 종류 1. 포화 이진 트리(Perfect Binary Tree) : 모든 중간 노드가 두 개의 자식을 가지는 이진 트리. 포와 이진 트리에서 Level n 의 노드 수는 (2^n) 이라는 특징이 있다. 2. 완전 이진 ..

[ 자료구조 ] 트리 용어 정리 트리(Tree)는 원소들이 부모-자식의 관계로 저장되는 노드(nodes)들의 집합이다. 비순환적으로 연결되어 있는 그래프로 이해해도 무관하다. 트리를 공부하기 전에 트리와 관련된 용어를 정리할 필요가 있어서 이 글에서는 트리 용어만 다룬다. 트리에는 여러 종류의 노드가 존재한다. 노드란 트리의 꼭지점을 의미한다. 노드의 특성에 따라 이름이 부여되는데, 우리가 살펴볼 노드는 아래와 같다. 각각 어떤 특성이 존재하는지 하나씩 알아보자. 부모 노드, 자식 노드, 루트 노드, 리프 노드(외부 노드), 중간 노드(내부 노드), 조상 노드, 자손 노드 노드(Node) 종류 1. 부모-자식 노드 직접 연결된 두 꼭지점은 부모-자식 관계를 가진다. 여기서 위에 위치한 노드를 ‘부모 노드’, 아래에 위치한 노드를 ‘자식..

[ 알고리즘 ] 이분탐색(Binary Search), upper_bound, lower_bound (C++) 1. 이분탐색 원리 이분탐색은 오름차순 또는 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법이다. 정렬된 배열에서 특정 값을 찾을 때 정중앙에 위치한 값을 활용하면 아주 빠른 속도로 탐색을 끝낼 수 있다. 아래 그림을 보자. 배열은 오름차순으로 정렬되어 있다고 가정한다. 배열의 시작점과 끝점의 정중앙에 위치한 값을 '중앙값'이라고 부르겠다. 만약에 그림과 같이 '탐색값 < 중앙값' 이면 중앙값의 오른쪽 부분은 고려할 필요가 없다. 오름차순으로 정렬되어 있기 때문이다. 따라서 이제 끝점은 중앙값이서 1을 뺀 위치가 된다. 끝점의 위치가 이동했으므로 중앙값의 위치도 아래 그림과 같이 이동한다. 이번에는 '중앙값 < 탐색값' 이므로 중앙값의 왼쪽 부분은 볼 필요가 없다. 따라서 시작점은 중앙값에 1을 더해준..

[ 자료구조 ] 큐(Queue) 큐(Queue) 큐는 선입선출(FIFO: First-In First-Out)의 원리에 따라 삽입과 삭제를 수행하는 자료구조다. 데이터 삽입을 enqueue라 하고, 데이터 삭제를 dequeue라고 한다. 그런데 흔히 삽입 및 삭제를 push, pop으로 부른다. 스택과 비교해서 보기를 바란다. 스택은 가장 먼저 들어온 데이터가 가장 마지막에 나가지만, 큐는 가장 먼저 들어온 데이터가 가장 먼저 나간다. 이러한 자료구조가 왜 필요할까? 어떻게 활용할 수 있을까? 가장 대표적인 예시는 '스케줄링'이라고 생각한다. 스케줄링은 쉽게 말해서 '줄 서기' 규칙이다. 마트에서 줄을 서는 경우를 예로 들어 보자. 줄에 가장 먼저 선 사람이 계산을 가장 먼저 하는 것은 당연하다. 티켓팅도 마찬가지다. 가장 먼저 들어온 ..

[ 자료구조 ] 스택(Stack) 스택 (Stack) 스택은 후입선출(LIFO: Last-In First-Out)의 원리에 따라 삽입과 삭제를 수행하는 자료구조다. 스택을 직역하면 '무더기'라는 뜻인데 말그대로 무더기처럼 쌓아 올리고, 하나씩 제거한다. 여기서 데이터 삽입을 push라 하고, 데이터 삭제를 pop이라 한다. 굉장히 간단한 자료구조다. 스택은 후입선출 구조이기 때문에 가장 마지막에 들어온 데이터가 가장 먼저 나간다. 반대로 가장 먼저 들어온 데이터는 가장 마지막으로 나간다. 위 그림만 봐도 쉽게 이해할 수 있을 것이다. 이러한 자료구조가 왜 필요할까? 어떻게 활용할 수 있을까? 스택의 활용 예시로 두 가지만 살펴보자. 먼저 인터넷 브라우저에서 '뒤로가기' 기능을 예로 들 수 있다. 구현할 수 있는 방법은 많겠지만 스택을 사..

[ 자료구조 ] 연결 리스트 : 원형 연결 리스트 연결 리스트의 마지막! 원형 연결 리스트에 대해 알아보자. 구조, 구현할 기능, 구현 순서로 진행된다. 원형 연결 리스트 1. 구조 원형 연결 리스트는 단일 연결 리스트와 거의 똑같다. 단일 연결 리스트에서 tail의 포인터를 head 향하도록 하면 원형 연결 리스트가 된다. 시작과 끝을 가지고 있기 때문에 기준점 역할을 하는 노드가 필요한데, 이런 역할을 하는 노드를 'cursor'라고 부른다. back은 cursor의 원소, front는 cursor->next의 원소다. 2. 클래스 정의 노드 클래스 (CNode) class CNode{ private: string elem; // 노드 원소값 CNode* next; // 다음 노드 friend class CircleList; }; 연결 리스트 클래스..

[ 자료구조 ] 연결 리스트 : 이중 연결 리스트 저번 글에 이어서 이중 연결 리스트와 순환 연결 리스트를 구현해보자. 저번 글과 마찬가지로 그림으로 구조를 먼저 살표보고, 어떤 기능을 구현할지 명시하고, 세부적인 기능을 구현한다. 이중 연결 리스트 1. 구조 각 노드는 데이터와 두 개의 포인터를 가지고 있다. next 포인터는 다음 노드를, prev 포인터는 이전 노드를 가리킨다. 따라서 단일 연결 리스트와는 다르게 양방향으로 이동할 수 있는 특징이 있다. 프로그래밍을 단순화하기 위해 양 끝에 더미 노드를 추가하는 것이 좋다. header 노드는 시작점을 의미하고, trailer 노드는 끝점을 의미한다. 이중 연결 리스트는 양방향으로 움직일 수 있는 장점이 있지만 그만큼 구현하기 위해 추가되는 요소들도 많다. 당장 단일 연결 리스트와 비교해봤을 때 구..

이전 1 2 3 4 ··· 6 다음

티스토리툴바