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

Contents

1. 시작하며...
2. 자료구조와 알고리즘
3. 알고리즘 성능 측정
4. 마치며...

시작하며...

자 구르미의 "Computer Science 정복하기 - 자료구조"의 첫 번째 장입니다.첫 장의 대부분의 내용은 책 "윤성우의 열혈 자료구조"의 첫 장 "자료구조와 알고리즘의 이해"를 요약이 주를 이루고 있습니다.혹시 이해가 안가는 부분이 있다면 책을 참고해주시면 좋겠습니다. 이 장의 대략적인 내용은 다음과 같습니다.

• 자료구조와 알고리즘 용어 정의
• 순차 탐색과, 이진 탐색을 예로 알고리즘 성능 측정

이 장의 소스코드는 다음을 참고해주세요.

 

url: https://github.com/gurumee92/datastructure

branch: ch01

code directory: src/ch01

 

자 시작합시다!

자료구조와 알고리즘

우리는 공부하기 이전에 무엇을 공부하는지 정확히 알 필요가 있습니다. 우리가 공부하는 것은 무엇이죠? 네 맞습니다. 자료구조입니다. 자료구조는 무엇일까요? 먼저 이 질문을 답하기 전에 먼저 프로그래밍의 정의는 무엇일까요? 책 "윤성우의 열혈 자료구조"에서는 프로그래밍의 정의를 다음과 같이 표현하고 있습니다.

 

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

 

여기서 "데이터를 표현하는 것"이 바로 자료구조입니다. 다시 바꿔 표현하자면, "프로그래밍을 처리하기 위한 데이터들을 담는 적절한 형태"라고 말할 수 있습니다. 그래서 자료구조는 대표적으로 다음과 같이 나눌 수 있습니다.

 

• 기본 데이터 타입
  • 정수형
  • 실수형
  • 문자형
  • 문자열
• 선형 자료 구조
  • 배열
  • 리스트
  • 스택
  • 큐
• 비선형 자료 구조
  • 트리
  • 그래프
• 파일 구조
  • 순차 파일
  • 색인 파일
  • 직접 파일

컴퓨터에서는 파일 역시 "데이터"이기 때문에 파일 구조 역시 자료 구조의 한 예로 볼 수 있습니다. 우리가 주로 살펴 볼 것은 선형 자료구조와, 비선형 자료구조입니다.

 

참고적으로 "알고리즘"에 대해 알아봅시다. 자료구조가 "데이터를 표현하는 것"이라면, 알고리즘은 "표현된 데이터를 처리하는 것"입니다. 따라서, 알고리즘은 자료구조에 의존적입니다. 많은 알고리즘 기법이 있습니다만, 이것은 우리가 주 목표가 아닙니다. 따라서, 우리는 자료구조와 관련된 알고리즘들과 정렬 알고리즘들만을 간략하게 살펴보도록 하겠습니다.

알고리즘 성능 측정

본격적으로 자료구조를 공부학기 전에알고리즘 성능 측정에 대해서 알아보도록 하죠. 알고리즘의 성능 측정의 주요 지표는 다음과 같습니다.

 

• 공간 복잡도
• 시간 복잡도

여기서 공간 복잡도는해당 알고리즘이 문제를 풀기 위해서 필요한 메모리 공간의 크기를 뜻합니다. 중요한 지표입니다만, 보통은 시간 복잡도를 더 많이 분석하는 편입니다. 시간 복잡도는해당 알고리즘이 얼마나 빠르게 문제를 해결하는가입니다. 여기서 얼마나 빠르게는 시간 측정도 있습니다만, 보통, 자료구조, 알고리즘에서 시간 복잡도는연산 횟수를 뜻합니다.

 

프로그래밍에서 연산은 수도 없이 많습니다. +, - 등의 산술연산, >, < 등의 비교 연산들이 있습니다. 어떤 연산을 연산 횟수로 쳐야 할까요? 바로,알고리즘에서 제일 중요한 연산의 횟수로 쳐야 합니다. 음... 살짝 두루뭉술하죠? 간단한 예를 들어봅시다. 당신은 주어진 배열의 모든 수를 더하는 프로그램을 만들어야 합니다. C로 프로그램을 만들면 다음과 같습니다.

 

src/ch01/ex01.c

int Sum(int arr[], int len){ 
    int result = 0; 
    
    for (int i=0; i<len; i++){ 
        result += arr[i]; 
    }
    
     return result; 
}

 

