'자바로 배우는 쉬운 자료구조' 요약

‘자바로 배우는 쉬운 자료 구조’ 라는 책을 읽고 내용을 요약하였습니다.

 

자료구조

자료구조란?

자료를 컴퓨터에서 어떻게 표현하고, 표현한 자료를 어떻게 좀 더 효율적으로 저장하고 처리할 것인지에 대한 논리적인 구조와 프로그램적인 처리 방법 등이 컴퓨터분야에서의 자료구조입니다.

 

자료구조의 분류

단순 구조

정수, 실수 , 문자, 문자열 등의 데이터 타입에 해당하는 자료구조

선형 구조

자료간의 앞뒤 관계가 일대일로 고정되어 있는 자료구조

비선형 구조

자료 간에 일대다 또는 다대다의 계층 구조나 망구조를 갖는 자료구조

파일 구조

서로 관련 있는 필드들로 구성된 레코드의 집한인 파일에 대한 자료구조로서, 보조기억장치에 데이터가 실제로 기록되는 자료구조

자료구조의 기본 표현 방식

자료구조의 기본 표현 방식에는 순차 자료구조 방식과 연결 자료구조 표현 방식이 있습니다.

순차 자료구조 방식

원소들 간의 논리적인 순서와 메모리에 저장하는 물리적인 순서가 같은 방식입니다.

선형 리스트

데이터를 나열한 목록을 리스트라고 합니다. 선형 리스트는 순서를 가지고 있는 리스트입니다.

선형 리스트의 특징은 다음과 같습니다.

• 순차 자료구조 방식에서는 원소들이 순서대로 연속하여 저장됩니다.
• 선형 리스트에서 삽입이나 삭제가 발생하여 원소들의 논리적 순서가 변경되면 그에 따라 물리적인 순서도 변경되어야 하기 때문에 원소들의 위치를 물리적으로 이동시키는 작업이 필요합니다.
• 선형 리스트를 순차 구조로 구현하기 위해 배열을 사용하는데, 배열은 <인덱스, 원소> 의 쌍으로 구성되어 메모리에 연속적으로 할당됩니다.

 

연결 자료구조 표현 방식

순차 자료구조 방식에서의 자리 이동 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료구조입니다. 다음 원소의 주소에 의해 순서가 연결되는 방식이기 때문에 순차 자료구조 방식과 달리 메모리에 저장되는 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않습니다.

노드

연결 자료구조 방식에서 원소는 연결될 다음 원소에 대한 메모리 참조값을 저장해야 하기 때문에 <원소, 주소 참조값>을 기본 단위로 하여 저장하는데, 이러한 단위 구조를 노드 라고 합니다. 노드는 값을 저장하는 데이터 필드와 다음 노드의 주소를 저장하는 링크 필드로 구성됩니다.

연결 리스트

리스트를 연결 자료구조 방식으로 표현한 리스트로서 연결하는 방식에 따라 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트가 있습니다.

원형 연결 리스트

마지막 노드의 링크 필드에 첫번째 노드에 대한 참조값을 저장하여 구성합니다. 단순 연결 리스트는 이전 노드에 접근 하려면 현재 위치와 상관없이 항상 리스트의 첫번째 노드부터 다시 시작해야 하지만, 원형 연결 리스트는 링크를 따라 계속 순회하면 이전 노드에 접근할 수 있습니다.

이중 연결 리스트

원형 연결 리스트도 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 하는 문제가 있기 때문에 양쪽 방향으로 순회할수 있도록 연결한 리스트입니다. 두 개의 링크 필드와 한개의 데이터 필드로 구성됩니다.

 

응용 자료구조

스택

접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 구조입니다. 같은 구조와 크기의 자료를 top 이라고 정한 한 곳으로만 쌓을 수 있고, top 으로만 접근하도록 제한하여 만든 자료구조입니다. 스택에서 원소를 삽입하는 연산을 push 라고 하고, 원소를 삭제하는 연산을 pop 이라고 합니다.

가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO) 방식으로 동작합니다.

스택의 구현

