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

1-1 자료구조의 기본적인 이해

• 자료구조란 무엇인가?

프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다. 데이터의 저장을 담당하는 것이 자료구조이다. 즉, 넓은 의미에서 int형 변수도, 배열도 자료구조의 일종이다.

• 자료구조와 알고리즘

자료구조가 데이터의 표현 및 저장밥법을 뜻한다면, 알고리즘은 표현 및 저장된 데이터를 대상으로 하는 문제의 해결 방법을 뜻한다.

예를 들어 다음의 배열 선언은 자료구조적 측면의 코드이다.

int arr[10] = {1,2,3,4,5,6,7,8,9,10};

반면 배열에 저장된 모든 값의 합을 더하는 반복문의 구성은 알고리즘적 측면의 코드이다.

for(idx = 0l idx<10; idx++)
sum += arr[idx];

이렇듯 자료구조가 결정되어야 그에 따른 효율적인 알고리즘을 결정할 수 있기 때문에 둘은 밀접한 관계를 갖는다.

자료구조에 따라서 알고리즘은 달라지고 알고리즘은 자료구조에 의존적이다.

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

• 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)

잘 동작하는 것을 기본으로 좋은 성능까지 보장받기 위해선 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다.

알고리즘을 평가하는 두 가지 요소는 다음과 같다.

1. 어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느린가 (속도 -> 시간 복잡도)
2. 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰는가 (메모리 -> 공간 복잡도)

일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행속도에 초점을 둔다.

속도를 평가하기 위해서는 처리해야 할 데이터양의 변화에 따른 속도의 증가 및 감소의 정도를 알아야 한다. 그래서 알고리즘의 수행 속도를 평가할 때는 다음과 같은 방식을 취한다.

1. 연산의 횟수를 센다.
2. 그리고 처리해야 할 데이터의 수 n에 대한 연산 횟수의 함수 T(n)을 구성한다.

함수의 형태로 구성하게 되면 그래프를 통해 데이터의 수 변화에 따른 연산횟수의 변화 정도를 한눈에 파악할 수 있기 때문에 둘 이상의 알고리즘을 비교하기 용이해진다.

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

for(i = 0; i < len; i++){
if(ar[i] == target){
return i;
}
}

값의 동등을 비교하는 == 연산을 적게 수행하는 탐색 알고리즘이 좋은 알고리즘이다. 즉, 탐색 알고리즘에서의 핵심의 동등비교를 하는 비교연산에 있다. 다른 연산들은 == 연산에 의존적이다.

따라서 == 연산의 횟수를 대상으로 시간 복잡도를 분석하면 된다. 이렇듯 알고리즘의 시간 복잡도를 계산하기 위해서는 핵심이 되는 연산이 무엇인지 잘 판단해야 한다. 그리고 그 연산 중심으로 시간 복잡도를 계산해야 한다.

알고리즘을 평가하는 데에 있어서 최선의 경우(brest case)보다 최악의 경우(worst case)가 중요한 판도이다. 평균적인 경우(average case)는 시간 복잡도를 평가하는 정보로 의미를 지니지만, 다양한 자료들이 광범위하게 수집되어야 하기 때문에 편균적인 경우를 계산하는 일은 쉽지 않다. 따라서 일반적인 알고리즘의 평가에는 논란의 소지가 거의 없는 최악의 경우가 선택될 수 밖에 없다.

• 순차 탐색 알고리즘의 시간 복잡도 : 1. 최악의 경우

데이터의 수가 n개일 때, 최악의 경우의 연산 횟수(비교 연산의 횟수)는 n이다.

T(n) = n

• 순차 탐색 알고리즘의 시간 복잡도 : 2. 평균적인 경우

가정 1. 탐색 대상이 배열에 존재하지 않을 확률을 60%라고 가정.

가정 2. 배열의 첫 요소부터 마지막 요소까지, 탐색 대상이 존재할 확률 동일하다.

따라서 배열에 탐색 대상이 존재하는 경우, 그렇지 않은 경우를 나누어서 연산횟수를 계산한다.

-> 탐색 대상이 존재하지 않는 경우의 연산횟수 n

-> 탐색 대상이 존재하는 경우의 연산 횟수 n/2

n * 1/2 + n/2 * 1/2 = 3n/4

=> 탐색 대상이 존재하지 않는 경우와 존재하는 경우의 확률이 각각 50%이므로

따라서 순차 탐색 알고리즘의 평균적인 경우의 시간 복잡도 함수는

