반응형

01-1 자료구조와 알고리즘

"프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다"

  • 자료구조 : 데이터의 표현 및 저장방법
  • 알고리즘 : 표현 및 저장된 데이터를 대상으로 하는 '문제의 해결 방법'

→ 자료구조에 따라서 알고리즘은 달라지고, 알고리즘은 자료구조에 의존적

본 책에서는 선형구조→비선형 구조까지 다룸 (파일구조x, 단순구조 x)

 

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

시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)

  • 잘 동작하는 것에 더하여 좋은 성능을 보장하기 위해 자료구조와 알고리즘을 분석하고 평가할 수 있어야 함 (만능은 존재하지 않음)
  • 시간복잡도 : 속도에 해당하는 알고리즘의 수행시간 분석 결과 (cpu에 얼마나 부하를 주는가?)
  • 공간복잡도 : 메모리 사용량에 대한 분석 결과

일반적으로 알고리즘을 평가할 때 메모리의 사용량보다 실행속도에 초점을 둠. 공간복잡도는 보조적인 역할

Q. 어떻게 속도를 평가하나?

  • 특정 상황에 대해서 속도를 재는 것은 무의미
  • $\because$ 처리해야 할 데이터 양의 변화에 따라 속도의 증가 및 감소의 정도가 달라지기 때문
  • 위의 이유로 알고리즘의 수행속도를 평가할 때 다음과 같은 방식을 취함
    1. 연산의 횟수를 셈
    2. 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성
  • 식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있고, 다른 알고리즘들의 시간복잡도를 비교할 수 있음

알고리즘은 상황에 맞게 종합적으로 사고하고 판단하여 선택해야 함

  • 데이터의 수가 많아짐에 따른 연산횟수의 증가 정도가 중요하므로 알고리즘 A가 B보다 훨씬 좋은 알고리즘. T(n)함수에 대한 패턴이 중요함
  • 그렇다고 알고리즘 B가 필요없는게 아님
    • B와 같은 성격의 알고리즘은 A보다 구현이 쉬워 데이터의 수가 많지 않고 성능에 덜 민감한 경우라면 구현의 편의를 위해 B를 선택하기도 함

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

#include<iostream>
using namespace std;

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)
		cout<<"탐색 실패"<<endl;
	else
		cout<<"타겟 저장 인덱스 : "<<idx<<endl;

	idx = LSearch(arr, sizeof(arr) / sizeof(int), 7);
	if (idx == 01)
		cout<<"탐색 실패"<<endl;
	else
		cout<<"타겟 저장 인덱스 : "<<idx<<endl;
	return 0;
}

타겟 저장 인덱스 : 3
타겟 저장 인덱스 : -1

  • 좋은 탐색 알고리즘에서는 비교하는 '==' 연산이 적게 수행되어야 함
    • '<'와 '++'는 '=='연산자가 true를 반환할 때까지 수행이 됨

최악의 경우와 최상의 경우

  • 탐색의 대상이 되는 요소의 수(ex) 배열길이)가 n인 경우,
    • 운이 좋아서 찾고자 하는 값이 배열의 맨 앞에 저장된 경우, 연산 횟수 1회 (best case)
    • 운이 없어서 찾고자 하는 값이 배열의 맨 뒤에 저장된 경우, 연산 횟수 n회 (worst case)
  • 알고리즘 평가에 있어 성능평가에서 중요한 것은 worst case

Q. 평균적인 경우를 따져야 하는 것 아닌가?

A. 계산하는 것이 쉽지 않음. 다양한 이론 및 가정이 포함되어야 함. 아래의 average case 참고

순차 탐색 알고리즘 시간복잡도 : worst case

데이터 수가 n개일 때, 최악의 경우에 해당하는 연산횟수는 n

$\therefore T(n)=n$

순차 탐색 알고리즘 시간복잡도 : average case

평균적인 경우의 연산 횟수 계산을 위한 두가지 가정

  • 가정 1. 탐색 대상이 배열에 존재하지 않을 확률이 50%
  • 가정 2. 배열의 첫 요소부터 마지막 요소까지, 탐색 대상이 존재할 확률은 동일

case1. 배열에 탐색대상이 존재하지 않는 경우의 연산횟수

  • 연산횟수 n

