Seongkyun Han's blog

CH1. 자료구조와 알고리즘의 이해

04 Mar 2019 | data structure 자료구조

CH1. 자료구조와 알고리즘의 이해

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

자료구조란 무엇인가

  • 자료구조에서는 데이터를 표현하고 저장하는 방법에 대해서 설명함
    • 데이터의 저장을 담당하는것이 바로 자료구조
    • 넓은 의미에서 int형 변수 선언이나 구조체의 정의, 배열의 선언 또한 자료구조에 속함
  • 실제로는 아래의 세부 자료 구조들이 존재
    • 선형구조
      • 리스트
      • 스택
      • 큐
    • 비선형구조
      • 트리
      • 그래프
    • 파일구조
      • 순차파일
      • 색인파일
      • 직접파일
    • 단순구조
      • 정수
      • 실수
      • 문자
      • 문자열
  • 수업에서는 __선형구조, 비선형구조__에 대해서만 다룸
  • 선형구조는 자료의 표현방식이 선형임을 의미
    • 선형 자료구조는 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식(공부하기 수월)
  • 비선형구조는 데이터를 나란히 저장하지 않음(어려움)

본서에서 자료구조 설명하는 방향

  • 본 서는 코드레벨에서의 구현이 아닌 자료구조의 모델 자체에 대한 이해를 강조한 서적

자료구조와 알고리즘

  • 자료구조는 데이터의 표현 및 저장방법을 뜻한다면, 알고리즘은 저장된 데이터를 대상으로 하는 문제 해결 방법을 의미
  • 따라서 자료구조가 결정되어야 그에 맞는 문제 해결 방법을 제시 할 수 있으므로 밀접한 관계를 가짐

1-2 알고리즘의 성능분석 방법

시간 복잡도와 공간 복잡도

  • 시간 복잡도는 속도에 해당하는 알고리즘의 수행시간 분석결과를 가리킴
  • 공간 복잡도는 메모리 사용량에 대한 분석결과를 가리킴
  • 보통 공간 복잡도보다 시간 복잡도를 더 중요시 여김
  • 시간 복잡도의 판단은 처리해야 할 데이터의 수 $n$에 대한 연산횟수의 함수 $T(n)$을 구성
    • 데이터 수의 증가에 따른 연산횟수의 변화 정도를 정량적으로 판단 할 수 있기 때문

순차 탐색(Linear search) 알고리즘과 시간 복잡도 분석의 핵심요소

  • 순차 탐색 알고리즘이라는 간단한 알고리즘으로 시간 복잡도를 계산
# pragma warning disable(4996)
# include<stdio.h>
int LSearch(int ar[], int len, int target)
{
	int i;
	for (i = 0; i < len; i++)
	{
		if (ar[i] == target)
			return i;
	}
	return -1;
}