T(n) = 3n/4이다.

역시 프로그램의 성격, 데이터의 성격에 따라서 존재할 확률은 50%보다 높을 수도 낮을 수도 있지만 이 부분은 가정되었기 때문에 최악의 경우보다 평균적인 경우의 시간 복잡도는 신뢰도가 낮다.

• 이진 탐색(binary search) 알고리즘

순차 탐색 알고리즘보다 성능이 좋다.

그러나 배열을 상태로 이진 탐색 알고리즘을 적용하기 위해서 "배열에 저장된 데이터는 정렬이 되어 있어야 한다."

그렇기 때문에 이진 탐색 알고리즘보다 성능이 덜한 순차 탐색 알고리즘도 유용한 알고리즘이다.

1. 배열 인덱스의 시작(0)과 끝의 인덱스를 확인

2. 시작과 끝의 인덱스를 합하여 그 결과를 2로 나눈다. (이때 나머지는 버린다.)

3. 2로 나눠서 얻은 가운데의 인덱스 값(i)으로 하여 arr[i]에 저장된 값이 찾으려던 값인지 확인한다.

   -> 맞으면 끝

   -> 다르면 4번으로

4. arr[i]에 저장된 값과 탐색 대상과 대소를 비교한다.

   -> arr[i] > 탐색대상 -> 시작 인덱스는 그대로, 끝 인덱스를 (i-1)로 재설정 ->탐색 범위 인덱스를 시작~(i-1)로 제한한다. -> 다시 2번부터 반복

   -> arr[i] < 탐색대상 -> 시작 인덱스를 (i+1)로, 끝 인덱스를 그대로 재설정-> 탐색 범위 인덱스를 (i+1)~로 제한한다. -> 다시 2번부터 반복

눈여겨볼 점은 탐색의 과정을 진행할 수록 탐색의 대상이 반(1/2)으로 준다는 사실이다.

• 이진 탐색(binary search) 알고리즘 구현

탐색의 시작 위치에 해당하는 인덱스 값을 first, 탐색의 끝 인덱스를 last로 표시한다. 이진 탐색 알고리즘이 진행됨에 따라 first와 last는 가까워진다.

즉, 이진 탐색 알고리즘은 first가 last을 추월할 때까지 진행하면 된다. first가 last을 추월하면 탐색의 대상이 존재하지 않음을 뜻하니 과정을 종료한다.

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

-> first가 last보다 큰 경우 탐색은 실패했다는 것을 의미하고, 탐색을 종료한다.

if(target < ar[mid]){
last = mid - 1; 
}
else{
first = mid + 1;
}

last = first = mid;로 취급하게 된다면 이미 탐색한 범위를 불필요하게 재탐색하게 된다. 더 큰 문제는 탐색의 대상이 배열에 존재하지 않는 경우에 발생한다.

탐색의 대상이 배열에 존재하지 않을 경우 first에 저장된 값이 last보다 커져서 반복문을 탈출할 수 있어야 하는데, +1과 -1처리를 해주지 않으면 결코 first에 저장된 값은 last보다 커질 수 없게 되기 때문에 무한루프에 빠진다.

즉 최대가 first = last라는 말.

• 이진 탐색 알고리즘의 시간 복잡도 계산 : 최악의 경우

역시 알고리즘을 보면

    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;
            }
        }
    }

순차 탐색 알고리즘과 마찬가지로 == 연산이 연산 횟수를 대표하는 연산으로 볼 수 있다.

-> 2로 나눌 때마다 == 연산 실행

-> n(데이터 수)이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회 진행.

-> 데이터가 1개 남았을 때, 이때 마지막으로 비교 연산 1회 진행

즉, 최악의 경우 시간 복잡도 함수는 T(n) = k + 1이 된다.

n이 1이 되기까지 2로 나눈 횟수가 k이니, n x (1/2)^k = 1 (n에 2를 몇 번(k) 나누면 1이 되는지)

n x 2^-k = 1 -> n = 2^k -> log2n = k

따라서 T(n) = log2n이다.

최악의 경우 비교 연산 횟수가 k+1도 함수가 될 것이라고 생각이 들지만, +1은 중요치 않고, 중요한 것은 데이터의 수n이 증가함에 따라서 비교연산의 횟수가 로그적으로 증가한다는 사실이다.

T(n)의 목적은 데이터 수의 증가에 따른 연산 횟수의 변화 정도를 판단하는 것이므로 +1은 중요치 않다.

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

