자료구조: 시퀀스 (리스트) ADT

Cheatsheet Content

### 시퀀스 (리스트) ADT: 소개 - **정의**: 요소를 선형 순서로 저장하는 추상 자료형. 각 요소는 고유한 위치(인덱스)를 가짐. - **특징**: - `n`개의 요소를 순서대로 저장 ($A_0, A_1, ..., A_{n-1}$). - 인덱스를 통해 요소에 접근. - **빈 리스트 (empty list)**: 요소가 없는 시퀀스 (`n=0`). #### 일반적인 연산 - **조회**: - `Size()`: 시퀀스 크기 반환. - `Get(i)`: 인덱스 `i`의 요소 반환. - `Set(i, x)`: 인덱스 `i`의 요소를 `x`로 설정. - `Find(x)`: `x`의 인덱스 반환 (-1은 없음). - **수정**: - `Insert(i, x)`: 인덱스 `i`에 `x` 삽입. - `Remove(i)`: 인덱스 `i`의 요소 제거. #### ADT와 자료구조의 차이 - **시퀀스 ADT**: '무엇을 할지' 정의 (개념적). - **자료구조 (구현)**: '어떻게 할지' 구현 (배열, 연결 리스트 등). ### 배열 (Arrays) - **정의**: 동일한 유형의 요소를 **연속된 메모리 공간**에 저장하는 자료구조. - **접근**: 정수 인덱스 ($0 \sim n-1$)를 사용한 **직접 접근**. #### 배열의 특징 및 연산 - **장점**: - **$O(1)$ 무작위 접근**: 인덱스로 즉시 요소에 접근 가능. - **캐시 친화적**: 연속된 메모리로 인해 높은 성능. - 메모리 효율적 (포인터 오버헤드 없음). - **단점**: - **고정 크기**: 생성 후 크기 변경이 어려움. - **느린 삽입/삭제**: 요소를 이동해야 하므로 $O(n)$ 시간 소요. #### 배열 연산 시간 복잡도 | 연산 | 시간 복잡도 | |---|---| | `Get(i)` | $O(1)$ | | `Set(i, x)` | $O(1)$ | | `Insert(i, x)` | $O(n)$ | | `Remove(i)` | $O(n)$ | #### 동적 배열 (Dynamic Arrays, 예: C++ `std::vector`) - 크기가 자동으로 조절되는 배열. - 내부 배열이 가득 차면, 더 큰 새 배열을 할당하여 기존 요소를 복사. - **분할 상환 분석**: `push_back()` 같은 연산의 평균 비용은 $O(1)$ (재할당 비용이 드물게 발생). ### 연결 리스트 (Linked Lists) - **정의**: 요소를 **비연속적인 메모리 공간**에 저장하는 선형 자료구조. - **노드**: 각 요소는 `값`과 다음 노드를 가리키는 `포인터`로 구성. - **접근**: `head`부터 시작하여 순차적으로 포인터를 따라가야 함. #### 연결 리스트의 특징 및 연산 - **장점**: - **빠른 삽입/삭제**: 포인터만 변경하면 되므로 $O(1)$ 시간 소요 (위치를 알고 있을 경우). - **동적 크기**: 필요한 만큼 메모리 할당/해제하여 크기 유연하게 조절. - **단점**: - **느린 조회/접근**: 특정 인덱스에 접근하려면 `head`부터 $O(n)$ 순회 필요. - **메모리 오버헤드**: 각 노드마다 포인터를 저장해야 함. - **캐시 비효율적**: 요소들이 메모리에 흩어져 있음. #### 연결 리스트 연산 시간 복잡도 | 연산 | 시간 복잡도 | |---|---| | `Get(i)` | $O(n)$ | | `Set(i, x)` | $O(n)$ | | `Insert(i, x)` | $O(1)$ (위치를 찾은 후) | | `Remove(i)` | $O(1)$ (위치를 찾은 후) | #### 연결 리스트의 종류 - **단일 연결 리스트**: 각 노드가 다음 노드만 가리킴. - **이중 연결 리스트**: 각 노드가 이전 노드와 다음 노드 모두 가리킴 (양방향 탐색 가능). - **원형 연결 리스트**: 마지막 노드가 첫 번째 노드를 가리켜 고리 형태를 이룸. ### 배열 vs. 연결 리스트: 비교 및 활용 | 특징 | 배열 (Array/Vector) | 연결 리스트 (Linked List) | |----------------|-----------------------------------------------|---------------------------------------------------------| | **메모리 구조** | 연속적 | 비연속적 (노드별로 분산) | | **접근 (조회)** | 빠름 ($O(1)$, 인덱스 기반) | 느림 ($O(n)$, 순차 탐색) | | **삽입/삭제** | 느림 ($O(n)$, 요소 이동 필요) | 빠름 ($O(1)$, 포인터 변경) | | **크기 조절** | 고정 또는 재할당 (동적 배열) | 유연함 (필요에 따라 노드 추가/제거) | | **메모리 오버헤드** | 낮음 | 높음 (각 노드에 포인터 저장) | | **캐시 효율성** | 좋음 | 나쁨 | #### 언제 무엇을 사용할까? - **배열/동적 배열**: - **데이터 조회/접근**이 빈번할 때. - 데이터의 **순서가 중요**하고, **크기가 상대적으로 고정**되거나 예측 가능할 때. - `std::vector`는 대부분의 경우 좋은 기본 선택. - **연결 리스트**: - **잦은 삽입/삭제**가 발생할 때 (특히 중간 위치). - 데이터의 **크기가 매우 유동적**일 때. - 특정 인덱스로의 **직접 접근이 중요하지 않을 때**. ### 일반성: 컨테이너, 반복자, 알고리즘 - **목표**: 특정 자료구조에 얽매이지 않고, 재사용 가능한 코드를 작성. #### 컨테이너 (Containers) - 요소들의 컬렉션을 저장하는 객체. - 각 컨테이너는 특정 자료구조를 기반으로 하며, 성능 특성이 다름. - **예시 (C++ STL)**: - `std::vector`: 동적 배열. - `std::list`: 이중 연결 리스트. - `std::deque`: 양방향 큐. #### 반복자 (Iterators) - 컨테이너의 요소들을 일반화된 방식으로 **순회하고 접근**할 수 있게 하는 객체. - **포인터와 유사하게 동작**: - `*p`: 반복자가 가리키는 요소의 값. - `++p`: 다음 요소로 이동. - `begin()`: 컨테이너의 첫 요소 반복자. - `end()`: 컨테이너의 마지막 요소 다음 위치 반복자. - 다양한 종류: 입력, 출력, 전방향, 양방향, 무작위 접근 반복자. #### 일반 알고리즘 (Generic Algorithms) - 반복자를 인자로 받아 여러 컨테이너에 적용 가능한 함수. - `#include `에 정의됨. - **예시**: - `std::sort(begin, end)`: `[begin, end)` 범위 정렬. - `std::find(begin, end, value)`: `[begin, end)` 범위에서 `value` 찾기. - `std::for_each(begin, end, function)`: `[begin, end)` 범위의 각 요소에 함수 적용. ### C++ 코드 예시: Vector와 List, 그리고 Iterator 활용 ```cpp #include #include #include #include // std::find, std::sort 등 int main() { // 1. std::vector (동적 배열) 사용 예시 std::vector numbers_vec = {10, 20, 30, 40, 50}; std::cout numbers_list = {1, 2, 3, 4, 5}; std::cout