int main(void)
{
	int arr[] = { 3, 5, 2, 4, 9 };
	int idx;

	idx = LSearch(arr, sizeof(arr) / sizeof(int), 4);
	if (idx == -1)
		printf("탐색실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);
	idx = LSearch(arr, sizeof(arr) / sizeof(int), 7);
	if (idx == -1)
		printf("탐색실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);
	getchar();
	return 0;
}
  • 위 코드에서 순차탐색 알고리즘인 LSearch 함수 내의 for문을 볼 때, 데이터 수 $n$에 대한 시간 복잡도 $T(n)$을 계산해보자.
    • 알고리즘에 사용된 연산자는 <, ++, == 세 가지임
    • 이 중 값을 비교하는 == 연산을 가장 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘임
    • 즉, 탐색 알고리즘의 핵심은 동등비교를 하는 비교연산에 있음
      • 비교연산을 적게할수록 <연산과 ++연산의 수행횟수가 줄게 됨(다른 연산들이 == 연산에 의존적)
    • 즉, ==연산의 횟수를 대상으로 시간 복잡도를 분석하면 됨
    • 찾고자 하는 배열의 값이 맨 앞에 있으면 비교연산의 수행횟수는 1이 됨 -> best case
    • 찾고자 하는 배열의 값이 맨 뒤에 있으면 비교연산의 수행횟수는 n이 됨 -> worst case (중요)
    • Average case의 경우 합리적이나 계산이 복잡하고 평균의 정의가 애매 -> 따라서 worst case로 계산

순차 탐색 알고리즘의 시간 복잡도 계산 1: Worst case

  • 데이터의 수가 n개일때 worst case는 n이 됨
  • $T(n)=n$

순차 탐색 알고리즘의 시간 복잡도 계산 2: Average case

  • 가정 1. 탐색 대상이 배열에 존재하지 않을 확률을 50%라고 가정: $T(n)=n$
  • 가정 2. 배열의 첫 요소부터 마지막 요소까지 탐색 대상이 존재할 확률은 동일: $T(n)=\frac{n}{2}$
  • 가정 1과 가정 2에 따라 위의 두 식을 하나로 묶어야 함 -> $n\times \frac{1}{2}\times +\frac{n}{2}\frac{1}{2}=\frac{3}{4}n$
  • 따라서 순차 탐색 알고리즘의 average case의 시간 복잡도는 $T(n)=\frac{3}{4}n$가 됨
  • 계산이 복잡하고, 모든 가정을 제대로 정의하지 못하면 신뢰도가 낮게 됨

이진 탐색(Binary Search) 알고리즘의 소개

  • 배열에 저장된 데이터는 정렬되어 있는 상태일 때만 사용 가능
  • 길이가 9인 배열에 다음과 같이 정렬된 데이터가 있다고 가정
  • arr[] = {1, 2, 3, 7, 9, 12, 21, 23, 27}
  • 위의 배열을 대상으로 숫자 3이 저장되어 있는지를 확인하기 위한 이진 탐색 알고리즘 적용
    • 첫 번째 시도: 배열의 중앙에 찾는 값이 저장되어 있는지를 확인
      • 배열 인덱스 시작과 끝은 각각 0과 8
      • 0과 8을 합하여 그 결과를 2로 나눔
      • 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인
    • 두 번째 시도: 탐색의 대상을 반으로 줄임(정렬되어있으므로)
      • arr[4]의 값인 9와 3의 대소를 비교
      • arr[4]>3 이므로 탐색 범위를 인덱스 0~3으로 제한
      • 0과 3을 더하여 결과를 2로 나눔(나머지 버림)
      • 2로 나눠서 얻은 결과 1을 인덱스 값으로 하여 arr[1]에 저장된 값이 3인지 확인
    • 세 번째 시도: 동일 패턴 반복
      • arr[1]의 값인 2와 3의 대소를 비교
      • arr[1]<3이므로 탐색 범위를 인덱스 2~3으로 제한
      • 2와 3을 더한 후 2로 나눠 2 계산(나머지 버림)
      • arr[2]의 값이 3인지 확인

이진 탐색 알고리즘의 구현

  • 왼쪽 끝 인덱스 first와 오른쪽 끝 인덱스 last가 first<=last 조건을 만족할 동안 비교가 진행되어야 함
    • first = last일 때에도 비교해야 할 대상이 아직 하나 남아있기 때문
# pragma warning disable(4996)
# include<stdio.h>
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; // ???
			else
				first = mid + 1; // ???
		}
	}
	return -1;
}

