자료구조와 알고리즘

 

1. 자료구조와 알고리즘

1.1 자료구조, 알고리즘이란?

■ 자료구조는 자료를 효율적으로 관리하는 방법으로 숫자, 문자, 문자열같은 단순 자료구조와 여러 자료를 한꺼번에 보관하는 복합 자료구조로 나눌 수 있다.

복합 자료구조는 다시 선형(linear) 자료구조와 비선형 자료구조로 나눌 수 있다.

1) 선형 자료구조: 항목들을 순서대로 나열하여 저장한다. 이때 항목을 접근하는 방법에 따라 ① 항목(요소) 접근을 맨 앞 또는 맨 뒤에서 스택, 큐, 덱이 있고 ② 임의의 위치에 자유롭게 접근하여 항목을 삽입 또는 삭제할 수 있는 리스트가 있다.

2) 비선형 자료구조: 트리, 그래프로 더 복잡한 연결 관계를 갖는 구조를 표현한다.

■ 알고리즘은 어떤 문제를 해결해 가는 논리적인 과정이다.

- 예를 들어 단어들이 배열에 저장되어 있다고 하면 배열은 자료구조이고, 단어를 찾는 방법이 알고리즘에 해당된다.

■ 자료구조와 알고리즘은 서로 밀접한 관계가 있으며, 더 개선된 알고리즘을 사용하려면 대부분 더 복잡한 자료구조를 사용해야 한다.

 

1.2 추상 자료형(Abstract Data Type, ADT)

■ 추상 자료형은 데이터 타입을 사용자가 추상적(수학적)으로 정의하는 자료형이다. 

데이터, 연산의 추상적인 모델을 나타내는 개념이며, 데이터의 형태, 어떤 연산(기능)이 수행되야 하는지 혹은 제공되는지를 정의하지만, 데이터나 연산을 어떻게 구현하는가는 정의하지 않는다. 이런 추상 자료형은 파이썬에서 구현하려면 함수보다 클래스로 구현하는 것이 좋다.

 

1.3 알고리즘 성능 분석

■ 좋은 알고리즘은 실행시간이 짧으며(<=> 계산 속도가 빠르며) 메모리같은 컴퓨터 자원을 적게 사용하는 알고리즘이다.

즉, 알고리즘 성능은 계산 속도와 메모리 사용량으로 평가된다. ( 이때 두 측정 지표의 중요도는 실행 시간 > 메모리 공간 이다.)

■ 이렇게 수행 시간, 메모리 사용량 등 알고리즘의 성능을 나타내는 척도를 복잡도(Complexity)라 한다.

■ 따라서 복잡도는 수행 시간에 대한 시간 복잡도와 수행 시, 알고리즘이 얼마나 메모리를 사용하는지에 대한 공간 복잡도가 있다.

■ 시간 복잡도(Time Complexity) 분석은 산술, 비교 등의 기본적인 연산을 고려하여, 알고리즘 수행에 필요한 연산의 개수를 계산한다.

이 연산의 수를 n의 함수로 나타낸 것을 시간 복잡도 함수라 하며 $ T(n)$으로 표기한다.

■ n이 커질수록 알고리즘들 간의 연산 개수가 많이 차이나기 시작한다. 따라서 효율적인 알고리즘은 입력의 개수가 많아도 연산의 수는 낮은 알고리즘이 된다.

■ 예를 들어 

a = 5
b = 7
print(a + b)

위 코드의 연산은 대입, 더하기 연산 등의 연산 횟수를 더하면 되며, 이 예시의 수행 시간은 상수 시간임을 알 수 있다. 이럴 때 빅오 표기법으로 $ O(1)$ 만큼의 시간 복잡도가 걸렸다고 한다. 

■ 몇 가지 예를 더 들어보겠다.

example (A[], n) # input은 n과 리스트 타입인 A
{
    k = └n/4┘;  # 나누기 연산 1번, └ ┘연산 1번, 총 연산 2번
    return A[k]; # 리스트 A에서 k번째 값을 가지고 오는 연산 1번
}

 

이 예시에서는 'k = └n/4┘;'에서 총 2번의 연산을 수행하고, 'return A[k];'에서는 리스트 A에서 k번째 값을 가지고 오는 연산 1번을 수행하여, n의 값에 상관없이 총 3번의 연산이 수행된다.

즉, n에 관계없이 이 알고리즘의 수행 시간은 상수 시간이 소요된다.