case2. 탐색 대상이 존재하는 경우의 연산횟수

  • 연산횟수 n/2
    • 길이가 7인 배열의 경우, 위의 가정 2에 따라 각 배열요소에 탐색 대상이 존재할 확률이 동일하므로 7번 탐색하면, 연산 횟수가 1+2+3+4+5+6+7 = 28, 평균 28/7 = 4회
    • n/2 = 3.5회이지만, 근사치 계산 (수식이 간결해지고 배열의 길이가 길어질수록 근사치 계산결과에 가까워짐)
  • 최종적으로는 가정 1에 따라, 1/2n + 1/2n/2 = 3/4*n
  • 최악의 경우에 비해서 상대적으로 average case에 대한 시간복잡도를 구하기 쉽지 않고 신뢰도도 높지 않음
    • 앞서 2가지 가정을 뒷받침할 근거가 부족
    • 프로그램, 데이터 성격에 따라 배열에 탐색 대상이 존재할 확률이 50%가 아닐 수 있는데 이런 부분이 고려되지 않음

→ 결론 : Worst case를 시간 복잡도의 기준으로 삼는다

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

  • 순차 탐색보다 높은 성능을 보이지만 아래의 조건을 만족해야 함
    • 배열에 저장된 데이터는 정렬되어 있어야 함

ex) 길이가 9인 배열

arr[] = {1, 2, 3, 7, 9, 12, 21, 23, 27};

이 배열을 대상으로 숫자 3이 저장되어 있는지 확인

첫번째 시도

  • 배열 인덱스의 시작과 끝은 각각 0과 8
  • 0과 8을 합하여 그 결과를 2로 나눔 → (0+8)/2 = 4
    • 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인 → NO

 

두번째 시도

  • arr[4] 에 저장된 값 9와 탐색 대상인 3의 대소를 비교
    • arr[4] = 9
    • 찾고자 하는 대상 3
    • 배열이 오름차순으로 정렬되었음을 전제하였기 때문에 탐색 범위를 수정 가능
  • arr[4] > 3이므로 탐색의 범위를 인덱스 기준 0~3으로 제한 (이전 : 0~8)
  • 0과 3을 더하여 그 결과를 2로 나눔. 나머지는 버림. (0+3)/2 = 1.5 ⇒ 1
  • 2로 나눠서 얻은 결과가 1이니, arr[1]에 저장된 값이 3인지 확인 → NO

→ 두번째 시도 만에 탐색의 대상을 반으로 줄임

세번째 시도

  • arr[1]에서 저장된 값 2와 탐색 대상인 3의 대소를 비교
  • 탐색 대상이 더 크므로 탐색의 범위를 인덱스 기준 2~3으로 제한(이전: 0~3)
  • 2와 3을 더하여 그 결과를 2로 나눔. 나머지는 버림. (2+3)/2 = 2.5 → 2
  • 2로 나눠서 얻은 결과가 2이니, arr[2]에 저장된 값이 3인지 확인 → YES

이진 탐색 알고리즘은 탐색의 대상을 반복하여 반씩 떨구어 내는 알고리즘

이진 탐색(Binary Search) 알고리즘의 구현

  • 탐색의 시작 인덱스(first)와 마지막 인덱스(last) 값을 포함하는 범위로, 탐색의 범위를 반으로 줄여나감.

Q. 언제까지 계속되어야 하나?

A. first 와 last가 같아질 때까지? NO. 같아진 경우 하나의 탐색 범위가 있으므로 이때도 탐색해야 함

#include <iostream>
using namespace std;

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

	while (first <= last) **// 중요(등호 포함됨)** 
	{
		mid = (first + last) / 2;

		if (targetValue == ar[mid])
		{
			return mid;
		}
		else //타겟이 아니라면 탐색 대상을 반으로 줄인다. 
		{
			if (targetValue < ar[mid])
				last = mid - 1; //왜 -1을 하였을까?
			else
				first = mid + 1; //왜 +1을 하였을까? 
		}
	}
	return -1;
}

int main()
{
	int arr[] = { 1,2,3,7,9,12,21,23,27 };
	int idx;

	idx = BSearch(arr, sizeof(arr) / sizeof(int), 7);
	if (idx == -1)
		cout << "탐색 실패" << endl;
	else
		cout << "타겟 저장 인덱스 : " << idx << endl;

	idx = BSearch(arr, sizeof(arr) / sizeof(int), 4);
	if (idx== -1)
		cout << "탐색 실패" << endl;
	else
		cout << "타겟 저장 인덱스 : " << idx << endl;

	return 0;
}

타겟 저장 인덱스 : 3 탐색 실패

Q. 위의 코드 중 while 문 조건에서 등호 (=)를 뺀 후 결과는?

탐색 실패 탐색 실패

  • 값 7이 3번째 인덱스에 포함(arr[3] = 7)되어 있음에도 불구하고 탐색 실패의 결과를 얻음

→ "first가 last보다 큰 경우 탐색이 종료됨. 이렇게 종료되었다는 것은 탐색에 실패했음을 뜻함"