int main(void)
{
	int arr[] = { 3, 5, 2, 4, 9 };
	int idx;

	idx = BSearch(arr, sizeof(arr) / sizeof(int), 4);
	if (idx == -1)
		printf("탐색실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);
	idx = BSearch(arr, sizeof(arr) / sizeof(int), 7);
	if (idx == -1)
		printf("탐색실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);
	getchar();
	return 0;
}
  • 위 코드에서 아래처럼 구현하지 않고 위처럼 +1을 추가하여 구현한 이유는?
if (target < ar[mid])
  last = mid;
else
  first = mid;
  • 정답 코드처럼 하지 않으면 불필요한 mid에 저장된 인덱스 값이 배열요소도 새로운 탐색의 범위에 포함이 되기 때문
  • 또한 위 코드처럼 작성 할 경우 대상을 배열에서 찾지 못할 경우 무한loop에 빠지며 프로그램이 종료되지 않게 됨
    • 탐색 대상이 배열에 존재하지 않을 경우 first의 값이 last보다 커져서 반복문을 탈출해야 함

이진 탐색 알고리즘의 시간 복잡도 계산: Worst case

  • 이진 탐색 알고리즘 또한 BSearch 함수의 while문 내의 배열 중앙 값과 찾는 값이 비교연산인 ==가 연산횟수를 대표함
  • 하지만 순차 탐색과는 다르게 n이 쉽게 정의되지 않음
    • 데이터의 수 n이 n/2, n/4, n/8, …, 1이 될 때까지 비교연산을 진행
    • 마지막으로 n이 1일 때 비교연산을 한번 더 수행(worst case, 수가 존재하지 않을 경우)
    • 데이터의 수가 8일 경우 8, 4, 2, 1로 총 4회의 연산 수행
  • 좀 더 정리하자면 다음과 같음
    • n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회 진행
    • 데이터가 1개 남았을 때, 이때 마지막으로 비교연산 1회 진행
    • 따라서 $T(n)=k+1$이 됨
  • k를 구하는 과정은 다음과 같음
    • n이 1이 되기까지 2로 나눈 횟수 k에 대해 n과 k에 관한 식은 다음과 같음
    • $n\times (\frac{1}{2})^{k}=1$ 이므로 양변에 log를 씌워 정리하면 $k=\log_{2}n=k$가 성립
  • 따라서 +1항은 근사화가 가능하므로 $T(n)=\log_{2}n$으로 정의됨

빅-오 표기법(Big-Oh Notation)

  • 빅-오라는 것은 함수 $T(n)$에서 가장 영향력이 큰 부분이 어딘가를 따지는 것임
  • $T(n)=n^{2}+2n+1$일 때, n이 매우 커지게 됨에 따라 $T(n)\approx n^{2}$가 됨
  • 이를 $O(n^{2})$라 하고, Big-Oh of $n^{2}$ 라고 읽음
  • 빅-오는 다항식 T(n)에 대해 최고차항의 차수로 정의 됨
    • $T(n)=5n^{3}+3n^{2}+2n+1$ -> $O(n^{3})$
  • 즉, 시간복잡도함수 T(n)에서 실제로 큰 의미를 갖는 것은 최고차항의 차수가 됨
    • 하지만 이는 식의 종류에 따라 다르므로(다차원 다항식에만 적용가능), 다양한 형태의 빅-오 표기들이 존재

대표적인 빅-오

  • $O(1)$
    • 상수형 빅-오
    • 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘을 뜻함
    • 예를 들어 연산의 횟수가 데이터 수에 상관없이 3회 진행되는 알고리즘일지라도 O(3)이 아닌 O(1)로 표기
  • $O(\log{n})$
    • 로그형 빅-오
    • 데이터 수의 증가율에 비해 연산횟수의 증가율이 훨씬 낮은 알고리즘을 의미(바람직한 유형)
    • 로그의 밑이 얼마냐에 따라 차이가 나나 알고리즘의 성능 관점에서 매우 미미하기에 대부분 무시됨
  • $O(n)$
    • 선형 빅-오
    • 데이터의 수와 연산횟수가 비례하는 알고리즘을 의미
  • $O(n\log{n})$
    • 선형로그형 빅-오
    • 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘
    • 많은 알고리즘들이 이 형태를 띔
  • $O(n^{2})$
    • 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘
    • 데이터의 양이 많은 경우에는 적용하기 부적절 (중첩된 반복문의 사용)
    • 중첩된 반복문의 사용은 알고리즘 디자인에서 바람직하지 못함
  • $O(n^{3})$
    • 데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘
    • 삼중으로 중첩된 반복문 내에서 알고리즘 관련 연산이 진행되는 경우
    • 바람직하지 못한 꼴
  • $O(2^{n})$
    • 지수형 빅-오
    • 사용하는것 자체가 바람직하지 못한 알고리즘
  • 빅-오간의 성능은 아래로 갈수록 점점 나빠지는 꼴
    • 즉, 연산량이 기하급수적으로 증가하게 되므로 위에 가까울수록 좋은 알고리즘이다

순차 탐색 알고리즘과 이진 탐색 알고리즘의 비교

  • 순차 탐색 알고리즘의 T(n) 함수: $T(n) = n$ -> $O(n)$
  • 이진 탐색 알고리즘의 T(n) 함수: $T(n) = \log_{2}{n}+1$ -> $O(\log{n})$
  • 실제 보기엔 $O(n)$과 $O(\log{n})$정도의 차이면 큰 차이가 아니라 하나, 실제로는 엄청난 차이를 보이는 것
    • $O(\log{n})$의 성능이 훨씬 우세

Related Posts