example (A[], n)
{
    result <- 0;
    for i <- 1 to n # i = 1, 2, 3, ... n, 총 n 번의 연산을 수행
        result <- result + A[i] # 리스트 A에서 i번째 값을 가지고 오는 연산 1번, 더하기 연산 1번
    return result;
}

이 예시에서는 for 루프가 한 번 실행될 때, for 문의 안쪽에서 총 2번의 연산이 수행되므로 이 알고리즘은 총 2n번의 연산이 수행된다.

따라서 시간 복잡도 함수로 나타내면 $ T(n) = 2n$이다. 즉 n에 비례하는 시간이 소요된다.

example (A[], n)
{
    result <- 0;
    for i <- 1 to n-1 # (n-1)번
        for j <- i+1 to n # (n-i)번
            result <- result + A[i] * A[j];
    return result;
}

이 예시는 바깥쪽 for문과 안쪽 for문에서 각각 (n-1)번, (n-i)번 연산이 수행되고 안쪽 for 문 내에서 리스트 A의 i번째, j번째 항목을 가지고 오는데 각각 연산 1번, A[i]와 A[j]를 곱하는 연산 1번, 그리고 result와 더하는 연산 1번, 총 4번의 연산이 수행된다.

따라서 이 알고리즘은 총 $ 4 × (n-1) × (n-i)  = 4n^2 + ...$ 즉, $ T(n) = 4n^2$이다. 따라서 $n^2$에 비례하는 시간이 소요된다.

example (A[], n)
{
    result <- 0;
    for i <- 1 to n
        for j <- 1 to n
            k <- A[1, 2, ..., n]에서 임의로 └n/2┘개를 선택했을 때, 그 중에서 최솟값
            result <- result + k;
    return result;
}

이 예시는 안쪽 for 문에서 └n/2┘번 연산과 최솟값을 선택하는데 상수(c)번의 연산, 그리고 그 다음 라인에서 더하기 연산 1번을 하므로 총 $ c ×└n/2┘+ 1$번의 연산을 수행한다.

그러므로 총 연산은 $n × n × ( c ×└n/2┘+ 1 ) ≒ n^3 + ...$ 번의 연산을 하는 것이다. 따라서 $n^3$에 비례하는 시간이 소요된다.

factorial(n)
{
    if n = 1 return 1;
    return n * factorial(n - 1);
}

이 예시의 구조는 순환 구조이다. n = 1이 아니면 factorial이 다시 호출되어 연산을 수행한다.

n * factorial(n - 1)의 연산 과정은 n * (n-1)에서 곱하기 연산 1번, (n-1) * (n-2)에서 곱하기 연산 1번, ..., n = 2와 n = 1일때 곱하기 연산 1번, 즉 연산 과정을 다음과 같이 나타낼 수 있다.

즉 1번의 곱하기 연산이 총 n번 있는 것이다. 펙토리얼은 n! = n × (n-1) × ... × 1이므로 곱하기 연산이 n번 수행되는 구조이다.

그러므로 $ T(n) = 1 × n = n$이라 할 수 있다. 따라서 이 펙토리얼 연산은 n에 비례하는 시간이 소요된다.

■ 몇 개의 예시에서 시간 복잡도 함수를 정의할 때 최고차항만 고려하였다. 그 이유는 차수가 가장 큰 항의 영향력이 절대적이기 때문이다. 

- 예를 들어 시간 복잡도 함수 $ T(n) = n^2 + n + 1$에서,

n = 1이면 T(n) = 1 + 1+ 1 이므로 결과값에 최고차항이 영향을 미친 비율은 1/3(33.3%)이라고 할 수 있다.

n = 10이면 T(n) = 100 + 10+ 1 = 111 이므로 $n^2$이 결과값의 90% 정도를 차지하고,

n = 100이면 T(n) = 10000 + 100+ 1 = 10101 이므로 $n^2$이 결과값의 99% 정도를 차지한다. 

즉 n이 점점 커질수록 시간 복잡도에 대한 최고차항의 중요도(영향력)가 절대적임을 알 수 있다.

따라서 최고차항만 고려하고 그 외의 정보는 제외하여 시간 복잡도를 분석하면 된다.

■ 이렇게 알고리즘의 성능을 계산한 다음, 성능을 표기하는 방법에는 빅오(Big Oh) 표기법이 있다.

