기록공간

정렬은 순서가 없는 사물들을 순서대로 재배열하는 것을 뜻한다. 순서에는 오름차순(ascending order)과 내림차순(descending order)이 있다. 다음 그림은 순서대로 오름차순과 내림차순의 예시를 보여준다. 예를 들면, 책은 '제목'이나 '저자명', 그리고 '발간 연도' 등을 기준으로 오름차순이나 내림차순으로 정렬할 수 있다. 인터넷 쇼핑몰에서는 물건들을 '판매 인기순'이나, '가격 낮은 순', '상품 평순' 등으로 정렬할 수 있고, 엑셀 프로그램도 성적처리를 하는 경우 '학번', '성적', '실습 점수' 등의 기준으로 정렬할 수 있다. 정렬은 자료 탐색에서 매우 중요하다. 예를 들면, 사전에서 우리가 단어를 쉽게 찾을 수 있는 것은 단어들이 알파벳순으로 정렬되어 있기 때문이다. 만약 사..

그래프란? 그래프(Graph)는 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다. 예를 들어, 지하철 노선도는 많은 역들이 어떻게 연결되어 있는지를 알려주며, SNS의 인맥 지도는 사람들의 복잡한 친구 관계를 표현한다. 그래프로 표시된 지도를 이용해 어떤 도시에서 다른 도시로 갈 수 있는 가장 가까운 경로를 찾을 수도 있다. 그래프는 선형 자료구조들이나 트리보다 더 일반화 된 자료구조를 제공하고 많은 분야에서 널리 사용하고 있다. 이와 같은 예들은 공통적으로 다양한 객체들이 서로 연결되어 있는 구조를 갖는다. 그래프는 이런 구조를 표현할 수 있는 훌륭한 논리적인 도구이다. 그래프의 역사 그래프는 수학자 오일러(Euler)에 의해 처음 창안되었다. 오일러는 위 그림과 같은 지형에서 "모든..

컴퓨터에서는 우선순위 개념이 종종 필요할 때가 있다. 예를 들면, 운영 시스템에서 시스템 프로세스는 응용 프로세스보다 더 높은 우선순위를 갖는다. 따라서 자료구조에서도 이러한 우선순위를 지원하는 것이 필요하다. 우선순위 큐는 이러한 우선순위의 개념을 큐에 도입한 자료구조이다. 보통의 큐는 먼저 들어온 데이터가 먼저 나가는 구조(FIFO)인데 비해, 우선 순위 큐는 모든 데이터가 우선순위를 가지고 있고, 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력되는 구조다. 우선순위 큐는 사실 가장 일반적인 큐로 볼 수 있다. 이것은 우선순위 큐를 사용하여 스택이나 큐를 얼마든지 구현할 수 있기 때문이다. 예를 들어 데이터가 들어온 시점 기준으로 빠른 것을 높은 우선순위로 잡으면 큐처럼 동작하고, 반대로 ..

재귀 또는 순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 재귀는 많은 문제들을 해결하는데 독특한 개념적인 해결책을 제공한다. 재귀를 이용하여 만든 재귀 함수는 어떻게 문제를 풀어가는지에 대해 직관적으로 알 수 있도록 해주어 가독성을 높인다는 장점이 있다. 하지만 단점도 존재한다. 함수를 호출하면 그 함수가 끝날때 어디로 복귀해야 한다는 복귀주소를 스택에 쌓게 되는데, 재귀함수는 재귀하는 횟수가 많아 질수록 이 쌓이는 복귀주소가 기하급수적으로 늘어나게 된다. 이로인해 스택 오버플로우가 발생하면 프로그램이 뻗는 현상이 나타난다. (이를 해결하기 위해 동적 계획법(Dynamic Programming)이라는 알고리즘을 사용한다) 재귀는 트리 구조에서 정말 많이 사용..

