시간 복잡도 표기법과 알고리즘, 하노이탑

1. 시간 복잡도 표기법

시간 복잡도는 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 변화하는지를 나타내는 개념이다. 대표적으로 빅오(Big-O), 빅세타(Big-Theta), 빅오메가(Big-Omega) 표기법이 사용된다.

1.1 빅오(Big-O) 표기법

• 최악의 경우 시간 복잡도를 나타냄.
• 알고리즘의 실행 시간이 가장 오래 걸리는 경우를 기준으로 평가.
• 입력 크기 n이 커질수록 성능이 어떻게 변하는지를 분석.
• 상한선(Upper Bound)을 나타냄.

예제

• 선형 탐색(순차 탐색) → O(N)
• 선택 정렬 → O(N²)
• 이진 탐색 → O(log N)
• 퀵 정렬(평균) → O(N log N), 최악 → O(N²)

---

1.2 빅세타(Big-Theta, Θ) 표기법

• 평균적인 경우 시간 복잡도를 나타냄.
• 최선과 최악의 경우를 포함하여 입력 크기에 따른 일반적인 실행 시간을 나타냄.
• 상한과 하한을 동시에 포함하여 알고리즘의 평균적인 성능을 표현.

예제

• 특정 정렬 알고리즘의 평균적인 실행 시간: Θ(N log N)

---

1.3 빅오메가(Big-Omega, Ω) 표기법

• 최선의 경우 시간 복잡도를 나타냄.
• 가장 빠른 경우를 기준으로 알고리즘의 실행 시간을 나타냄.
• **하한선(Lower Bound)**을 나타냄.

예제

• 이진 탐색의 최선 시간 복잡도 → Ω(1) (찾는 값이 첫 번째 위치에 있는 경우)

---

2. 빅오, 빅세타, 빅오메가 비교

표기법 설명 의미

O(g(n))	최악의 경우	가장 비효율적인 상황에서 실행 시간의 상한을 의미
Θ(g(n))	평균적인 경우	실행 시간의 상한과 하한이 일치하는 경우
Ω(g(n))	최선의 경우	가장 빠른 실행 시간의 하한을 의미

---

3. 시간 복잡도 분석 방법

1. 반복문(For, While) 분석
   • 단일 반복문 → O(N)
   • 중첩 반복문 → O(N²) (이중 반복문), O(N³) (삼중 반복문)
2. 순차 탐색 (Sequential Search)
   • 정렬되지 않은 배열에서 특정 값을 찾는 알고리즘.
   • 첫 번째 요소부터 마지막 요소까지 탐색.
   • 최악의 경우: 배열에 찾는 값이 없거나 마지막에 위치한 경우 → O(N)
   • 최선의 경우: 첫 번째 요소가 찾는 값일 경우 → O(1)
3. 이진 탐색 (Binary Search)
   • 정렬된 배열에서 특정 값을 찾을 때 사용.
   • 탐색 범위를 절반씩 줄여가며 검색.
   • 시간 복잡도: O(log N) (최악의 경우)
   • 최선의 경우: Ω(1) (첫 번째 요소가 찾는 값일 경우)

---

4. 순환(재귀)과 반복

순환(Recursion)과 반복(Iteration)은 같은 문제를 해결하는 두 가지 접근 방식이다.

4.1 반복 구조의 팩토리얼

def factorial_iter(n):
    result = 1
    for k in range(1, n+1):
        result *= k
    return result

• O(N)의 시간 복잡도를 가짐.
• 반복문을 통해 n! 값을 계산.

4.2 순환(재귀) 구조의 팩토리얼

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

• O(N)의 시간 복잡도를 가짐.
• 함수가 자기 자신을 호출하여 n! 값을 계산.

재귀 함수 호출 시 스택 오버헤드가 발생할 수 있음.

• 재귀 깊이가 깊어질 경우 스택 메모리 초과 가능.
• 반복문으로 변환하여 해결할 수도 있음.

---

5. 하노이 탑 문제

• 하노이 탑 문제는 재귀적으로 해결할 수 있으며, T(n)을 구하는 식이 순환적인 형태를 띈다.
• 시간 복잡도: O(2ⁿ)

재귀 구현

def hanoi_tower(n, source, auxiliary, target):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi_tower(n-1, source, target, auxiliary)  # n-1개를 보조 기둥으로 이동
    print(f"Move disk {n} from {source} to {target}")  # 가장 큰 원판 이동
    hanoi_tower(n-1, auxiliary, source, target)  # n-1개를 목표 기둥으로 이동

• T(n) = 2T(n-1) + 1 로 표현됨.
• T(1) = 1 을 적용하면 O(2ⁿ)의 시간 복잡도를 가짐.

---

6. 시간 복잡도 비교

시간 복잡도 알고리즘 예시

O(1)	해시 테이블 조회
O(log N)	이진 탐색
O(N)	순차 탐색, 단일 반복문
O(N log N)	퀵 정렬(평균), 병합 정렬
O(N²)	선택 정렬, 삽입 정렬
O(2ⁿ)	하노이 탑 문제, 피보나치 수열(재귀)
O(N!)	순열 생성

---

7. 빅오 표기법을 활용한 분석