이 프로그램에서 주요 알고리즘은 배열의 모든 수를 더하는 것입니다. 이 모든 수를 더할 때 가장 중요한 연산은 바로 더하기입니다.

 

여기서 공간 복잡도는 배열의 크기입니다. len즉, 배열의 길이에 비례하지요. 만약 배열의 길이가 N이라면, 필요 메모리 공간 역시 N입니다. 이 때 공간 복잡도는O(N)이라고 표현합니다.

 

그럼 시간 복잡도는 무엇일까요? 앞서 말했듯이더하기 연산의 횟수입니다. 시간 복자도 역시len, 배열의 길이에 비례합니다. 배열의 길이가 N이라면 연산 횟수도 N번이지요. 이 때 시간 복잡도는O(N)이라고 표현합니다.

 

참고!

빅-오 표기법 O(N)은 빅-오 표기법입니다. 알고리즘 측정 시, 자주 쓰이는 표기법입니다. 빅오는 연산 수식 최대 차항을 따릅니다. 최대 차항이 작을수록 빠른 알고리즘입니다. 알고리즘 빠르기 O(1) > O(log2(N)) > O(N) > O(N ^ k) > O(k ^ N) 수식과 빅오 표기법은 아래 표를 참고하세요.

 

수식	최고 차항	빅-오 표기법
n	n	O(n)
n^2 + 2n + 1	n^2	O(n^2)
2n^2 + 2n	n^2	O(n^2)
log2(n) + 1	log2(n)	O(log2(n))
1	K	O(1)

 

그럼 다른 문제를 살펴볼까요? 당신은 주어진 배열 안에서 주어진 수를 찾는 프로그램을 짜야 합니다. 탐색에 있어서 가장 중요한 연산은 무엇일까요? 주어진 수와 배열 안의 숫자를 비교하는 것입니다.

 

이번에는 대표적으로 가장 쉬운 탐색 알고리즘 2가지, 순차 탐색과 이진 탐색을 예로 들어 성능 비교를 해보겠습니다. 먼저 순차 탐색입니다. 순차 탐색은 말 그대로 배열 안의 숫자들을 순차적으로 순회하면서 주어진 수와 비교합니다. 이를 함수로 표현하면 다음과 같습니다.

 

src/ch01/ex02.c

int LinearSearch(int arr[], int len, int target){ 
    for (int i=0; i<len; i++){ 
        if (arr[i] == target) { 
            return i; 
        } 
    }
    
    return -1; 
}

 

위 함수는 배열의 길이동안 순회하면서, 주어진 숫자target과 비교합니다. 만약 같으면 해당 인덱스i를 반환합니다. 배열 안에서 해당 숫자를 찾지 못하면-1을 결과로 반환하죠.

 

여기서 공간 복잡도는 배열의 크기(길이)입니다. O(N)이죠. 시간 복잡도는 어떨까요? 시간 복잡도는 보통 다음의 2가지의 경우를 생각해야 합니다.

 

• 최악의 경우 시간 복잡도
• 평균 시간 복잡도

최악의 시간 복잡도는 말 그대로 최악일때, 알고리즘의 시간 복잡도입니다. 위 순차 탐색의 최악의 경우는 모든 배열을 순회하더라도 숫자를 찾지 못했을 경우입니다. 이 경우 연산의 횟수는 배열의 길이입니다. O(N)이죠.

 

평균 시간 복잡도는 구하려면, 몇 가지 가정이 필요합니다. 여기서는 다음을 가정으로 세우겠습니다.

 

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

만약 탐색 대상이 존재하지 않을 경우는 연산의 횟수는 몇 번일까요? 정답은배열의 길이만큼 연산을 해야 합니다. 간단하게N이라고 하죠. 만약 탐색 대상이 존재할 경우 연산의 횟수는 몇번일까요? 이 경우 가정 2번을 통해서 연산 횟수는 근사치로N/2입니다. 그래서 다음 수식이 평균 시간 복잡도를 구하는 수식입니다.

 

1/2 * (N + N/2)

 

여기서 앞의1/2는 해당 숫자가 존재할 확률 50%입니다. 그리고N은 없을 경우의 연산 횟수,N/2는 탐색 대상이 있을 때, 연산의 횟수입니다. 따라서3N/4의 시간 복잡도를 지닙니다.

 