순차 자료구조인 1차원 배열을 이용하여 구현하는 순차 자료구조 방식을 이용한 방법과 연결 자료구조 방식을 이용한 방법이 있습니다. 순차 자료구조를 이용한 방법은 구현하기는 쉽지만, 물리적으로 크기가 고정된 배열을 사용하기 때문에 스택의 크기를 변경하기가 어렵고, 메모리의 낭비가 생길수 있다는 문제가 있습니다.

스택의 활용

프로그램 간의 호출과 복귀에 따른 순서를 스택의 LIFO 구조를 응용하여 관리하는 시스템 스택에 사용됩니다.

 

큐

삽입과 삭제의 위치와 방법이 제한되어 있는 유한 순서 리스트 입니다. 한쪽 끝에서는 삽입 작업이 이루어지고, 반대쪽 끝에서는 삭제 작업이 이루어져서 삽입된 순서대로 삭제되는 선입선출(FIFO) 방식으로 동작합니다.

1차원 배열로 구현한 선형 큐는 앞부분에 빈자리가 있어도 rear 가 배열의 마지막 인덱스가 되면 더 이상 원소를 삽입할 수 없는 포화 상태가 됩니다.

큐의 구현

순차 자료구조인 1차원 배열을 이용하여 구현하는 순차 자료구조 방식을 이용한 방법과 연결 자료구조 방식을 이용한 방법이 있습니다. 순차 자료구조를 이용한 방법은 구현하기는 쉽지만, 사용크기가 제한되어 있어서 큐의 길이를 마음대로 변경할 수 없고, 원소가 없을 때에도 항상 처음 크기를 유지하고 있어야 하므로 메모리가 낭비되는 문제가 있습니다. 순차 자료구조 방식에는 선형큐와 원형큐가 있고, 연결 자료구조 방식에는 연결 큐와 덱이 있습니다.

 

원형큐

원형 큐는 1차원 배열의 처음과 끝을 논리적으로 연결하여 만든 큐입니다. 선형 큐의 잘못된 포화 상태 문제를 해결합니다.

덱

큐의 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐로서 스택의 성질과 큐의 성질을 모두 가진 큐입니다. 양방향 삽입과 삭제를 구현하기 위해서 양방향 링크 필드를 가진 이중 연결 리스트를 이용하여 구현합니다.

큐의 활용

큐는 작업 버퍼 큐, 프로세스 스케줄링, 대기 행렬을 모델링하는 시뮬레이션 등에서 사용됩니다.

 

트리

계층관계를 가진 비선형자료구조 입니다. 트리를 구성하는 원소를 노드라고 하고 노드를 연결하는 선을 간선 이라 합니다. 트리의 시작 노드를 루트 노드라 합니다. 한 노드가 가지는 자식 노드의 수를 그 노드의 차수 라 합니다.

이진 트리

모든 노드의 차수를 2 이하로 정하여 전체 트리의 차수가 2 이하가 되도록 만든 것이 이진 트리 입니다.이진 트리는 왼쪽 서브 트리와 오른쪽 서브 트리를 가지는데, 서브 트리 역시 이진트리가 됩니다.

이진 트리의 종류

포화 이진 트리

모든 레벨에 노드가 꽉 차서 포화 상태인 이진 트리 입니다.

완전 이진 트리

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 노드가 왼쪽에서 오른쪽으로 채워져 있는 트리입니다.

편향 이진 트리

최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리입니다.

이진 트리의 구현

순차 자료구조 방식을 이용한 구현

이진 트리의 노드 번호를 배열의 인덱스로 사용하여 1차원 배열로 표현할 수 있습니다. 인덱스 0번은 실제로 사용하지 않고 비워두고 항상 인덱스 1번부터 노드를 저장합니다. 그러면 노드 i의 부모노드의 인덱스는 i/2 가 되고, 왼쪽 자식 노드의 인덱스는 i*2, 오른쪽 자식노드의 인덱스는 i*2+1이 되는 인덱스 관계가 성립합니다.

연결 자료구조 방식을 이용한 구현

데이터를 저장하는 데어터 필드와 왼쪽 자식노드를 연결하는 왼쪽 링크 필드, 오른쪽 자식노드를 연결하는 오른쪽 링크 필드로 구성합니다.

 

순회 방법