결론적으로 while문에서 '='를 빼면, worst case(탐색 범위가 하나만 남은 경우)에 index를 찾을 수 없게 됨

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

데이터의 수 n과 그에 따른 시간 복잡도 함수 T(n)을 정확히 그리고 오차 없이 구하는 것은 대부분의 경우 쉽지 않음

→ '빅-오'라는 것은 함수 T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것

ex) $T(n)=n^2+2n+1$ 은 $T(n)=n^2$ 로 간략화해서 진행할 수 있음

Q. 간략화 할 수 있는 이유는?

A. n의 값이 커질수록 T(n)에서 $n^2$이 차지하는 비율이 절대적으로 큼

표기는 $O(n^2)$로 하고, "빅-오 오브 n^2"로 읽음

단순하게 빅-오 구하기

"T(n)이 다항식으로 표현이 된 경우, 최고차항의 차수가 빅-오가 된다."

대표적인 빅-오

  • $O(1)$ : 상수형 빅-오. 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘
  • $O(logn)$ : 로그형 빅-오. '데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘
  • $O(n)$ : 선형 빅-오. 데이터수와 연산횟수가 비례
  • $O(nlogn)$ : 선형로그형 빅-오. 데이터의 수가 두배로 늘때, 연산횟수는 두배 조금 넘게 증가하는 알고리즘
  • $O(n^2)$ : 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘→데이터 양이 많은 경우 적용하기 부적절
  • $O(2^n)$ : 지수형 빅-오. 연산횟수가 지수적으로 증가

연산횟수 대소 정리

  • $O(1) < O(logn)<O(n)<O(nlogn)<O(n^2)<O(2^n)$

 

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

#include <iostream>
using namespace std;

//Linear search vs Binary search 비교

int BSearch(int ar[], int length, int targetValue)
{
	int first = 0;
	int last = length - 1;
	int mid;
	int opCount = 0; //비교연산의 횟수를 기록

	while (first <= last)
	{
		mid = (first + last) / 2;

		if (targetValue == ar[mid])
		{
			return mid;
		}
		else
		{
			if (targetValue < ar[mid])
				last = mid - 1;
			else
				first = mid + 1;
		}
		opCount += 1;
	}
	cout << "데이터 수 "<<length<<"에 대한 "<<"비교연산횟수 : " << opCount << endl;
	return -1;
}

int main()
{
	int arr1[500] = { 0, };
	int arr2[5000] = { 0, };
	int arr3[50000] = { 0, };
	int idx;

	//배열 arr1을 대상으로, 저장되지 않는 정수 1을 찾으라고 명령 
	idx = BSearch(arr1, sizeof(arr1) / sizeof(int), 1);
	if (idx == -1)
		cout << "탐색 실패" << endl;
	else
		cout << "타겟 저장 인덱스 : " << idx << endl;

	//배열 arr2을 대상으로, 저장되지 않는 정수 1을 찾으라고 명령 
	idx = BSearch(arr2, sizeof(arr2) / sizeof(int), 1);
	if (idx == -1)
		cout << "탐색 실패" << endl;
	else
		cout << "타겟 저장 인덱스 : " << idx << endl;

	//배열 arr1을 대상으로, 저장되지 않는 정수 1을 찾으라고 명령 
	idx = BSearch(arr3, sizeof(arr3) / sizeof(int), 1);
	if (idx == -1)
		cout << "탐색 실패" << endl;
	else
		cout << "타겟 저장 인덱스 : " << idx << endl;

	return 0;
}

데이터 수 500에 대한 비교연산횟수 : 9
탐색 실패
데이터 수 5000에 대한 비교연산횟수 : 13
탐색 실패
데이터 수 50000에 대한 비교연산횟수 : 16
탐색 실패

→ 순차 탐색 알고리즘의 Big Oh 가 O(n) 이므로, 비교해보면 $O(n)$ 과 $O(logn)$의 알고리즘 사이의 연산횟수에서 큰 차이를 보여줌

 
 
반응형
저작자표시 비영리 변경금지

'자료구조' 카테고리의 다른 글

[책리뷰] 윤성우의 열혈 자료구조 Ch3. Linked list 1 - 배열기반  (0) 2024.10.27
[책리뷰] 윤성우의 열혈 자료구조 Ch2. 재귀  (0) 2024.10.27
[자료구조] Stack  (0) 2022.10.04
[자료구조] Linked List - (6) 노드 삭제  (0) 2022.06.12
[자료구조] Linked List - (5) 데이터 조회  (0) 2022.06.12

+ Recent posts

티스토리툴바