본문 바로가기

자료구조 및 알고리즘

 (12)
우선순위 큐 우선순위 큐는 이름에서도 의미하듯 우선순위를 정한 큐이다. 큐의 경우에는 줄서기에 비유한다면 우선순위 큐는 응급실의 응급 상황인 사람이 먼저 들어가는 상황에 비유해보자. 이처럼 우선순위가 부여가 된다. 앞서 배운 큐의 핵심 연산은 2가지이다. enqueue() 데이터 삽입 dequeue() 데이터 삭제 이와 마찬가지로 우선순위 큐의 핵심 연산도 2가지 모두 동일하다. 반면에 연산의 결과는 차이가 있다. 큐의 경우에는 먼저 들어간 데이터가 먼저 나오지만 우선순위 큐는 우선순위가 더 높은 데이터가 먼저 나온다. 우선순위 큐를 구현하기 위해서 아래와 같은 3가지의 방법이 있다. ・배열 기반 구현 ・연결 리스트 기반 구현 ・힙 기반 구현 우선 배열과 연결 리스트를 이용하면 간단하게 구현할 수 있다. 1) 배열의..
이진 트리 이진 트리는 배열과 리스트로 구현이 가능하다. 이진 트리에서 이해하기 쉬운 리스트로 구현할 예정이다. 배열 기반 트리는 나중에 나올 '힙'이라는 자료 구조에서 알아보도록 하자. 이 포스트에서는 리스트를 이용하여 이진 트리를 구현해볼 것이다. 노드의 형태 먼저 아래의 그림을 보면 노드의 형태가 나온다. 이진 트리의 정의를 보면 "노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다." 라고 정의되어 있다. 그러므로 아래의 그림은 두 가지 형태는 같은 노드로 표현이 된다. 이진 트리의 연결 아래의 그림을 보면 B노드를 생성한 후 A 노드의 왼쪽 자식으로 연결해준 모습을 보여준다. 연결의 경우 간단하기 때문에 다른 언급은 하지 않겠다. 이진 트리의 순회 트리의 순회 방..
트리 앞에서 봤던 자료구조들은 전부 선형적인 자료구조였다. 지금 알아볼 트리는 비선형적인 자료구조이기때문에 많이 다르게 느껴질 수 있다. 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다. 나무처럼 가지를 늘려가며 뻗어나가는 것이다. 일상생활에서도 자주 접할 수 있다. 아래의 그림으로 트리가 어떤 형태인지 알아보자. 트리의 기본적인 용어 노드 : 트리의 구성요소에 해당하는 A, B, C, D, E, F 요소들을 노드라고 한다. 간선 : 노드와 노드를 연결하는 선을 간선이라 한다. 루트 노드 : 트리 구조에서 최상위에 존재하는 A노드를 루트 노드라고 한다. 단말 노드 : 잎 노드라고도 불리며 C, D, E, F노드를 단말 노드라고 한다. 내부 노드 : 단말 노드를 제외한..
큐 (리스트를 이용한 구현) 지난 포스팅에서는 배열을 이용하여 큐를 구현해보았다. 이번 장에서는 리스트를 이용하여 큐를 구현해볼 예정인데 큐는 배열을 사용하였을 경우 front를 기반으로 한 칸씩 이동하며 데이터를 삭제하였다. 포인터를 이용할 경우에는 front가 비어있을 경우 큐가 비었다고 볼 수 있다. 아래의 그림은 최초의 큐 형태이다. ① 데이터 삽입을 보자. 첫 번째 노드가 추가가 될 경우 Front와 Rear는 첫 번째 노드를 가리키게 되며 두 번째 노드의 추가로부터는 Rear가 새로운 노드를 가리키게 추가함으로써 데이터 삽입이 완료가 된다. ② 데이터의 삭제를 보자. 삭제할 노드를 임시 변수에 저장해둔 후 Front를 다음 위치를 가리키게 해준다. 그 이후 임시 변수에 담아두었던 노드를 삭제한 후 데이터를 반환한다. 삭제..
큐 (배열을 이용한 구현) 큐는 앞서 설명한 스택과 함께 언급되며 비교되는 자료구조이다. 스택은 먼저 들어간 데이터가 나중에 나오는 구조(LIFO)이지만 큐는 먼저 들어간 데이터가 먼저 나온다. 이는 일상생활에서도 자주 접할 수 있다. 버스를 타기위해 줄을 서는데 먼저 선사람부터 먼저 타는 상황을 떠올려보자. 이렇듯 큐의 구조는 FIFO(First In First Out)의 구조로 이루어진다. 들어가기에 앞서 1. Front와 Rear라는 용어가 나오는데 Front는 큐의 머리를 뜻하며 Rear는 큐의 꼬리를 뜻한다. 2. 스택은 Push()와 Pop()으로 삽입, 삭제를 하지만 큐의 경우에는 Enqueue()와 Dequeue()로 삽입, 삭제가 이루어진다. 큐의 구현에 대한 원리 ① 데이터 삽입을 보자. 큐는 뒤에서 넣고 앞으로..
스택 (리스트를 이용한 구현) 리스트를 이용한 구현 앞서 구현한 배열을 리스트로 변경할 경우 연결 리스트의 특징을 그대로 가져오게 된다. 리스트라고 말하면 복잡해 보이지만 "역순으로 삭제가 가능한 리스트이다"라고 생각한다면 그다지 어렵지 않다. 아래의 내용은 비어있는 초기의 리스트 스택 형태이다. 들어가기에 앞서 1. 리스트 구현과 동일하게 노드가 존재하며 노드는 데이터와 다음 위치를 가리킬 수 있는 노드를 가지고 있다. 2. 스택은 top이 아닌 head로 변경이 되며 이는 현재 위치를 가리키는 변수이다. ① 데이터 삽입을 보자. 배열을 이용한 스택과 동일하게 Push()라는 함수 호출로 값을 삽입한다. 먼저 10을 추가해보자. 10을 추가할 경우 head는 새로운 노드를 가리키게 되며 nextNode는 자기 자신의 이전 노드를 가..
스택 (배열을 이용한 구현) 스택은 한쪽 끝에서만 들어가고 한쪽 끝에서만 삽입과 삭제가 이루어지는 자료구조이다. LIFO(Last In First Out)로 가장 먼저 들어간 것이 가장 나중에 나오는 구조이다. 쉽게 생각하기 위해서 프링글스 통을 떠올려보자. 가장 밑에 있는 감자칩은 가장 먼저 들어갈 것이다. 이 감자칩을 빼내려면 위에 있는 감자칩을 모두 빼낸 후 가장 나중에 나올 수 있다. 이 구조가 스택의 핵심이다. 배열을 이용한 구현 들어가기에 앞서 1. 5개의 배열을 이용한 스택을 구현한다. 2. top이라는 용어가 나오는데 top은 가장 최근에 저장된 위치를 가리키는 변수이다. 비어있는 상태일 경우에는 -1을 가리킨다. ① 데이터 삽입을 보자. 스택은 Push()라는 함수 호출로 값을 삽입한다. 가장 먼저 10이라는 값을 ..
단방향 연결 리스트 연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이번 내용에서 배워볼 방법은 동적 할당으로 연결 리스트를 구현해볼 예정이다. 기본 개념만 익힐 것이니 응용은 자신의 생각으로 더 나은 구조로 구현하길 바라겠다. 들어가기 전 노드와 리스트의 형태 1. 노드 - 노드란, 리스트에서 연결되는 하나의 데이터 정보를 말하는데 어떠한 데이터를 담을 공간과 자신의 다음 위치를 가리킬 포인터를 노드라고한다. 이해하기 쉽도록 아래의 그림을 떠올리면 된다. 2. 리스트 - 리스트는 위의 노드를 연결한 모양인데 꼬리에서 꼬리를 무는 형태로 그려진다. 수많은 구현 방법이 있겠지만 지금 구현하는 방법은 head와 tail 즉, 머리(시작점)와 꼬리(끝점)라는 멤..

티스토리툴바