이진 트리에 있는 모든 노드를 한번씩 모두 방문하여 노드가 가지고 있는 데이터를 처리하는 순회 방법에는 전위 순회와 중위 순회, 후위 순회의 세 가지가 있습니다.

전위 순회

현재 노드, 왼쪽 서브트리, 오른쪽 서브트리 순서로 순회하는 방법입니다.

중위 순회

왼쪽 서브트리, 현재 노드, 오른쪽 서브트리 순서로 순회하는 방법입니다.

후위 순회

왼쪽 서브트리, 오른쪽 서브트리, 현재 노드 순서로 순회하는 방법입니다.

 

이진 탐색 트리

탐색을 위한 자료구조로 이진 트리를 사용하기 위해서 저장할 데이터의 크기에 따라 노드의 위치를 정의한 트리입니다.

이진 탐색 트리는 다음과 같은 특징을 가집니다.

• 모든 원소는 서로 다른 유일한 키를 갖는다
• 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다
• 오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다
• 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리를 이룬다

힙

완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조 입니다. 일반적으로 힙은 최대 힙을 의미하며, 같은 키값의 노드가 중복되어 있을 수 있습니다.

최대 힙(Max Heap)

키값이 가장 큰 노드를 찾기 위한 완전 이진 트리입니다.

최소 힙(Min Heap)

키값이 가장 작은 노드를 찾기 위한 완전 이진 트리입니다.

그래프

연결되어 있는 원소간의 관계를 표현하는 자료구조 입니다. 그래프는 모든 연결 구조를 표현할 수 있기 때문에 여러 분야에서 폭넓게 이용되고 있습니다.

그래프의 종류

그래프는 방향성과 연결 정도에 따라 여러 형태가 있습니다. 간선의 방향 유무에 따라서 방향 그래프와 무방향 그래프가 있고, 연결 정도에 따라서 부분 그래프, 완전 그래프가 있습니다. 그리고 가중치를 가진 간선으로 이루어진 가중 그래프가 있습니다.

그래프의 구현

그래프를 구현하기 위해서 표현하는 방법은 순차 자료구조 방식을 이용하는 2차원 배열의 인접 행렬 방법과 연결 자료구조 방식인 연결 리스트를 사용하는 인접 리스트 방법이 있습니다.

그래프의 탐색(순회)

하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하는 것을 그래프 순회 또는 그래프 탐색이라고 합니다. 그래프 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색이 있습니다.

깊이 우선 탐색(DFS)

시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향이 간선으로 탐색을 계속함으로써 모든 정점을 방문하는 순회 방법입니다. 깊이 우선 탐색은 스택을 사용합니다.

너비 우선 탐색(BFS)

시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법입니다. 가까운 정점들을 먼저 방문하고 멀리 있는 정점들을 나중에 방문하는 순회 방법입니다. 너비 우선 탐색은 큐를 사용합니다.

신장트리

n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어져 사이클이 없는 단순 연결 그래프를 신장 트리라고 합니다. 깊이 우선 탐색을 이용하여 생성된 깊이 우선 신장트리와 너비 우선 탐색을 이용하여 생성된 너비 우선 신장트리, 무방향 가중치 그래프에서 가중치의 합이 최소인 최소 비용 신장 트리가 있습니다.

 

 

정렬

순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것을 정렬이라 합니다.

정렬 방법의 분류

정렬은 실행 방법과 정렬 장소에 따라 분류할 수 있습니다.

정렬은 실행하는 방법에 따라 한번에 두 개씩 비교하여 교환하는 방식으로 정렬하는 비교식 정렬과 키 값을 기준으로 하여 자료를 여러 개의 부분집합으로 분해하고 부분집합을 정렬함으로써 전체를 정렬하는 분산식 정렬이 있습니다.

정렬은 정렬 장소에 따라 컴퓨터 메모리 내부에서 정렬하는 내부 정렬과 메모리의 외부인 보조 기억 장치에서 정렬하는 외부 정렬로 분류할 수 있습니다.

내부 정렬 방법

교환 방식 : 키를 비교하고 교환하여 정렬하는 방식(선택 정렬, 버블 정렬, 퀵 정렬)

삽입 방식 : 키를 비교하고 삽입하여 정렬하는 방식(삽입 정렬, 셸 정렬)