컴퓨터의 탐색은 레코드(Record)의 집합에서 특정한 레코드를 찾아내는 작업을 말한다. 레코드는 하나 이상의 필드(Field)로 구성된다. 예를 들어, 각 학생의 정보를 이진트리의 각 노드에 저장한다고 생각해 보자. 학생정보 구조체가 레코드에 해당하고, 구조체의 멤버 변수인 학번, 이름, 주소, 주민등록번호 등이 필드에 해당한다. 레코드를 서로 구별하려면 필드들 중에서 서로 중복되지 않는 고유한 값을 가지는 필드가 있어야 하는데, 이를 키(Key)라고 부른다. 학생 정보에서는 주민등록번호나 학번이 여기에 해당된다. 결국 탐색은 주어진 키를 가진 레코드를 찾는 작업이고, 레코드가 노드에 저장되는 이진탐색트리에서는 주어진 키를 가진 노드를 찾아야 한다. 이진탐색트리의 정의 이진탐색트리(BST, Binary..

트리란? 트리(Tree)는 계층 구조(Hierarchical Structure)로 자료를 저장하는 자료구조이다. 여기서 말하는 계층 구조란 트리를 구성하는 노드가 부모-자식(Parent-Child) 관계라는 의미이다. 즉 특정 부모 노드 하나에 여러 개의 자식 노드들이 연결되는 구조를 말한다. 이러한 구조로 노드들이 연결된 모습이 마치 마치 나무와 같아 트리라는 이름이 붙여졌다. 그래서 앞으로 살펴 볼 용어 중 나무의 부분에 대한 명칭을 가져온 것이 있다. 예를 들어, 컴퓨터의 폴더 구조나 가족의 가계도, 직장의 조직도 등과 같이 계층적인 관계를 가진 자료를 표현하고 싶은 경우 선형 자료구조만으로 충분하지 않다. 트리는 이러한 계층적인 자료를 표현하는데 이용되는 자료구조이다. 트리의 용어들 트리와 관련된..

이진 트리의 문제점 이진 트리의 문제점은 한쪽으로 치우친 형태로 트리 구조가 만들어질 수 있다는 것이다. 이렇게 되면 트리 구조가 아니라 일반적인 연결 리스트와 별 차이가 없는 구조가 되어 이진 트리의 장점을 전혀 발휘할 수 없게 된다. 위와 같이 이진 트리가 구성되면 실제 이진 트리의 장점인 노드 검색 시 성능이 O(logN)이 된다는 것을 보장할 수 없다. 만약 위 그림처럼 트리가 구성되어 있다면 14를 찾기 위해서는 트리의 맨 밑까지 내려가야 한다. 즉, 9번의 노드 검사가 필요하게 된다. 이처럼 위 트리 구조는 최악의 경우에 성능이 O(N)이다. 이러한 문제를 해결하기 위한 방법 중 하나인 AVL 트리에 대해서 본격적으로 알아보도록 하자. AVL 트리 AVL 트리는 전체 트리의 구조가 균형이 맞도..

큐란? 큐(Queue)는 사전적인 정의로 '긴 열', '대기열'를 뜻한다. 길게 늘어져 있는 줄을 생각하면 편하다. 큐(Queue)는 일상생활에서도 자주 접하게 된다. 예를 들면 극장에서 표를 사려고 길게 늘어진 사람들의 줄, 또는 도로 위에서 신호를 기다리며 길게 늘어선 차들 등이 있다. 이러한 대기열에는 한 가지 중요한 특징을 가지고 있다. 그것은 바로 '선입선출(First-In First-Out : FIFO)'이다. 새치기라는 예외적인 상황을 제외하고 정상적인 경우라면 언제나 먼저 도착한 사람이 먼저 나가게된다. 자료구조에 사용되는 큐는 이러한 줄 서기의 특징을 그대로 가지고 있다. 큐는 추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터가 나오는 자료구조이다. 먼저 저장된 데이터가 나중..