알설분 1차시

알설분에서는 컴퓨터로 문제를 해결할 때 사용할 자료구조(1), 그리고 알고리즘(2)에 대하여 주로 다룬다. 알고리즘의 필요 조건 5가지(Input, Output, Definiteness, Finiteness, Effectiveness)중에서는 Finiteness를 살펴볼 예정임.

(Finiteness: 알고리즘..이라고 불리기 위해서는 어떠한 입력이 주어지더라도 유한한 시간 내에 종료하는 것이 보장되어야 함.)

좋은 알고리즘(효율적인 알고리즘)?

좋은 알고리즘이란 자고로 입력의 규모(크기)에 대해 다항시간 내에 종료되어야 한다.

여담: 그 정반대.. NP-Complete

'좋은 알고리즘'이 존재하지 않음. Bin Packing이 그 예시이다.

Bin Packing
서로 용량이 다른 n개의 파일이 있고, 이를 CD에 모두 저장하여야 한다. 필요한 CD의 최소 갯수는 몇개일까? (CD는 720MB 용량을 가짐)

또 다른 예시로는

Independent Set
그래프 G = (V, E) 내에서 임의의 노드를 k개 추출할 때, 추출한 노드 내에 서로 직접 연결되어있는 엣지가 하나도 없애 할 수 있는 최대의 k는 무엇일까?

NP-Complete 문제들중에 하나라도 해답을 찾으면 나머지 NP-Complete 문제 또한 푸는게 가능하다고 함.

예시: 검색에서

만약 정렬되되어 있는 배열 내에서 특정 원소의 위치를 찾아야 한다면.. 굳이 Sequential하게 찾을 필요는 없겠죠 당연함 Binsearch가 있음. '좋은 알고리즘'이 아까 말한 것 처럼 입력 크기에 대한 다항시간 내에 종료되는거긴 한데, 그런 좋은 알고리즘 내에서도 당연히 더 입력 크기에 비해서 소모되는 리소스가 덜 가파르게 늘어난다면 '더 좋은 알고리즘'이라고 부를 수 있겠죠 그런 면에서 보면 O(log n)을 쓰는 Bin Search보다 O(n)을 쓰는 Sequential Search가 덜 좋다..라고 볼 수 있는 것.

예시: 피보나치 수열의 n번째 수 구하기

recursive algorithm을 쓰는 이유는 일단.. 상당히 직관적이다. 재귀적으로 정의되는 문제는 당연히 재귀적으로 코드를 적었을 때 더 읽기 쉽잖아요.

그럼 피보나치 수열의 n번째 수는 수식으로 이렇게 정의되는데

$$f_0 = 0, f_1 = 1, f_n = f_(n-1) + f_(n-2) for n >= 2$$

코드로 그대로 옮기면 이렇다

func f(int n) {
  match n {
    case 0 {
      return 0
    }

    case 1 {
      return 1
    }

    case 2 <= $ {
      return f(i - 1) + f(i - 2)
    }
  }
}

이 코드의 실행 순서는 이진트리처럼 볼 수 있는데, 그럴 때 코드의 실행 시간은 트리의 전체 노드 수와 정비례 관계에 있게 된다.

T(0) = 1
T(1) = 1

T(n) = T(n - 2) + T(n - 1) + 1

$T(n) <= c * 2^n - 1$ 라고 가정하고 이에 원본 점화식을 대입하면

$$
T(n - 2) + T(n - 1) + 1 <= c * 2^n - 1
$$

좌변에 가정식을 대입해도 여전히 좌변은 우변보다 작아지게 된다.

$$
(c * 2^(n - 2) + 1) + (c * 2^(n - 1) + 1) - 1 <= c * 2^n - 1
2 <= c * 2^n - c * 2^(n - 2) - c * 2^(n - 1)
2 <= c * 2^n * (1 - 1/4 - 1/2)
2 <= c * 2^n * 1/4
8 <= c * 2^n
$$

이 되는데, 2 이상의 자연수 n을 대입해보면

$n = 2 -> 8 <= c * 4, 2 <= c$
$n = 3 -> 8 <= c * 8, 1 <= c$
$n = 4 -> 8 <= c * 16, 1/2 <= c$

위 점화식을 만족하는 가장 작은 c는 2이다. 그래서 $T(n) <= 2^(n + 1) - 1$이 되고, 자연히 $O(2^n)$이 됨을 알 수 있음.

반면 재귀를 안 쓰고 그냥 포문으로 돌리면

func f(int n) {
  assert(1 < n)

  int history[0, 1]

  for(int i = 2; i <= n; i++) {
    history[i] = history[i - 2] + history[i - 1]
  }

  return history[n]
}

리니어하게 끝난다. $O(2^n)$과 $O(n)$의 대결이다.

비용의 Order

대체로 알고리즘의 비용이라고 하면 가장 먼저는 시간복잡도를 말 하고 그 다음에 공간복잡도임. 우리가 O(n2)다 O(nlogn)이다 하는게 Big O Notation이라고 하는데, 입력 크기에 대한 비용함수가 최대 어느정도까지 커질 수 있는지를 말함. O(nlogn)이면 입력이 n일 때, 비용 함수가 k * (nlogn)보다는 작아진다는 뜻(특정 임계 이상으의 n에서 소모 시간을 k*nlogn보다 작게 만드는 양의 실수 k를 찾을 수 있다는 뜻).

Big O 말고 Big Omega도 있는데 얘는 반대로 비용 함수가 더 커지는 임계 n과 배율 k를 찾을 수 있다는거고, Big O랑 Big Omega로 표현한 시간복잡도가 동일하다면 이건 Big Theta라고도 함..!! 상한과 하한을 동일한 함수로 표현할 수 있다면 사실상 비용함수를 올바르게 추론한건데, 왜 Big Theta가 아니라 Big O를 더 널리 쓰는진 모르겠음.

두 시간복잡도 함수의 Order를 비교하고 싶으면(뭐가 더 효율적인지 알고 싶으면) 분수로 나눠서 극한으로 보내버리면 됨. lim(n -> inf, n: T_1(n)/T_2(n)) 하면 됨..

연결된 페이지 (Inlinks)

연결된 페이지가 없습니다.