본문 바로가기
자료구조

[자료구조] 리스트&배열

by 상똥 2022. 10. 9.

1. 리스트

• 리스트의 개념

   - 유한한 원소들을 한 줄로 나열한 구조

   - 각 원소들은 인덱스에 대응됨

 

• 리스트의 구분

   - 정렬되지 않은 리스트 : 위치 예측 불가능, 추가연산에 유리

   - 정렬된 리스트 : 위치 예측 가능, 검색 연산에 유리 ⇒ 더 효율적

 

• 리스트의 종류

   - 원소를 저장 : 배열, 연결 리스트

   - 원소와 순서를 저장 : 스택, 큐

 

2. 배열

• 배열의 개념

   - 인덱스를 활용하여 리스트를 구현한 구조 (배열의 모든 요소들은 인덱스에 대응됨)

   - 연속적으로 할당된 공간 (최소한 배열의 크기만큼 연속된 공간이 있을 때 사용 가능)

   - 하나의 주소로 n개의 자료에 접근 가능함 (첫 번째 원소인 A의 위치 0014를 알면, 연속된 공간을 사용하는 배열의 특성에 의해 그 다음 원소들의 위치 0015, 0016...을 알 수 있다)

• 배열의 연산

연산 정렬된 배열 ★ 정렬되지 않은 배열
검색 ① Linear search Linear search
② Binary search
추가 Insert by value ① Insert(A, x)
② Insert by index(A, i, x)
③ Store(A, i, x)
제거 ① Delete by value(A, x)
② Delete by index(A, i, x)

(* A=배열, i=인덱스, x=원소) 아래에서 설명하는 모든 배열은 정렬된 배열 기준 

 

3. 배열의 검색

 • 배열의 선형탐색 (Linear search)

   - 완전검색(exhaustive search) 또는 순차검색(sequential search)

   - 배열의 첫 번째 원소부터 차례로 방문하면서 찾으려는 원소와 동일한 원소가 있는지 확인

   - 입력 : 배열(A), 찾고자 하는 원소(x)

   - 출력 : x의 index(i)

#include <stdio.h>

int linear_search(int* arr, int x, int SIZE) {
	for (int i = 0; i < SIZE; i++)
		if (arr[i] == x)
			return i;
	return -1;
}

int main() {
	int SIZE;
    scanf_s("%d", &SIZE);
	int arr[100];
	for (int i = 0; i < SIZE; i++)
		scanf_s("%d", &arr[i]);

	int x;
	scanf_s("%d", &x);
	printf("%d", linear_search(arr, x, SIZE));
}

   - 선형탐색의 시간복잡도 : O(n)

      ① 최악의 경우 : O(n) (찾고자 하는 원소가 맨 뒤에 있는 경우)

      ② 최선의 경우 : O(1) (찾고자 하는 원소가 배열의 맨 앞에 있는 경우)

      ③ 평균의 경우 : O(n/2) = O(n) (찾고자 하는 원소가 중간에 있는 경우)

 

• 배열의 이진탐색 (Binary search)

   - 분할&정복 알고리즘(divide&conquer)

   - 배열의 중간 원소와 찾고자 하는 원소를 비교하여 중간 원소를 기준으로 배열을 분할함으로써 검색 수행

    ⇒ 정렬된 배열에서만 사용 가능함

   - 배열의 중간 원소를 찾아 배열을 절반으로 분할하여 검색할 범위를 지정하고, 검색을 재귀적으로 수행함

     (시작 위치 = s 끝 위치 = e)

#include <stdio.h>

int arr[100];

int binary_search(int* arr, int x, int s, int e) {
	int mid = (s + e) / 2;

	if (x == arr[mid])
		return mid;
	else if (x < arr[mid]) {
		e = mid - 1;
		return binary_search(arr, x, s, e);
	}
	else {
		s = mid + 1;
		return binary_search(arr, x, s, e);
	}

	return -1;
}

int main() {
	int SIZE;
    scanf_s("%d", &SIZE);
    
	for (int i = 0; i < SIZE; i++)
		scanf_s("%d", &arr[i]);

	int x, s = 0, e = SIZE;
	scanf_s("%d", &x);
	printf("%d", binary_search(arr, x, s, e));
}

   - 이진탐색의 시간복잡도 : O(logn)

  ∵ n개의 데이터에 대해 배열을 반 씩 분할하며 검색하므로,

          T(n) = T(n/2) + 1

          T(n/2) = T(n/4) + 1

          T(n/4) = T(n/8) + 1

                    ∙ ∙ ∙

          T(2) = T(1) + 1

           ⇒ T(n) = T(1) + logn

           ⇒ O(logn)

 

4. 배열의 추가

• 추가 알고리즘

① 새로운 원소를 추가할 위치 결정 : 새로운 원소(x)보다 가장 큰 값들 중에서 가장 작은 값의 위치 O(k)

② 가장 끝에 있는 원소부터 추가할 원소의 위치에 있는 원소까지 차례로 한 칸씩 위치를 옮겨서 공간을 확보 O(n-k) = O(n)

③ 원소 추가 O(1)

④ 배열의 크기 증가 O(1)

#include <stdio.h>

int arr[100];

int insert_by_value(int* arr, int SIZE) {
	int x, i;
	scanf_s("%d", &x);

	for (i = SIZE - 1; i > -1; i--) {
		if (arr[i] == x)
			break;

		if (arr[i] < x)
			break;
		else
			arr[i+1] = arr[i];
	}
	arr[i+1] = x;

	return arr[SIZE];
}

int main() {
	int SIZE;
	scanf_s("%d", &SIZE);

	for (int i = 0; i < SIZE; i++)
		scanf_s("%d", &arr[i]);

	insert_by_value(arr, SIZE);
	SIZE++;
}

   - 추가의 시간복잡도 : O(n)

 

• 제거 알고리즘

① 제거할 원소(x)를 배열에서 탐색 O(k)

② 배열의 특성상 빈칸이 발생하지 않도록 제거할 원소 뒤에 있는 원소들을 한 칸씩 앞으로 이동 O(n-k) = O(n)

③ 배열의 크기 감소 O(1)

#include <stdio.h>

int arr[100];

int delete_by_value(int* arr, int SIZE) {
	int x, i;
	scanf_s("%d", &x);
	
	for (i = 0; i<SIZE ; i++) 
		if (arr[i] == x)
			break;

	for (int j = i; j < SIZE; j++)
		arr[j] = arr[j + 1];

	return arr[SIZE];
}

int main() {
	int SIZE;
	scanf_s("%d", &SIZE);

	for (int i = 0; i < SIZE; i++)
		scanf_s("%d", &arr[i]);

	delete_by_value(arr, SIZE);
	SIZE--;
}

   - 제거의 시간복잡도 : O(n)

요약

검색 선형탐색 O(n)
이진탐색 O(logn)
추가 O(n)
제거 O(n)

 

티스토리툴바