이번에는이진 탐색을 분석해볼까요? 먼저 이진 탐색은, 다음 조건이 필요합니다.

 

주어진 배열은 오름 차순으로 정렬된 상태입니다.

 

예를 들어1, 2, 3, 4, 5이런 식으로 배열이 정렬되어 있어야 합니다. 탐색을 하게 되면 반을 탐색 공간에서 제외하기 때문에 정렬 된 상태에서 이진 탐색이 제대로 동작하게 됩니다. 좀 더 구체적인 예를 들어볼까요?

 

주어진 배열 1, 2, 3, 4, 5
찾는 숫자 4

 

이 때, 배열의 정 중앙의 숫자와 비교합니다.

 

탐색 공간의 중간 : (0 (첫 인덱스) + 4 (마지막 인덱스)) / 2 = 2

3 (탐색 공간의 중간에 위치하는 숫자) < 4 (탐색 대상)

 

이 때 시작 위치를 탐색 공간 중간보다 1칸 오른쪽으로 해서 반으로 줄입니다. 그리고 같은 연산을 진행합니다.

 

탐색 공간의 중간 : (3 (아까 중앙 인덱스 2 의 한 칸 오른쪽 인덱스) + 4) / 2 = 3

4 (탐색 공간의 중간에 위치하는 숫자) = 4 (탐색 대상)

 

이제 탐색 공간을 찾았으면 해당 인덱스 3을 반환하는 것이죠. 만약 탐색 숫자보다 중앙의 위치한 수가 크면, 반대로 마지막 위치를 중간보다 1칸 왼쪽으로 해서 반으로 공간을 줄이면 됩니다. 코드를 살펴보겠습니다.

 

src/ch01/ex03.c

int BinarySearch(int arr[], int len, int target){ 
    int start = 0; 
    int last = len-1; 
    
    while (start <= last){ 
        int mid = (start + last) / 2; 
        int search = arr[mid]; 
        
        if (search == target) { 
            return mid;     
        } else if (search < target) { 
            start = mid + 1; 
        } else { 
            last = mid - 1; 
        } 
    } 
    
    return -1; 
 }

 

근데 정 중앙에서 1칸을 더 오른쪽/왼쪽 이동하는 것일까요? 왜냐하면,중앙의 숫자와 같지 않을 경우 이 공간을 탐색할 필요가 없기 때문입니다. 만약 mid + 1(-1) 이 아니고 mid 위치로 옮긴다며느 무한 반복할 수 있는 경우의 수가 생겨버립니다.

 

그리고while 문의 조건 start<=last를 주의 깊게 살펴봐 주세요. start 가 last보다 클 때는, 탐색이 이미 끝났음을 의미하는 것입니다.

 

이제 이진 탐색의 알고리즘을 측정해볼까요? 공간 복잡도는 순차 탐색과 동일하게 배열의 크기(길이)입니다 시간 복잡도를 살펴보죠. 평균 시간복잡도는 굉장히 구하기 어렵기 때문에 최악의 경우만 살펴보도록 하겠습니다. 최악의 경우는 맨 끝에 탐색 대상이 존재할 경우입니다. 이 경우 N개에 대해서 다음의 횟수를 가지죠.

 

탐색 크기 N개 연산 1회

탐색 크기 N/2 개 연산 1회

탐색 크기 N/4 개 연산 1회
...

 

즉, 1개일 때, 1번, 2개일 때 2번(1 + 1), 4개일 때, 3번(2 + 1) 8개일 때 4번(3 + 1) 이런식입니다. 그렇다면, 다음처럼 일반화가 가능합니다.

 

N이 1이 될 때까지 연산 횟수는 N을 2로 나눈 수 K (K = log2(N))

N이 1일 때, 연산 1번

 

T(N) = K + 1

T(N) = log2(N) + 1

 

이 경우 시간 복잡도는O(log2(N))이라고 표현합니다. 즉 우리는최악의 경우, 순차 탐색 보다 이진 탐색이 효율적인 알고리즘이라고 판단할 수 있습니다.

마치며...

이번 장에서는 대략적인 자료구조와 알고리즘의 용어 정의, 알고리즘 성능 측정을 위한 방법을 살펴보았습니다. 다음 장에서는 "재귀"라는 자료구조와 알고리즘에서 주로 쓰이는 코드 기술을 살펴보겠습니다. 수고하셨습니다.