■ 빅오 표기법의 수학적 정의는 '두 개의 함수 $f(n)$과 $g(n)$이 주어졌을 때, 모든 $n > n_0$에 대해 $| f(n) | ≤ c | g(n) |$을 만족하는 상수 $c$와 $n_0$가 존재하면 $f(n) = O(g(n))$이다.'

이 정의에서 $c$와 $n_0$에 대해 어떠한 제한이 없으므로 정의를 만족하는  $c$나 $n_0$은 무수히 많을 수 있다.

■ 예를 들어 $f(n) = 2n^2 + 3n + 1, g(n) = n^2$이라 할 때, $| 2n^2 + 3n + 1 | < c | n^2 |$를 만족하는 $c$와 $n_0$쌍은 (4, 3), (5, 2), (6, 1), ... 등이 가능하다. 

따라서 위의 정의에 따라 $f(n) = O(g(n)), 2n^2 + 3n + 1 = O(n^2)$이라 할 수 있다. 

n이 증가함에 따라 시간 복잡도 함수의 증가

 

■ 위의 그래프와 같이 $2^n$이 가장 느린, 성능이 떨어지는, 즉 시간 복잡도가 좋지 않은 알고리즘이다. 

- 성능 순으로 나열하면 $O(1) < O(log_n) < O(n^p), 0< p ≤ 1 < O(nlog_n) < O(n^2) < O(2^n) < O(n!)$이며, O(n!)으로 갈수록 시간 복잡도가 높아진다.

■ 단, 빅오 표기법에는 문제점이 하나 있다.

- 예를 들어 $f(n) = 2n + 1$일 때 $O(n)$알고리즘이지만, $O(n^2)$알고리즘이기도 하다.

$n_0 = 1, c = 4$로 잡으면 $n ≥ 1$에 대해 $2n + 1 ≤ 4n^2$이 되어 빅오 표기법 정의가 만족된다. 따라서 $O(n^2)$ 알고리즘이 되는 것이다.

- 이와 같은 문제점의 이유는 빅오 표기법이 n에 따른 함수의 상한을 표기한 것이며, 상한은 여러 개가 존재할 수 있기 때문이다.

■ 이런 문제점을 해결하기 위해 하한을 표시하는 빅오메가(Big Omega), 동일한 함수로 상한과 하한을 나타내는 빅세타(Big Theta)가 있다.

■ 빅오메가의 수학적 정의는 '두 개의 함수 $f(n)$과 $g(n)$이 주어졌을 때, 모든 $n > n_0$에 대해 $| f(n) | ≥ c | g(n) |$을 만족하는 상수 $c$와 $n_0$가 존재하면 $f(n) = \Omega(g(n))$이다.'

■ 빅세타의 수학적 정의는 '두 개의 함수 $f(n)$과 $g(n)$이 주어졌을 때, 모든 $n > n_0$에 대해 $c_1 |g(n)| \leq |f(n)| \leq c_2 |g(n)|$을 만족하는 상수 $c_1, c_2 n_0$가 존재하면 $f(n) = \Theta(g(n))$이다.'

[출처] Complexity ❘ Asymptotic Analysis. · What exactly does big Ө notation… ❘ by Tarun Jain ❘ Medium

■위의 그래프를 직관적으로 보면 빅오는 'f는 g보다 빠르게 증가하지 않는다', 빅오메가는 'f는 g보다 느리게 증가하지 않는다', 빅세타는 'f는 g와 같은 정도로 증가한다'

■ 예를 들어 $f(n) = 2n^2 - 8n$이면 빅오 표기법으로 $f(n) = O(n^2)$으로 표기할 수 있다. 이를 그래프로 보면

f와 g가 상한 관계이므로 빅오 표기법으로 나타낼 수 있기 때문이다.

- 빅오메가는 빅오와 반대 개념이라서 $f(n) = \Omega(n^2)$으로 나타낼 수 있다. 빅오와 동일하게 표기되는데, 

이는 빅오의 반대 개념이므로 빅오메가가 n이 증가함에 따라 $f(n)$이 $n^2$보다 작을 수 없다는 의미이기 때문이다.

- 빅세타는 빅오와 빅오메가가 같은 경우에 사용한다. 따라서 이 예시처럼 빅오와 빅오메가가 $n^2$으로 같은 경우,

$f(n) = \Theta(n^2)$으로 표기할 수 있다. 이는 $f(n)$은 n이 증가함에 따라 $n^2$과 동일한 증가율을 가지기 때문이다. 즉, 동일한 함수로 상, 하한을 만드는 것이다.

