본문 바로가기
반응형

CS/자료구조

 (12)
[ 자료구조 ] 이진 탐색 트리(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. 부모-자식 노드 직접 연결된 두 꼭지점은 부모-자식 관계를 가진다. 여기서 위에 위치한 노드를 ‘부모 노드’, 아래에 위치한 노드를 ‘자식..
[ 자료구조 ] 큐(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 노드는 끝점을 의미한다. 이중 연결 리스트는 양방향으로 움직일 수 있는 장점이 있지만 그만큼 구현하기 위해 추가되는 요소들도 많다. 당장 단일 연결 리스트와 비교해봤을 때 구..
[ 자료구조 ] 연결 리스트(Linked List) : 단일 연결 리스트 연결 리스트를 배우기 전에 왜 배우는지를 먼저 알고 가자. 결론부터 말하면 연결 리스트는 배열의 단점을 극복하기 위해 나온 자료구조다. 배열의 장단점에는 무엇이 있는지 먼저 알아보고, 연결 리스트의 가장 단순한 구조인 '단일 연결 리스트'를 구현하는게 오늘의 학습목표다. 배열의 특징, 연결리스트 구조 배열은 인덱스를 통해 데이터에 직접적인 접근이 가능하기 때문에 접근이 아주 빠르다는 장점이 있다. 그러나 배열 내의 데이터 이동 및 재구성이 굉장히 힘들다. 배열에서 원소를 하나 삭제하려면 그 뒤에 있는 원소들을 전부 한 칸씩 당겨야 하고, 원소를 삽입하려면 그 뒤에 있는 원소들을 전부 한 칸씩 밀어야 한다. 또한 배열의 크기는 초기에 설정하면 이후에 변경 불가능하다. 초기에 설정한 크기를 넘어가면 데이터 ..
반응형

티스토리툴바