C/C++ 알고리즘

재귀와 call stack

모든 재귀 함수에는 base case와 그쪽으로의 진행이 필요합니다.

재귀와 call stack이란?

모든 재귀 함수에는 base case와 그쪽으로의 진행이 필요합니다.

더 작은 instance로 문제를 풉니다.

중요한 점

빈 입력, 한 요소, 중복, 정렬된 입력을 테스트하세요.
정확성과 최적화를 분리하세요.
프로덕션에서는 standard library를 우선하세요.

C와 C++ 코드 예제

실행 →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

예상 출력

C++

실행 →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

예상 출력

C와 C++ 비교

Factorial은 시간 O(n), stack O(n)입니다. 큰 입력은 검증하고 반복문 풀이도 고려하세요.

Loop, pointer, length와 buffer가 명시적입니다.

C++

Iterator와 algorithm이 연산과 저장 방식을 분리합니다.

연습 문제

두 버전을 실행하고 수정하여 각 언어의 보장을 관찰하세요.

각 비교를 직접 추적하세요.
중복과 극값을 테스트하세요.
Standard library와 benchmark하세요.