Algorithm Study (배열, 리스트)

이전내용 링크

 

완전탐색

정렬

문자열

 

5. 배열 & 동적배열

일렬로 늘어선 (같은 종류의)자료 여러개를 저장하기 위한 가장 기초적인 자료구조는 배열이다.

배열과 비슷한 자료구조로 연결 리스트가 존재한다.

 

배열은 처음 선언할때 크기를 지정해야 하며, 선언된 크기 이상의 자료를 넣을 수 없다.

이를 해결하기 위해 동적 배열이 존재 한다.

동적 배열은 배열을 이용한 별도의 자료 구조이며 대부분의 언어에서 문법이 아닌 표준 라이브러리에 포함 되어있다.

 

배열(동적배열) 은 다음과 같은 특징이 있다.

• 원소들이 메모리의 연속된 위치에 저장된다.
• 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다.

동적배열의 추가적인 특징은 다음과 같다.

• 배열의 크기를 변경하는 연산(resize)이 가능하다(해당 연산을 수행하기 위해서는 배열 크기 N에 비례하는 시간이 걸린다)
• 주어진 원소를 배열의 맨 끝에 추가하는 연산(append)을 지원한다(상수시간 소요)

위 동적배열의 연산 소요 시간의 자세한 내용은 책'알고리즘 문제해결 전략 2'의 선형 자료구조에서 다루고 있다.

 

동적 배열은 표준라이브러리에서 잘 구현하고 있다(C++ vector, JAVA & C# ArrayList 등)

동적 배열의 재할당에서 비용을 줄이는 방법이 있다.

append 연산을 여러번 수행할 때의 배열 최종 크기를 미리 짐작할 수 있다면 미리 용량을 늘려 오버헤드를 줄일 수 있다(C++ vector : reserve(), JAVA ArrayList : ensureCapacity() 등)

 

6. 연결 리스트

배열에서 원소의 순서를 유지하면서 임의의 위치에 원소를 삽입/삭제 하는 연산이 선형 시간이 걸리는 점을 해결한 자료구조로 삽입/삭제 연산을 산수 시간에 할 수 있다.

 

연결 리스트는 원소가 연속된 메모리에 존재 하지 않고 메모리 이곳 저곳에 존재한다.

각 원소들은 다음 원소를 가리키는 포인터를 가지고 있다.

해당 구조를 노드 라고 부른다.

삽입/삭제 시에 포인터 정보만 변경하면 되기 때문에 연산이 상수 시간에 이루어진다.

C++ STL의 list, JAVA, C# 의 LinkedList 등의 자료구조가 표준라이브러리에 존재한다.

 

위 자료구조들은 탐색, 삽입/삭제, 잘라붙이기, 크기 구하기 등 각각의 소요시간이 다르므로 구현 목적에 맞게 사용하면 된다.

 

책 '알고리즘 문제해결전략2' 표 18.1

작업	동적 배열	연결 리스트
이전 원소/다음 원소 찾기	O(1)	O(1)
맨 뒤에 원소 추가/삭제	O(1)	O(1)
맨 뒤 이외의 위치에 원소 추가/삭제	O(n)	O(1)
임의의 위치 원소 찾기	O(1)	O(n)
크기 구하기	O(1)	O(n) (구현에 따라 O(1))