Chap 01. 자료구조와 알고리즘의 이해 [윤성우의 열혈 자료구조]

doriskim·2022년 11월 18일

자료구조

윤성우의 열혈 자료구조

목록 보기

1/9

*본 내용은 [윤성우의 열혈 자료구조] 책과 강의를 보고 공부하면서 요점 정리한 내용입니다.

Chap 01-1: 자료구조에 대한 기본적인 이해

🔳 자료구조와 알고리즘

프로그램이란 데이터를 표현하고(자료구조), 그렇게 표현된 데이터를 처리하는 것이다(알고리즘).
자료구조의 분류
알고리즘은 자료구조에 의존적이다.
자료구조가 결정되어야 알고리즘을 정의하고 개발할 수 있다.

※앞으로 자료구조를 학습할 때
-이론을 공부하고 구현을 공부한다.
-자료구조의 모델을 그림으로 우선 이해해야 한다.

Chap 01-2: 알고리즘의 성능분석 방법

🔳 시간 복잡도 & 공간 복잡도

◼알고리즘을 평가하는 두 가지 요소

시간 복잡도(time complexity): 얼마나 빠른가, CPU에 얼마나 부담을 주는가
공간 복잡도(space complexity): 얼마나 메모리를 적게 쓰는가
시간 복잡도를 더 중요시 한다.

◼시간 복잡도의 평가 방법

중심이 되는 특정 연산의 횟수를 세어서 평가를 한다.
데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다.

◼알고리즘의 수행 속도 비교 기준

데이터의 수가 적은 경우의 수행 속도는 큰 의미가 없다.
데이터 수에 따른 수행 속도의 변화 정도를 기준으로 한다.

🔳 최악의 경우, 최상의 경우, 평균적인 경우

최상의 경우(best case)
운이 좋은 경우
배열의 맨 앞에서 대상을 찾는 경우
만족스러운 상황이므로 성능평가의 주 관심이 아니다!
최악의 경우(worst case)
운이 좋지 않은 경우
배열의 끝에서 찾거나 대상이 저장되지 않은 경우
만족스럽지 못한 상황이므로 성능평가의 주 관심이다!
평균적인 경우(average case)
가장 현실적인 경우
일반적으로 등장하는 상황에 대한 경우의 수
최상의 경우와 달리 알고리즘 평가에 도움이 된다(보조적인 역할)
하지만 계산하기가 어렵고 객관적 평가가 쉽지 않다.

🔳 순차 탐색 알고리즘

// 순차 탐색 알고리즘 함수
int LSearch(int ar[], int len, int target)
{
   	int i;
   	for(i=0; i<len; i++)
   	{
   		if(ar[i] == target) // 중심 연산자'=='
   			return i; // 찾은 대상의 인덱스 값 반환
   	}
   	return -1; // 찾지 못했음을 의미하는 값 반환
}

※ 중심 연산자 찾는 방법(hint)
1. 의심되는 연산자 써보기
예시) ==, <, ++
2. 주변 연산자의 연산 횟수는 중심 연산자의 연산 횟수에 의존적이다.
예시) ==가 true를 반환할 때까지 <, ++ 수행하므로 중심 연산자는 ==

◼ 순차 탐색 최악의 경우 시간 복잡도
데이터의 수가 $n$ 개일 때, 최악의 경우에 해당하는 연산횟수는(비교연산의 횟수는) $n$ 이다.
따라서 $T(n) = n$

◼ 순차 탐색 평균적 경우 시간 복잡도

가정1. 탐색 대상이 배열에 존재하지 않을 확률은 50%이다.
가정2. 배열 첫 요소부터 마지막 요소까지 탐색 대상 존재 확률은 동일하다.
탐색 대상이 존재하지 않는 경우의 연산 횟수는 $n$
가정2.에 의해서 탐색 대상이 존재하는 경우의 평균적인 연산횟수는 $n\over2$
가정1.에 의해서 탐색 대상이 배열에 존재하는 경우, 존재하지 않는 경우의 확률은 $1\over2$ 이다.
따라서 $T(n) = n\times{1\over2} + {n\over2}\times{1\over2} = {3\over4}n$
문제점) 가정1, 가정2에 대한 근거가 전혀 없다.
평균적 경우는 객관적으로 인정하기 어려워 최악의 경우를 구한 다음 보조적 수단으로 사용한다.

