알고리즘 문제 해결 전략2 18장 선형 자료 구조(1)

18.1 도입

일렬로 늘어선 같은 종류의 자료 여러 개를 저장하기 위한 가장 기초적인 자료구조는 배열. 동적 배열과 연결 리스트에 대해 다룸.

 

18.2 동적 배열

배열의 큰 문제 중 하나는 처음에 배열을 선언할 때 배열의 크기를 지정해야 함. 그 이상의 자료를 집어넣을 수 없다는 점임. 동적 배열은 배열이 갖는 다음과 같은 특성을 그대로 이어 받음. 원소들은 메모리의 연속된 위치에 저장됨. 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있음. 동적으로 할당받은 배열과 동적 배열은 서로 별개의 개념임. 동적 배열 클래스는 현재 배열의 크기와 동적으로 할당받은 배열을 가리키는 포인터를 다음과 같이 저장하고 있음. 메모리를 할당받을 때 배열의 크기가 커질 때를 대비해서 여유분의 메모리를 미리 할당받아 둠. 

 

동적 배열의 재할당 전략

append()를 수행하는 데 선형 시간이 걸리는 것은 아주 가끔 일어나는 재할당 과정 때 뿐임. N번의 append() 연산을 하는 데 드는 총 시간이 ... 따라서 이런 재할당 전략으로는 상수 시간에 append()를 구현한다는 우리 목표를 달성할 수 없음. 상수 시간에 append()를 구현하는 비결은 재할당을 할 때마다 정해진 개수의 여유분을 확보하는 것이 아니라, 현재 가진 원소의 개수에 비례해서 여유분을 확보하는 것임. 이와 같은 전략을 택하면 항상 복사의 수가 배열의 크기에 선형으로 비례함을 보일 수 있음. 

 

18.3 연결 리스트

특정 위치에서의 삽이과 삭제를 상수 시간에 할 수 있게 해 줍니다. 연결 리스트는 우너소들이 메모리 여기 저기 흩어져 있고 각 원소들이 이전과 다음 원소를 가리키는 포인터를 가지고 있는 방식으로 구현됨 .

 

연결 리스트 다루기

결과적으로 i번째 노드를 찾는 데 드는 시간은 리스트의 길이에 선형 비례하게 됨. 반면 다른 노드들의 순서를 유지하면서 새 노드를 삽입하거나 기존 노드를 삭제하는 작업은 아주 간단함. 프로그램에서 되돌리기 연산을 지원하는 데 유용하게 쓸 수 있습니다. 되돌리기가 가장 잘 사용되는 곳은 사용자 인터페이스입니다. 유용한 곳이 있으면 11장 조합 탐색임. 조합 탐색에서는 답의 한 조각을 만들고, 현재의 상태를 갱신한 뒤 나머지를 재귀 호출로 해결함. 그리고 재귀 호출이 끝난 후 문제의 상태는 다시 복구되어야 함. 

 

18.4 동적 배열과 연결 리스트의 비교

삽입 삭제를 할 일이 없거나, 배열의 끝에서만 하면 될 경우에는 동적 배열이 거의 항상 더 좋은 선택임. 임의의 원소에 빠르게 접근할 수 있을 뿐더러, 원소들이 메모리에 연속해 배치되어 있다는 점이 CPU 캐시의 효율을 더 높여줌.