■ 입력 데이터에 따라 성능의 차이가 생기며, 3가지로 나누어 평가할 수 있다.

1) 최선의 경우: 수행 시간이 가장 빠른 경우

2) 평균의 경우: 수행 시간이 평균적인 경우

3) 최악의 경우: 수행 시간이 가장 늦은 경우

- 대부분 알고리즘 분석은 최악의 경우를 선택한다. 최선의 경우는 알고리즘의 하한을 계산하기 때문에 최악의 경우 어떠한 정보도 얻을 수 없기 때문에 의미가 없는 경우가 많다.

- 평균의 경우는 모든 입력들의 총합을 입력의 가짓수로 나눠 계산한다. 즉, 모든 입력에 대한 가능성, 모든 경우의 수를 고려해 수행 시간을 계산한다.

- 최악의 경우는 알고리즘 수행 시간의 상한을 계산하므로, '알고리즘이 이 수행 시간보다 더 오래 걸리지 않을 것이다'와 같은 알고리즘에 대한 좋은 정보를 제공한다. 

 

1.4 순환 알고리즘 시간 복잡도 분석

■ 순환 또는 재귀 호출은 자기 자신을 다시 호출하는 기법이다.

■ 예를 들어 펙토리얼을 다음과 같이 순환 함수의 형태로 구현할 수 있다.

def factorial(n):
    if n == 1: return 1
    else: return n * factorial(n-1)

만약 n = 3이면, 순환의 작동 방식은 다음과 같다.

먼저 n = 3일 때, 1) 자기 자신을 호출한다. 이때 n = 2가 되고, 2) 다시 자기 자신을 호출한다. 그러면 3) n = 1이 되어 종료 조건을 수행하고 1을 반환한다. 4) 이 1값은 n = 2일 때, factorial(n - 1) = 1이므로 2 * 1 = 2를 반환한다. 5) 반환된 2는 n = 3일 때 factorial(n - 1) = 2이므로, 최종적으로 3 * 2 = 6을 반환한다.

■ 순환 함수는 위와 같이 자기 자신을 순환적으로 호출하는 부분과 순환을 멈추는 부분인 종료 조건으로 구성해야 한다.

■ 대부분의 경우 순환은 반복 구조로 변환할 수 있다. 

■ 예를 들어 펙토리얼 반복 구조는 

# 반복 구조
def factorial_iter(n):
    result = 1
    for i in range(n, 0, -1): # n, n - 1, n - 2, ..., 1 까지
        result *= i
    return result

■ 이처럼 순환은 반복 구조보다 간결하고 직관적이며 복잡한 문제를 쉽게 해결할 수 있지만, 실행에 있어 대부분 함수 호출이 반복보 구조보다 느리기 때문에 수행 시간과 기억 공간 사용에 있어 비효율적인 경우가 많다.

- 왜냐하면 위의 예시처럼 펙토리얼 순환 함수에 n = 3을 넣었을 때, n = 2, n = 1에 대한 결과를 기억하고 있어야 n = 3일 때의 펙토리얼 값을 구할 수 있었다.

- 즉, n이 증가하면 그만큼의 함수 호출과 기억 공간의 사용이 증가하게 된다.

■ 순환이 더 빠른 경우도 있다. 대표적으로 거듭 제곱을 구하는 문제가 있다.

■ $x^n$을 구하는 함수를 반복 구조로 구현하면,

def power_iter(x, n):
    result = 1
    for i in range(n): # n번 반복
        result *= x
    return result

 

- 이 함수의 시간 복잡도는 $O(n)$이다. 이 구조보다 더 효율적인 알고리즘이 있는데, $x^n = (x^2)^{n/2}$의 공식을 이용하는 것이다. 식에서 볼 수 있듯이 이 공식을 사용하는 의도는 n이 주어졌을 때, n의 크기를 절반씩 줄여 가며 계산하기 위함이다.

- n이 짝수이면 $n^2$을 먼저 계산하고 $\frac {n}{2}$승을 하면 된다. n이 홀수면 $x^2$을 $\frac {(n-1)}{2}$승하고 여기에 $x^1$을 곱해주면 된다. 즉 n에 따라 계산하는 것이다.

1) n이 짝수인 경우

$power(x, n) = power(x^2, n/2) = (x^2)^{n/2} = x^{2(n/2)} = x^n$