병합 방식 : 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합)

분배 방식 : 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수 정렬)

선택 방식 : 이진 트리를 사용하여 정렬하는 방식(힙 정렬, 트리 정렬)

선택 정렬

전체 원소들 중에서 선택하여 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬합니다.

버블 정렬

인접한 두개의 원소를 비교하여 자리륵 ㅛ환하는 방식을 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬됩니다.

퀵 정렬

정렬할 전체 원소에 대해서 정렬을 수행하지 않고 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분집합으로 분할합니다. 왼쪽 부분집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분집합에는 기준 값보다 큰 원소들을 이동시킵니다.

삽입 정렬

정렬되어 있는 부분집합에 정렬할 새로운 원소의 순서를 찾아 삽입하는 방법입니다.

셸 정렬

일정한 간격으로 떨어져있는 자료들로 구성한 부분집합 단위로 삽입 정렬을 수행하는 방법입니다. 전체 원소에 대해서 정렬을 수행하는 삽입 정렬 방법에서 비교연산과 교환 연산을 하는 것보다 부분집합으로 나누어 정렬하면 비교횟수와 교환연산을 줄일 수 있습니다.

병합정렬

정렬되지 않은 자료들을 부분집합으로 분할하고 각 부분집합에 대해서 정렬 작업을 완성한 후에 다시 결합하는 분할 정복 기법을 사용합니다. n개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 n-way 병합이라고 합니다.

기수정렬

기수 정렬은 분배방식의 정렬 방법으로 정렬할 원소의 키값에 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복합니다. 기수 정렬은 원소의 키를 표현하는 값의 기수만큼의 버킷이 필요하고, 키값의 자리수만큼 기수 정렬을 반복합니다.

힙 정렬

힙 자료구조를 이용하여 정렬하는 방법입니다.

트리 정렬

이진 탐색 트리를 이용하여 정렬하는 방법입니다. 정렬할 원소들을 이진 탐색 트리로 구성하고 중위 순회 방법을 사용하여 이진 탐색 트리의 원소들을 순회하여 꺼내면 오름차순 정렬이 됩니다.

검색

자료를 검색하는 것은 원하는 탐색키를 가진 항목을 찾는 것입니다. 찾은 경우를 검색 성공이라 하고, 찾지 못한 경우는 검색 실패라고 합니다. 검색 방법에 따라서 비교 검색 방식과 계산 검색 방식으로 분류합니다.

비교 검색 방식

검색 대상의 키를 비교하여 검색하는 방법입니다.(순차 검색, 이진 검색, 트리 검색)

계산 검색 방식

키를 비교하지 않고 계수적인 성질을 이용한 계산으로 검색 하는 방법입니다.(해싱)

순차 검색

일렬로 되어있는 자료를 처음부터 마지막까지 순서대로 비교하여 검색하는 방법입니다. 배열이나 연결 리스트로 구현된 순차 자료구조에서 원하는 항목을 찾는 방법입니다.

색인 순차 검색

인덱스 테이블을 추가로 사용하여 탐새그이 효율을 높이는 검색 방법입니다. 찾고자 하는 키값을 인덱스 테이블에서 검색하여 알아낸 범위에 대해서만 순차 검색을 수행합니다.

이진 검색

가운데에 있는 항목을 키값과 비교하여 키값이 더 크면 오른쪽 부분을 검색하고, 키값이 더 작으면 왼쪽 부분을 검색하는 방법을 반복 수행하는 분할 정복 기법을 이용한 검색 방법입니다. 이진 검색은 반드시 정렬되어 있는 자료에서의 검색에서만 사용할 수가 있습니다.

이진 트리 검색

루트 노드를 기준으로 왼쪽 서브 트리는 루트 노드보다 키값이 작은 원소들로 구성하고, 오른쪽 서브 트리는 루트 노드보다 키값이 큰 원소들로 구성한 이직 탐색 트리를 이용한 검색 방법입니다.

해싱

계수적인 성질을 이용하여 키가 있는 위치를 계싼하여 바로 찾아가는 계산 방식입니다. 해싱 검색은 키값에 대해서 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블로 바로 가서 항목이 있으면 검색 성공이 되고 없으면 검색 실패가 됩니다.