🔳 이진 탐색 알고리즘

오름차순으로 정렬되어 있는 길이가 9인 배열에서 3의 값을 갖고 있는 index를 찾고자 한다.

배열 인덱스의 시작 $(first)$ 과 끝 $(last)$ 은 각각 0과 8이다.
가운데 index 값을 찾는다. 이때 나머지는 버린다.
$(first+last)/2$
예시) $(0+8)/2=4$
arr[4]의 값이 3인지 확인한다.
3이 아니라면 저장된 값과 3과의 대소를 비교한다.
저장된 값이 3보다 크면 오른쪽을 버리고 탐색 범위를 왼쪽으로 인덱스를 제한하고, 3보다 작으면 왼쪽을 버리고 탐색 범위를 오른쪽으로 인덱스를 제한한다. (배열이 오름차순 정렬이므로)
예시) arr[4] = 9 → 탐색 범위 0~3으로 제한
위 과정을 3을 찾을 때까지 반복.

이진 탐색은 매 과정마다 탐색의 과정을 반씩 줄여나가기 때문에 순차 탐색보다 비교적 좋은 성능을 보인다. 하지만 배열이 정렬되어 있어야 한다는 제약이 따른다.
찾고자 하는 값이 배열에 저장되어 있지 않을 때는?
항상 $first$ 는 오른쪽으로 $last$ 는 왼쪽으로 이동한다.
$first$ 와 $last$ 가 만났다는 것은 탐색 대상이 없다는 것을 의미하는게 아니라 탐색 대상이 하나 남았다는 것을 뜻한다.
$first$ 와 $last$ 가 역전 되었다는 것은 탐색 대상이 저장되어 있지 않다는 것을 의미한다.
따라서 이진 탐색 알고리즘의 반복 조건은 다음과 같다.

    while(first <= last)
    {
        //이진 탐색 알고리즘의 진행
    }

이진 탐색 알고리즘의 구현

int BSearch(int ar[], int len, int target)
{
 	int first = 0; // 탐색 대상의 시작 인덱스 값
 	int last = len-1; // 탐색 대상의 마지막 인덱스 값
 	int mid;

 	while(first <= last)
 	{
    	mid = (first+last) / 2; // 탐색 대상의 중앙을 찾는다.
     	if(target == ar[mid]) // 중앙에 저장된 것이 타겟이라면
     	{
     		return mid; // 탐색 완료!
     	}
    	else // 타겟이 아니라면 탐색 대상을 반으로 줄인다.
     	{
     		if(target < ar[mid])
     			last = mid-1; // 왜 -1을 하였을까?
     		else
     			first = mid+1; // 왜 +1을 하였을까?
     	}
     }
     return -1; // 찾지 못했을 때 반환되는 값 -1
}

※주의) -1 혹은 +1을 하지 않으면 $first <= mid <= last$ 가 항상 성립이 되어, 탐색 대상이 존재하지 않는 경우 first와 last의 역전 현상이 발생하지 않는다!

최악의 경우 시간 복잡도
이진 탐색 알고리즘의 핵심 연산자는 '=='이다. 따라서 ==연산자의 연산 횟수를 기준으로 시간 복잡도를 결정할 수 있다.
데이터 수가 16개 일 때 $T(n) = 4+1$
데이터 수가 8개 일 때 $T(n) = 3+1$
데이터 수가 4개 일 때 $T(n) = 2+1$
.
.
.
$T(n) = log_2n+1$
그리고 1은 생략 가능하다.
$T(n) = log_2n$