2) n이 홀수인 경우

$\text{power}(x, n) = \text{power}\left(x^2, \frac{n-1}{2}\right) \cdot x = \left(x^2\right)^{\frac{n-1}{2}} \cdot x = x^{n-1} \cdot x = x^n$

- 이 알고리즘을 n에 따라 계산하는 순환 함수로 구현하면

def power(x, n):
    if n == 0:
        return 1 # x의 0승은 1
    elif n % 2 == 0: # n이 짝수
        return power(x*x, n//2)
    else: # n이 홀수
        return power(x*x, (n-1)//2) * x

순환적으로 호출될 때 n의 크기가 절반씩 줄어든다.

- 예를 들어 n이 100이면

power(x*x, 100//2) -> 재귀 호출. n = 50 전달 -> power(x*x, 50//2) -> 재귀 호출. n = 25 전달 -> power(x*x, 25//2)

-> 재귀호출. n = 12 전달 -> power(x*x, 12//2) -> 재귀호출. n = 6 전달 -> power(x*x, 6//2) -> 재귀호출. n = 3전달

-> power(x*x, (3-1)//2) -> 재귀호출. n = 1 전달 -> power(x*x, (1-1)//2) -> n = 0 -종료 조건 수행 -> 1 반환

- n을 $2^k$라고 가정하면 $2^k -> 2^k-1 -> 2^k-2 -> ... -> 2^1 -> 2^0$이다. 즉, 순환 호출을 한 번 할 때마다 n의 크기가 절반씩 줄어들며, k 번의 순환 호출이 발생함을 알 수 있다.

- $n = 2^k$이므로 양변에 log를 취하면 $log_{2}{n} = k$가 된다. n이 2의 거듭제곱이 아닌 경우에도 한 번의 순환 호출이 발생할 때, 1번의 곱셈과 1번의 나눗셈이 일어나고, n의 크기를 절반씩 줄이기 때문에 전체 연산의 개수는 $k = log_{2}{n}$에 비례하게 된다. 따라서 이 알고리즘의 시간 복잡도는 \( O(log_{2}{n}) \)이므로 반복 구조인 $O(n)$보다 성능이 좋다고 할 수 있는 것이다.

■ 그러나 특정한 문제를 제외하면, 보통 순환이 더 느린 경우가 많다. 대표적인 예로 피보나치 수열의 계산이 있다.

- 피보나치  수열은 $\text{fib}(n) = \begin{cases} 0, & \text{if, } n = 0 \\ 1, & \text{if, } n = 1 \\ fib(n-2) + fib(n-1), & \text{otherwise} \end{cases}$ 이렇게 정의 자체가 순환적이다.

- 정의에 따라 수열을 만들면 다음과 같은 방식으로 순환 호출을 통해 계산하는 것을 알 수 있다.

■ 피보나치 수열을 코드로 구현하면 다음과 같다.

def fib(n):
    if n == 0: return 0 # 종료 조건
    elif n == 1: return 1 # 종료 조건
    else:
        return fib(n-2) + fib(n-1) # 순환 호출

- 이런 구조의 순환 호출은 비효율적이다. n = 3, n = 4, n = 5, ... 으로 n의 값이 점점 커질수록 호출되는 fib가 다시 fib들을 호출하고, 이 호출된 fib들이 또 다른 fib들을 호출해 마치 호출되는 구조가 깊은 트리 모양이 된다.

- 예를 들어 n = 4일 때 fib(3)은 fib(1)과 fib(2)를, fib(3)에 의해 호출된 fib(2)는 다시 fib(0), fib(1)을 호출한다. 

만약 n = 6으로 fib(6)이면 fib( )함수를 총 25번 순환호출한다.

- 이렇게 비효율적인 이유는 중간에 계산된 값( ex) fib(2), fib(3), ...)을 기억하여 재이용하지 않고 다시 계산하기 때문이다.

- 실제로 이 알고리즘의 시간 복잡도는 $O(2^n)$으로 성능이 좋지 않다.

- 반복 구조를 이용하면 다음과 같이 피보나치 수열을 구현할 수 있다.

def fib_iter(n):
    if n < 2: return n
    a, b = 0, 1
    for i in range(2, n+1):
        tmp = b
        b += a
        a = tmp
    return b

이 알고리즘은 n 번 반복을 하기 때문에 시간 복잡도는 $O(n)$으로 순환 호출로 구현했을 때보다 훨씬 효율적이다.