[알고리즘] Week 6: 재귀 알고리즘 - 개념과 예제

Day 1: 재귀의 개념

• 강의 내용:
  • 재귀의 정의와 중요성
    • 재귀란 무엇인가?
    • 재귀 함수의 기본 구조 (기저 조건과 재귀 호출)
    • 재귀 알고리즘의 중요성 및 활용 사례
  • 재귀의 장단점
    • 재귀의 장점 (간결함, 특정 문제에 대한 자연스러운 표현)
    • 재귀의 단점 (성능 문제, 스택 오버플로우 위험)
• 실습:
  • 간단한 재귀 함수 작성 및 실행

# 재귀 함수의 기본 예제: 1부터 n까지의 합 계산
def recursive_sum(n):
    if n == 1:
        return 1
    else:
        return n + recursive_sum(n - 1)

# 예제 실행
print("1부터 5까지의 합:", recursive_sum(5))  # 15

 

Day 2: 팩토리얼 계산

• 강의 내용:
  • 팩토리얼의 개념
    • 팩토리얼의 정의 (n! = n * (n-1)!)
    • 팩토리얼의 수학적 표현 및 활용
  • 팩토리얼의 재귀적 구현
    • 기저 조건 및 재귀 호출
• 실습:
  • 팩토리얼 계산 함수 구현 및 예제

# 팩토리얼 계산 함수 구현
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

# 팩토리얼 계산 예제
print("5! =", factorial(5))  # 120

 

Day 3: 피보나치 수열

• 강의 내용:
  • 피보나치 수열의 개념
    • 피보나치 수열의 정의 (F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1)
    • 피보나치 수열의 수학적 표현 및 활용
  • 피보나치 수열의 재귀적 구현
    • 기저 조건 및 재귀 호출
• 실습:
  • 피보나치 수열 계산 함수 구현 및 예제

# 피보나치 수열 계산 함수 구현
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# 피보나치 수열 계산 예제
print("피보나치 수열의 10번째 항:", fibonacci(10))  # 55

 

Day 4: 피보나치 수열의 최적화

• 강의 내용:
  • 피보나치 수열의 비효율성
    • 중복 계산 문제
    • 시간 복잡도 분석 (O(2^n))
  • 메모이제이션을 통한 최적화
    • 메모이제이션의 개념 및 적용 방법
• 실습:
  • 메모이제이션을 적용한 피보나치 수열 계산 함수 구현

# 메모이제이션을 적용한 피보나치 수열 계산 함수 구현
def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

# 피보나치 수열 계산 예제
print("최적화된 피보나치 수열의 50번째 항:", fibonacci_memo(50))  # 12586269025

 

Day 5: 하노이의 탑

• 강의 내용:
  • 하노이의 탑의 개념
    • 하노이의 탑 문제 설명
    • 하노이의 탑의 수학적 표현 및 원리
  • 하노이의 탑의 재귀적 구현
    • 기저 조건 및 재귀 호출
• 실습:
  • 하노이의 탑 해결 알고리즘 구현 및 예제

# 하노이의 탑 해결 함수 구현
def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)

# 하노이의 탑 예제 실행
n = 3
hanoi(n, 'A', 'C', 'B')
# 예상 출력:
# Move disk 1 from A to C
# Move disk 2 from A to B
# Move disk 1 from C to B
# Move disk 3 from A to C
# Move disk 1 from B to A
# Move disk 2 from B to C
# Move disk 1 from A to C

 

Day 6: 재귀 알고리즘의 성능 분석

• 강의 내용:
  • 재귀 알고리즘의 성능 분석
    • 재귀 호출의 시간 복잡도 분석 방법
    • 재귀 알고리즘의 공간 복잡도 분석
  • 재귀와 반복의 비교
    • 재귀 알고리즘과 반복 알고리즘의 비교
    • 각각의 장단점
• 실습:
  • 재귀 알고리즘과 반복 알고리즘의 성능 비교 예제

# 반복적 팩토리얼 계산 함수 구현
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

# 성능 비교 예제
import time

n = 500

# 재귀적 팩토리얼 계산 시간 측정
start_time = time.time()
factorial(n)
end_time = time.time()
print("재귀적 팩토리얼 계산 시간:", end_time - start_time)

# 반복적 팩토리얼 계산 시간 측정
start_time = time.time()
factorial_iterative(n)
end_time = time.time()
print("반복적 팩토리얼 계산 시간:", end_time - start_time)

 

Day 7: 종합 연습 및 프로젝트 준비

• 강의 내용:
  • 재귀 알고리즘 종합 연습
    • 다양한 재귀 알고리즘 문제 풀이
    • 알고리즘 성능 분석 및 최적화
  • 프로젝트 준비
    • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 구현 계획 수립
• 실습:
  • 재귀 알고리즘 종합 연습 문제 풀기
  • 프로젝트 주제 및 계획 수립

### 종합 연습 문제 예시
1. 주어진 정수 배열에서 모든 부분집합을 찾는 재귀 함수 구현
2. 미로 찾기 문제를 재귀적으로 해결
3. 문자열의 모든 순열을 생성하는 재귀 함수 구현

### 프로젝트 주제 예시
1. 재귀적 데이터 구조 처리 시스템
2. 재귀적 그래프 탐색 도구
3. 재귀적 패턴 생성기

### 프로젝트 요구사항 예시
1. 재귀적 데이터 구조 처리 시스템:
   - 다양한 데이터 구조 입력 및 저장
   - 재귀 알고리즘을 통한 데이터 처리
   - 처리된 데이터 출력 및 분석

### 프로젝트 계획 예시
1. 데이터 입력 모듈 구현
2. 재귀 알고리즘 구현 (예: 트리 탐색, 그래프 탐색 등)
3. 데이터 출력 및 분석 모듈 구현

 

이 강의는 파이썬의 재귀 알고리즘, 특히 팩토리얼 계산, 피보나치 수열, 하노이의 탑의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!