1. 버스 도착 시간 예시
   • 버스가 정류장에 도착하는 시간을 분석하면:
     • 최선의 경우(Ω) → 정류장 도착과 동시에 버스 도착
     • 평균적인 경우(Θ) → 일반적인 평균 대기 시간
     • 최악의 경우(O) → 버스가 가장 늦게 도착할 경우
2. 정렬되지 않은 배열에서 특정 값을 찾는 경우
   • 최선의 경우(Ω) → 첫 번째 요소에서 찾을 경우 O(1)
   • 평균적인 경우(Θ) → 중간 위치에서 찾을 경우 O(N/2)
   • 최악의 경우(O) → 마지막 요소 또는 없는 경우 O(N)

---

8. 순환 알고리즘의 시간 복잡도

• 순환적 문제(재귀 문제)는 보통 **재귀 관계식(Recurrence Relation)**을 이용해 복잡도를 분석할 수 있다.
• 이진 탐색: T(n) = T(n/2) + O(1) → O(log N)
• 하노이 탑: T(n) = 2T(n-1) + 1 → O(2ⁿ)

순환적 알고리즘의 복잡도를 분석하는 방법:

1. 재귀 관계식을 세운다.
2. 연속 대입법(Substitution Method)으로 일반식을 유도.
3. 시간 복잡도를 결정.

예를 들어, 하노이 탑 문제에서:

• T(n) = 2T(n-1) + 1
• T(n-1) = 2T(n-2) + 1
• 이를 계속 대입하면 T(n) = 2ⁿ - 1이 되어 O(2ⁿ) 이 된다.

---

9. 정리

1. 빅오(O), 빅세타(Θ), 빅오메가(Ω) 표기법을 사용하여 알고리즘의 최악, 평균, 최선의 경우 성능을 분석한다.
2. 반복과 재귀를 비교하여 최적의 알고리즘을 선택해야 한다.
3. **순환(재귀)과 반복(Iteration)**은 서로 변환 가능하며, 최적의 방법을 선택하는 것이 중요하다.
4. 시간 복잡도 분석을 통해 알고리즘의 실행 시간을 예측하고 최적화할 수 있다.

[하노이탑 풀이]

 

출력된 결과를 기반으로 하노이 탑 알고리즘의 실행 과정을 분석해보겠다.

---

1. 코드 분석

입력값 hanoi_tower(4, 'A', 'B', 'C')의 의미:

• n=4: 총 4개의 원판을 이동해야 함.
• 'A': 출발 기둥(Source)
• 'B': 보조 기둥(Auxiliary)
• 'C': 목적 기둥(Destination)

---

2. 코드 오류 분석

출력에서 "Move disk {n} from source to {to}" 가 그대로 출력되고 있다.
이는 source라는 문자열이 그대로 들어갔기 때문이며, {fr}로 변경해야 올바른 출력이 된다.

수정된 코드

def hanoi_tower(n, fr, tmp, to):
    if n == 1:
        print(f"Move disk 1 from {fr} to {to}")
    else:
        hanoi_tower(n-1, fr, to, tmp)  # n-1개의 원판을 보조 기둥으로 이동
        print(f"Move disk {n} from {fr} to {to}")  # 원래 출발 기둥에서 목적 기둥으로 이동
        hanoi_tower(n-1, tmp, fr, to)  # 보조 기둥의 n-1개 원판을 목적 기둥으로 이동

hanoi_tower(4, 'A', 'B', 'C')

이제 Move disk {n} from source to {to}가 아니라, 올바른 기둥 이름을 출력할 것이다.

---

3. 출력 분석

입력값 hanoi_tower(4, 'A', 'B', 'C')을 실행하면,
하노이 탑의 원리에 따라 4개의 원판을 A에서 C로 옮기는 과정이 순서대로 출력된다.

단계별 분석

(1) n=4일 때

• n-1=3개의 원판을 A → B로 이동 (보조 기둥으로 임시 이동)
• A → C로 가장 큰 원판(4번 원판) 이동 (목표 기둥으로 직접 이동)
• n-1=3개의 원판을 B → C로 이동 (최종 목적지로 이동)

---

(2) 세부 실행 과정

첫 번째 단계 (A → B로 3개 이동)

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B

✔ A에서 B로 원판 3개 이동 완료

---

두 번째 단계 (A → C로 4번 원판 이동)

Move disk 4 from A to C

✔ 가장 큰 원판을 목적지 C로 이동 완료

---

세 번째 단계 (B → C로 3개 이동)

Move disk 1 from B to C
Move disk 2 from B to A
Move disk 1 from C to A
Move disk 3 from B to C
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

✔ 보조 기둥 B에 있던 원판 3개를 최종 목적지 C로 이동 완료

---

4. 최종 정리

✔ 하노이 탑의 핵심 로직

1. n-1개의 원판을 보조 기둥으로 이동
2. 가장 큰 원판을 목표 기둥으로 이동
3. n-1개의 원판을 목표 기둥으로 이동

출력된 순서는 하노이 탑 알고리즘이 올바르게 실행되었음을 의미한다.
올바른 출력이 되도록 source를 {fr}로 변경하면 코드가 정상적으로 작동할 것이다.

 

 

참고자료

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

'하노이의 탑' 이해하기