성능 & 재귀

Source: Dev.to

센서 없이 참가자 수 세기

옵션 1: 사람을 하나씩 세기 – 1, 2, 3, 4…

옵션 2: 두 개씩 세기 – 2, 4, 6, 8…

옵션 3: 짝짓기 전략 사용

1. 모두 일어서서 숫자 1을 생각한다.
2. 다른 사람과 짝을 지어 두 숫자를 더하고 그 합을 기억한다.
3. 각 짝에서 한 사람은 앉는다.
4. 아직도 서 있는 사람이 있으면 2단계부터 다시 반복한다.

마지막으로 남은 사람은 정확한 참가자 수를 알게 된다. 이 방법은 다른 방법들보다 훨씬 효율적이며, 알고리즘적 사고가 왜 중요한지를 보여준다.

성능과 빅 O 표기법

성능은 입력 크기가 증가함에 따라 프로그램 실행 시간이 어떻게 증가하는지를 설명한다.

• 옵션 1은 O(n) (선형 시간)으로 실행된다: 참가자당 한 단계씩.
• 옵션 2는 O(n / 2) 로 실행되며, 여전히 선형이지만 상수 계수만큼 빠르다.
• 옵션 3은 O(log n) (로그arithmic 시간)으로 실행된다: 각 라운드마다 서 있는 참가자 수가 절반으로 줄어들어, 100명일 경우 약 7단계만 필요하다.

재귀

재귀 함수는 **기저 사례(base case)**에 도달할 때까지 문제를 점점 작은 하위 문제로 나누어 해결한다.

마트료시카 인형 비유

• 재귀 단계: 현재 인형을 연다. 안에 또 다른 인형이 있으면 반복한다.
• 기저 사례: 열 수 없는 가장 작은 인형; 여기서 멈추고 이전 단계들을 “거꾸로 세어” 나간다.

예시: 팩토리얼 함수

def factorial(n):
    if n == 0:
        return 1  # base case
    return n * factorial(n - 1)  # recursive case

# Evaluation trace
factorial(4)
# → 4 * factorial(3)
# → 4 * 3 * factorial(2)
# → 4 * 3 * 2 * factorial(1)
# → 4 * 3 * 2 * 1 * factorial(0)
# → 4 * 3 * 2 * 1 * 1
# → 24

David Malan의 로그arithmic 카운팅 데모

CS50 강의에서 David Malan 교수는 O(log n) 전략을 시연한다:

1. 모두 일어서서 숫자 1을 가정한다.
2. 짝을 지어 두 숫자를 더하고 한 사람은 앉힌다.
3. 한 사람이 남을 때까지 반복한다.

문제 크기가 매 라운드마다 절반으로 줄어들기 때문에, 1,000명의 방에서는 전체 인원을 파악하는 데 약 10라운드만 필요하다— 로그arithmic 시간 복잡성을 명확히 보여주는 예시다.

참고 문헌

• CS50x 2026 – Lecture 3 – Algorithms (PDF: Recursion_Blueprint.pdf)
• 알고리즘 분석에 대한 추가 자료: Big O notation