03-1. 리스트와 배열
리스트는 가장 기초적이고 오랫동안 사용된 자료구조로, 가장 널리 사용되는 구현 방법으로 배열이 있다.
리스트
- 원소를 한 줄로 나열한 구조
- 유한한 원소들의 나열 — a finite sequence of elements
- 각 원소들은 인덱스에 대응된다. ⇒ 그래서 `(인덱스, 원소)`의 쌍으로 나타낼 수 있다.
리스트 구현 방법
- 배열(Array) - 인덱스 기반
- 연속된 기억 공간에 원소를 저장한다. 따라서 인접한 원소는 인접한 주소에 저장한다.
⇒ 그래서 배열은 메모리에 배열 크기보다 더 큰 연속된 공간이 있을 때만 사용할 수 있다. - 연결 리스트(Linked List) - 포인터 기반
- 메모리에 배열 크기보다 더 큰 연속된 공간이 없을 때 사용한다.
⇒ 그래서 어떤 원소를 저장할 때, 그 원소는 다음 원소가 위치한 곳에 대한 포인터(link)를 내장한다.
리스트는 성질에 따라서 정렬된 리스트와 정렬되지 않은 리스트로 나눌 수 있다.
| 종류 | 예시 | 검색 | 추가 | 삭제 |
| 정렬된 리스트 | [1, 2, 3, 4, 5] | 용이 (원소 위치 예상 가능) | 곤란 (정렬 순서 유지) | 곤란 (삭제 후 뒤 원소 모두 앞으로 이동) |
| 정렬되지 않은 리스트 | [10, 3, 28, 1, 7] | 곤란 (원소 위치 예상 불가) | 용이 (순서 상관 없음) | 곤란 (삭제 후 뒤 원소 모두 앞으로 이동) |
두 리스트의 장단점이 비슷해보일 수 있으나, 연산 중 검색은 굉장히 많은 횟수로 발생하기 때문에 정렬된 리스트가 더 효율적이다.
앞으로의 리스트는 정렬된 리스트만 의미한다.
리스트 종류별 목적을 잠깐 정리해보면:
배열과 연결 리스트는 원소를 저장하는 것이 목적이고, 스택과 큐는 원소와 순서를 저장하는 것이 목적이다.
배열(Array)
- 리스트를 인덱스를 이용해 구현한 구조
- 연속적으로 할당된 기억 공간
- 모든 프로그래밍 언어에서 기본 제공
- 배열의 모든 원소들은 인덱스에 대응
- n개의 자료를 하나의 주소로 접근 가능 — 첫 번째 원소의 주소만 알면 모든 자료에 다 접근 가능
배열의 원소가 일렬로 연속된 공간에 저장되므로, 첫 번째 원소의 주소만 알면 배열의 모든 원소에 접근이 가능하다.
(다음 인접 주소로 이동하면 되니까)
왼쪽 그림에서는 array의 주소(예:24124)로 6개의 모든 배열 원소에 접근할 수 있다.
(24124, 24124+1, 24124+2, 24124+…)
배열 구현
정적 배열(Static Array)
컴파일 타임에 명시된 상수값으로 스택에서 메모리가 고정되어 할당된다. 배열의 크기는 변경할 수 없고, 함수가 끝나면 자동으로 해제된다.
#define SIZE 100
{
int count = 0;
int arr[SIZE];
}동적 배열 (Dynamic Array)
런타임에 크기를 결정해서 힙에 메모리를 할당하며, `malloc`, `calloc`, `realloc` 등을 사용해 할당된다. 이때 `arr`는 배열이 아니라 `int` 하나를 가리키는 포인터이며, 힙의 연속된 메모리 공간을 가리킨다. 배열처럼 `arr[i]` 문법을 사용할 수 있으며, 사용이 끝난 후에는 `free` 함수를 사용하여 반드시 메모리를 해제해야 한다.
#define SIZE 100
{
int count = 0;
int *arr = calloc(SIZE, sizeof(int));
}
| 연산 | 동작 | 코드(C) |
| 생성(CREATE) | N개의 원소를 저장할 수 있는 배열 공간을 할당 | `int L[10]` |
| 인출(RETRIEVE) | 배열의 i번째 원소를 조회 | `int x = L[5]` |
| 검색(SEARCH) | 배열에 포함된 원소의 인덱스를 조회 |
`for (int i=0; i< N; i++) { if (L[i] == x) return i; }`
|
| 저장(STORE) | 원소 x를 배열의 i번째 위치에 저장 | `L[5] = x` |
| 추가(INSERT) | 원소 x를 배열에 추가 | `L[count++] = x` |
03-2. 배열의 검색
검색의 정의
| A 배열 | ||||
| 인덱스 | 0 | 1 | 2 | 3 |
| 원소 | 7 | 10 | 13 | 9 |
- 성공적인 검색: key element가 배열에 있는 경우 ⇒ 해당 index를 리턴한다.
- 실패한 검색: key element가 배열에 없는 경우 ⇒ -1 또는 null을 리턴한다. (인덱스로 절대 쓰일 수 없는 값)
//검색 성공
search(A, 9); //key element
=> returns 3
//검색 실패
search(A, 2); //key element
=> returns -1 (null)
선형 검색 (Linear Search)
완전 검색 또는 순차 검색이라고도 하며, 배열의 첫 번째 원소부터 차례로 key element와 동일한 원소가 있는지 확인한다.
따라서 정렬되지 않은 배열에서도 적용이 가능하다.
코드로 살펴보면:
for(int i=0; i<count; i++) { //모든 원소에 대해 확인
if(arr[i] == x) return i; //key element(x)와 같은 원소를 찾으면 인덱스(i) 리턴
}
return -1; //같은 원소를 찾지 못했으면 실패이 때 선형 탐색의 시간 복잡도: \(O(n)\)
- 최악: \(O(n)\)— 배열의 처음부터 끝까지 확인
- 평균: \(O(n/2)\)
- 최선: \(O(1)\) — 배열의 처음 원소가 key element와 같을 경우
이진 검색 (Binary Search) — 분할 정복 알고리즘 (Divide & Conquer)
배열의 중간 원소(mid)와 key element를 비교하여 배열을 절반으로 분할하면서 검색을 재귀적으로 수행한다.
주의할 점은 이 검색은 정렬된 배열에서만 적용할 수 있다.
코드로 살펴보면:
/*
이진 검색은 재귀적으로 실행되므로 중지할 수 있는 base case를 반드시 설정해준다.
배열의 크기가 1일 때(원소가 1개 뿐일 때) 남은 원소가 key element인지 확인하고
결과에 따라 값을 리턴하고 재귀를 중지한다.
*/
if(s == e) return (arr[s] == x) ? s : -1;
mid = (s+e)/2; //mid index
if(arr[mid] == x) return mid; //key element를 찾았으면 인덱스 리턴
//arr[mid] > key element: mid보다 작은 범위에서 검색 - arr[s] ~ arr[mid-1]
if(arr[mid] > x) return binary_search(s, mid-1);
//arr[mid] < key element: mid보다 큰 범위에서 검색 - arr[mid+1] ~ arr[e]
if(arr[mid] < x) return binary_search(mid+1, e);이 때 이진 탐색의 시간 복잡도: \(O(logN)\)
🤔 이 때 시간 복잡도가 \(O(logN)\)이 되는 이유
이진 탐색은 탐색할 때마다 범위가 1/2로 줄어들게 된다.
1번: N
2번: N/2
3번: N/4
4번: N/8
.
.
마지막: 1
이 때, 몇 번을 나누면 탐색 범위가 1이 되는지를 찾으면 되는데 이걸 수식으로 쓰면:
\[
\frac{N}{2^k} = 1
\]
결국 2를 몇 번 곱했을 때 N이 되는지 찾게 된다..
그럼 이 말은 결국 로그의 정의와 마찬가지이므로 수식을 풀이하면:
- 앙변에 대해 역연산했을 떄 \(N=2^k\)가 되니까, 이를 로그로 변환하면 \(log_2N=k\)가 된다.
- 빅오표기법에서는 밑을 무시하므로 \(O(logN)\)이 된다.
03-3. 배열의 추가와 제거
배열의 추가
어떤 정렬된 배열이 있을 때, 적절한 위치에 새로운 원소를 삽입한다. 이 때 위치는 명확히 지정하지 않는다.
추가 알고리즘 (시간 복잡도 \(O(n)\))
1. 새로운 원소 X를 추가할 위치를 결정한다. — \(O(k)\)
2. 추가할 위치에 이미 저장된 원소를 이동시켜 공간을 확보한 뒤, — \(O(n-k)\)
(해당 위치를 포함해 그 뒤의 원소들을 모두 한 칸씩 뒤로 이동시킨다)
3. 원소 X를 그 자리에 저장한다. — \(O(1)\)
4. 배열의 크기(count)를 증가시킨다. — \(O(1)\)
코드로 구현하면:
/*
[예외 처리 필요]
1. count == 0: 배열의 크기가 0일 경우
2. count == Size: 배열이 꽉 찼을 경우
3. x < arr[0]
4. x > arr[count-1] 3,4번은 빠르게 처리할 수 있는 예외 케이스(끝에 추가)
*/
//1. x를 추가할 위치 결정
for(i=0; i<count; i++) {
if (arr[i]>x) break;
}
//2. 추가할 위치의 원소 이동 -> 공간 확보
for(j=count-1; j>=i; j--) { //뒤에서부터 이동
arr[j+1] = arr[j];
}
//3. 원소 추가(확보된 빈 공간에 저장)
arr[i] = x;
//4. 배열의 크기 증가
count++;
return arr;
배열의 제거
어떤 정렬된 배열이 있을 때, 배열 중간에 빈 공간이 남지 않도록 원소를 삭제한다.
추가 알고리즘 (시간 복잡도 \(O(n)\))
1. 제거할 원소 X를 배열에서 찾는다. — \(O(k)\)
2. 제거할 원소 뒤에 있는 원소들을 한 칸씩 앞으로 이동시킨다. — \(O(n-k)\)
3. 배열의 크기(count)를 감소시킨다. — \(O(1)\)
코드로 구현하면:
/*
[예외 처리 필요]
1. count == 0: 배열의 크기가 0일 경우
2. x == arr[0]
3. x == arr[count-1] 2,3번은 빠르게 처리할 수 있는 예외 케이스(끝에 추가)
4. x가 arr 배열에 포함되지 않을 경우
*/
//1. x를 찾는다
for(i=0; i<count; i++) {
if (arr[i] == x) break;
if (i == count) return; //예외 4에 해당
}
//2. 제거할 위치의 원소 뒤의 원소들을 앞으로 이동
for(j=i; j<count-1; j++) { //앞에서부터 이동
arr[j] = arr[j+1];
}
//3. 배열의 크기 감소
count--;
return arr;'CS > 자료구조' 카테고리의 다른 글
| [k-mooc/자료구조] 06-1. 정렬(Sorting) - O(N^2) 정렬 알고리즘 (2) | 2025.07.27 |
|---|---|
| [k-mooc/자료구조] 05. 스택/큐(Stack/Queue) (4) | 2025.07.26 |
| [k-mooc/자료구조] 04. 연결 리스트(Linked List) (2) | 2025.07.21 |
| [k-mooc/자료구조] 02. 성능 분석 (1) | 2025.07.18 |
| [k-mooc/자료구조] 01. 자료구조의 소개 (2) | 2025.07.17 |