N과 그에 따른 시간 복잡도 함수 T(n)을 오차 없이 구하는 것은 쉽지 않은 일이다.

그럴 때 빅-오를 따지면 되는데, 빅-오란 함수 T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것이다.

ex) T(n) = n^2 + 2n + 1

= n^2 + 2n

= n^2

n	n^2	2n	T(n)	n^2의 비율
10	100	20	120	83.33%
100	10,000	200	10,200	98.04%
10,000	100,000,000	20,000	100,020,000	99.98%

표에서 보이듯 n^2이 차지하는 비율이 절대저이다. n이 조금만 증가해도 n^2이 차지하는 비율은 99%를 넘어선다.

이렇든 T(n) = n^2 + 2n + 1에서 2n + 1이 미치는 영향은 미미해지므로 다음과 같이

T(n) = n^2로 간략화할 수 있고 이를 빅-오 표기법으로 표현하면 다음과 같다.

O(n^2) -> Big-Oh of n^2

• 단순하게 빅-오 구하기

수학적 접근 없이도 T(n)이 다항식으로 표현될 경우, 최고차항의 차수가 빅-오가 된다는 사실을 알면 어렵지 않게 빅-오를 구할 수 있다.

ex) T(n) = 5n^4 + 2n + 9 -> O(n^4)

그리고 이를 일반화하면, 최고차항의 나머지를 지우고, 최고차항의 계수 또한 지운다.

즉, 다항식으로 표현된 시간 복잡도 함수 T(n)에서 실제로 큰 의미를 갖는 것은 최고차항의 차수라는 이야기다.

물론 계수가 매우 큰 경우는 차이가 크게 날 수 있으나, 빅-오는 데이터 수의 증가에 따른 연산횟수의 증가 형태(패턴)을 나타내는 표기법이다.

빅-오의 관점에서 다음 줄은 동일하다.

-> 데이터의 수가 2, 3, 4개로 늘어날 때 연산횟수는 4, 8, 16으로 두 배씩 늘어났다.

-> 데이터의 수가 2, 3, 4개로 늘어날 때 연산횟수는 99, 198, 396으로 두 배씩 늘어났다.

따라서 다음이 의미하는 바는 O(logN), 데이터의 수의 증가에 따른 연산횟수의 증가 형태를 좌표 평면상에 그려놓으면, 증가하는 추세가 둔화되는 형태를 띈다. 다시 말해서 로그 그래프와 유사한 형태를 띈다.

• 대표적인 빅-오

-> O(1) : 상수형 빅-오이다. 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘을 뜻한다. 예를 들어 연산의 횟수가 데이터 수에 상관없이 3회 진행되는 알고리즘일지라도 O(3)이라 하지 않고 I(1)이라고 한다.

-> O(logN) : 로그형 빅-오이다. 데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮기 때문에 바람직한 유형의 알고리즘이다. 로그의 밑에 따라서 차이가 나긴 하지만 성능 관점에서 차이는 미미하기 때문에 대부분 밑의 차이는 무시된다.

-> O(n) : 선형 빅-오이다. 데이터 수와 연산 횟수가 비례하는 알고리즘을 의미한다.

-> O(nlogn) : 선형로그형 빅-오이다. 데이터 수가 두 배 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘을 의미한다.

-> O(n^2) : 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 따라서 데이터 양이 많을 경우 적용하기 부적절하다. 이중으로 중첩된 반복문 내에서 주로 발생. 즉, 중첩 반복문을 지양하자.

-> O(n^3) : 데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 삼중으로 중첩된 알고리즘에 관련된 영상이 진행되는 경우에 발생한다.

-> O(2^n) : 지수형 빅-오이다. 지수적 증가로 사용하기 무리가 있다.

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

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

T(n) = n # 순차 탐색 알고리즘의 T(n) 함수 -> O(n)

T(n) = log2n + 1 # 이진 탐색 알고리즘의 T(n) 함수 -> O(logn)

둘의 비교를 위한 절차.

1. 최악의 경우를 대상으로 비교하는 것이 목적이니 탐색의 실패 유도.
2. 탐색의 실패가 결정되기까지 몇 번의 비교연산이 진행되는지 센다.
3. 데이터 수는 500, 5000, 50000일 때를 기준으로 각각 실험.

n	순차 탐색 연산횟수	이진 탐색 연산횟수
500	500	9
5,000	5,000	13
50,000	50,000	16

위의 표를 통해 O(n)과 O(logn)의 연산횟수가 얼마나 차이나는지 알 수 있다.