알고리즘

정의

• an Efficient method for solving a problem using a finite sequence of instructions
• a list of well-defined instructions for completing a task
• 컴퓨터를 이용한 효율적인 문제 해결 기법

요구 조건

• 입력(Input)
  • 모든 알고리즘은 주어진 문제(Input)을 해결해야 함
  • 입력 없이는 문제 해결을 시작할 수 없음
  • 입력은 미리 정의된 양식을 준수해야 함
• 출력(Output)
  • 모든 알고리즘은 문제를 해결한 결과(Output)를 보고해야 함
  • 결과를 보고하지 않는 알고리즘은 의미 없음
  • 출력은 미리 정의된 양식을 준수해야 함
• 명확성(Definiteness)
  • 알고리즘의 단계는 다른 해석이 존재하지 않아야 함
  • 2가지 이상의 해석이 가능한 모호한(Implicit) 지시문을 지양할 것
  • 객관적으로 유일한 해석만 가능한 명시적인(Explicit) 지시문을 지향할 것
• 유한성(Finiteness)
  • 알고리즘은 반드시 유한한 횟수의 연산을 통해서 결과를 도출해야 함
  • 무한한 연산의 반복(무한 루프)은 허용하지 않음
• 효율성(Efficiency)
  • 알고리즘은 자원을 최소로 사용하면서 결과를 도출해야 함
    • 시간적 효율성(Temporal Efficiency)
    • 공간적 효율성(Spatial Efficiency)
    • 전력적 효율성(Power Efficiency)

요구 조건 예시 - 탐색 알고리즘

• 입력: n개의 집합 + 찾고자 하는 원소의 키
  • {1, 3, 6, 2, 4} + 2
• 출력: 찾고자 하는 원소가 있으면 1, 없으면 0
  • {1, 3, 6, 2, 4} + 2 → 1
  • {1, 3, 6, 2, 4} + 5 → 0
• 명확성: 탐색 알고리즘은 다른 해석이 불가능함
• 유한성: 모든 원소를 한번씩 찾으면 끝
• 효율성: 순차탐색 → 이진탐색

알고리즘의 중요성

• 피보나치 수열: Fₙ₊₂ = Fₙ₊₁ + Fₙ
• Bruteforce Solution: 피보나치 수열의 식을 바로 적용한 재귀 함수 기반의 알고리즘
  • 연산 시간: O(2ⁿ)
  • 비효율적(지수시간문제)

int Fib (int n) {
    if (n==0 || n==1)
        return n;
    return Fib(n-1) + Fib(n-2);
}

• Iterative Solution: 피보나치 수열의 결과를 저장하는 배열을 이용하는 반복 구조의 알고리즘
  • 연산 시간: O(n)
  • 추가적인 저장공간 요구 → O(n) (Memoization)

int Fib_iterative (int n) {
    int FS [n+1];
    FS [0] = 0;
    FS [1] = 1;
    for (int i = 2; i <= n; i++)
        FS [i] = FS [i-1] + FS [i-2];
    return FS [n];
}

• Divide-and-Conquer Solution: 피보나치 수열에 대한 kⁿ 접근 방법
  • 피보나치 수열을 kⁿ으로 표현
  • kⁿ을 계산하는 분할정복 알고리즘 → O(log n)

int get_k_n (int k, int n) {
    if (n==0)
        return 1;
    if (n==1)
        return k;
    int kn = get_k_n (k, n/2);
    return kn * kn;
}