간략한 요약
이 강의에서는 알고리즘과 자료 구조의 차이점을 설명하고, 시퀀스 및 집합 인터페이스와 배열 및 포인터 기반 자료 구조라는 두 가지 주요 자료 구조 도구를 소개합니다. 정적 시퀀스 인터페이스와 동적 시퀀스 인터페이스를 살펴보고, 연결 리스트와 동적 배열을 사용하여 이러한 인터페이스를 구현하는 방법을 분석합니다. 동적 배열의 amortized 분석을 통해 작업 시퀀스 전반에 걸쳐 평균화함으로써 개별 작업의 비용이 높더라도 전체 성능이 향상될 수 있음을 보여줍니다.
- 인터페이스와 자료 구조의 차이점 이해
- 정적 및 동적 시퀀스 인터페이스 구현
- 연결 리스트와 동적 배열의 장단점 분석
- 동적 배열의 amortized 분석을 통한 효율성 향상
소개
알고리즘 소개 강의에서는 알고리즘 대신 자료 구조를 다루며, 시퀀스, 집합, 연결 리스트, 동적 배열과 같은 간단한 자료 구조를 소개합니다. 인터페이스(API 또는 ADT)와 자료 구조의 차이점을 설명하며, 인터페이스는 원하는 작업을 명시하고 자료 구조는 이를 수행하는 방법을 제시합니다. 인터페이스는 저장할 데이터와 지원되는 작업 및 의미를 지정하고, 자료 구조는 이러한 작업을 지원하는 알고리즘을 제공합니다.
집합과 시퀀스
이 강의에서는 집합과 시퀀스라는 두 가지 주요 인터페이스를 다룹니다. 집합은 수학적 의미와 프로그래밍적 의미가 다를 수 있으며, 시퀀스는 특정 순서로 저장된 항목들을 나타냅니다. 시퀀스 인터페이스는 항목의 순서를 유지하고, 정적 시퀀스와 동적 시퀀스로 나눌 수 있습니다. 또한, 배열과 포인터 기반 자료 구조라는 두 가지 주요 자료 구조 도구를 소개합니다.
정적 시퀀스 인터페이스
정적 시퀀스 인터페이스는 항목 수가 변경되지 않는 시퀀스를 다루며, build, length, iteration, get, set과 같은 작업을 지원합니다. build는 초기 데이터를 기반으로 새로운 자료 구조를 생성하고, length는 시퀀스의 고정된 길이를 반환합니다. iteration은 시퀀스의 항목을 지정된 순서대로 출력하고, get_at과 set_at은 특정 위치의 항목을 가져오거나 변경합니다. 이러한 작업은 정적 배열을 통해 효율적으로 구현할 수 있습니다.
정적 배열
정적 배열은 정적 시퀀스 인터페이스의 자연스러운 해결책으로, 메모리의 연속적인 공간에 데이터를 저장합니다. word RAM 모델을 사용하여 메모리 접근 방식을 설명하고, 배열의 i번째 항목에 접근하는 것은 배열의 시작 주소에 i를 더한 위치에 접근하는 것과 같습니다. 이를 통해 get_at과 set_at 작업을 상수 시간에 수행할 수 있습니다. 메모리 할당 모델에서는 크기가 n인 배열을 생성하는 데 선형 시간이 걸린다고 가정합니다.
Word RAM 모델
Word RAM 모델에서는 배열 접근이 상수 시간에 이루어지려면 워드 크기 w가 최소 log n 이상이어야 합니다. 이는 n개의 항목을 다루려면 각 항목의 주소를 워드 내에 표현할 수 있어야 하기 때문입니다. 이러한 가정은 실제 머신과 이론을 연결하며, 알고리즘의 확장성을 고려할 때 중요합니다.
동적 시퀀스 인터페이스
동적 시퀀스 인터페이스는 정적 시퀀스 인터페이스에 insert와 delete 작업을 추가하여 시퀀스의 크기를 변경할 수 있도록 합니다. insert_at은 특정 위치에 새로운 항목을 삽입하고, delete_at은 특정 위치의 항목을 삭제합니다. 특히, insert_first, insert_last, delete_first, delete_last와 같은 특수한 경우에 대한 효율적인 알고리즘을 고려합니다.
연결 리스트
연결 리스트는 노드를 사용하여 항목을 저장하고, 각 노드는 항목과 다음 노드를 가리키는 포인터를 가집니다. head 포인터를 사용하여 리스트의 시작을 추적하고, 필요에 따라 length를 저장할 수도 있습니다. 연결 리스트는 포인터를 사용하여 노드의 순서를 유지하며, 메모리 내에서 노드의 물리적 위치는 중요하지 않습니다. 연결 리스트는 배열 기반 자료 구조와 포인터 기반 자료 구조의 예시입니다.
정적 배열과 연결 리스트의 동적 시퀀스 작업 분석
정적 배열에서 insert와 delete는 선형 시간이 걸리는데, 이는 항목을 삽입하거나 삭제할 때마다 다른 항목들을 이동시켜야 하기 때문입니다. 연결 리스트에서 insert_first와 delete_first는 상수 시간에 수행할 수 있지만, get_at과 set_at은 i번째 항목에 접근하기 위해 i번 포인터를 따라가야 하므로 i 시간이 걸립니다. 이러한 분석을 통해 각 자료 구조의 장단점을 파악할 수 있습니다.
동적 배열
동적 배열은 배열과 연결 리스트의 장점을 결합하여, Python의 리스트와 유사하게 구현됩니다. 동적 배열은 배열의 크기가 n(시퀀스의 항목 수)과 정확히 일치하지 않도록 하여, 크기가 대략 n이 되도록 유지합니다. 배열의 크기를 theta(n)으로 유지하면서, insert_last와 같은 작업을 상수 시간에 수행할 수 있도록 합니다.
동적 배열의 크기 조정
동적 배열에서 항목을 삽입할 때 배열이 가득 차면, 새로운 배열을 할당하고 기존 항목을 복사해야 합니다. 배열의 크기를 두 배로 늘리는 방법을 사용하면, 크기 조정 작업은 드물게 발생하며, amortized 분석을 통해 작업당 평균 비용이 상수 시간이 됩니다. 크기 조정 비용은 1 + 2 + 4 + 8 + ... + n으로, 이는 기하 급수의 합이므로 theta(n)입니다.
Amortized 분석
Amortized 분석은 작업 시퀀스 전반에 걸쳐 평균 비용을 계산하는 방법으로, 개별 작업의 비용이 높더라도 전체 성능을 평가하는 데 유용합니다. 동적 배열에서 insert_last 작업은 상수 amortized 시간을 가지는데, 이는 n번의 insert_last 작업을 수행하는 데 선형 시간이 걸리기 때문입니다. Amortized 분석을 통해 동적 배열이 효율적인 자료 구조임을 확인할 수 있습니다.
시퀀스 인터페이스 작업 비교
강의에서는 배열, 연결 리스트, 동적 배열의 주요 시퀀스 인터페이스 작업에 대한 성능을 비교합니다. 배열은 get_at과 set_at 작업에서 상수 시간을 가지지만, insert와 delete 작업에서는 선형 시간이 걸립니다. 연결 리스트는 insert_first와 delete_first 작업에서 상수 시간을 가지지만, 다른 작업에서는 선형 시간이 걸립니다. 동적 배열은 get_at과 set_at 작업에서 상수 시간을 가지며, insert_last와 delete_last 작업에서 상수 amortized 시간을 가집니다.
