프로그래밍 기말 — 교과서형 정리 + 손코딩

§1 Exam Structure & How to Read — 시험 구조와 읽는 법

이 노트는 프로그래밍 기말 시험범위(4개 강의 — 복잡도 ①②, 자료구조, 메모리·재귀·메모이제이션)를 처음부터 끝까지 교과서처럼 읽도록 구성했습니다. 큰 흐름은 셋입니다 — 복잡도(코드가 얼마나 잘 확장되는가), 자료구조(데이터를 어떻게 담아야 빠른가), 메모리·재귀(함수 호출이 실제로 어떻게 동작하는가). 마지막 §9는 사용자가 가장 중요하다고 한 손코딩입니다.

1.1 한눈에 보는 복잡도 위계 — 이것만은 반사적으로

§2 Time Complexity & Big-O — 시간 복잡도

The Key Idea — 왜 필요한가

코드가 빠른지 느린지 재는 방법은 둘이다. ① wall-clock time(스톱워치로 실제 시간 측정) — 컴퓨터·다른 프로그램·입력에 따라 들쭉날쭉. ② counting operations(입력이 커질 때 연산 수가 어떻게 느는지 셈) — 기계 독립적이고 수학적. 우리는 ②를 쓰고, 그 추세를 Big-O로 표기한다. 핵심은 정확한 횟수가 아니라 추세(trend), 즉 입력 n이 커질 때의 상한(upper bound)이다.

# 연산 수는?
def sum_list(numbers):
    total = 0            # 1 operation
    for num in numbers:  # n operations
        total += num     # n operations
    return total         # 1 operation
# 합 = 2n + 2 → 추세는 n에 비례 → O(n)

2.1 Big-O 단순화 3규칙 — simplification

2.2 복잡도별 대표 코드 패턴 — 코드만 보고 즉답

def has_duplicate(lst):          # O(n²)
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            if lst[i] == lst[j]:
                return True
    return False
# set을 쓰면 O(n)으로 개선 가능 → §3, §5에서 다시

§3 Space Complexity & Time-Space Tradeoff — 공간 복잡도

The Key Idea

시간이 "얼마나 오래?"라면 공간은 "메모리를 얼마나 쓰나?"이다. 비유: 요리에서 시간=조리 시간, 공간=필요한 냄비·팬 수. 핵심 규칙: 입력 자체는 세지 않는다 — 알고리즘이 추가로 할당하는(extra) 메모리만 센다.

3.1 O(1) vs O(n) 공간 — 같은 시간, 다른 공간 — in-place의 힘

리스트 뒤집기를 두 가지로. 둘 다 시간은 O(n)이지만 공간이 다르다.

# O(n) space — 새 list 생성          # O(1) space — 제자리 교환(in-place)
def rev1(nums):                       def rev2(nums):
    result = []                            l, r = 0, len(nums)-1
    for i in range(len(nums)-1,-1,-1):       while l < r:
        result.append(nums[i])                 nums[l], nums[r] = nums[r], nums[l]
    return result                            l += 1; r -= 1

3.2 Time-Space Tradeoff — 메모리를 써서 시간을 산다

§4 Searching & Sorting — 탐색과 정렬

4.1 Linear vs Binary Search — 선형 vs 이진 탐색

4.2 정렬 4종 비교 — 반드시 외울 표

# Merge Sort: [5,3,8,1]          # Selection Sort: [5,3,8,1]
[5,3,8,1] → [5,3] [8,1]              min=1 → [1,3,8,5]
[5][3] [8][1]   (base)               min=3 → [1,3,8,5]
[3,5] [1,8]     (merge)              min=5 → [1,3,5,8] ✓
[1,3,5,8]       (merge) ✓

§5 Data Structures — List · Stack · Queue · Dict · Set

The Key Idea

자료구조는 데이터를 조직·저장하는 방식이다. 구조마다 잘하는 연산과 못하는 연산이 다르다. 옷장 비유: 바닥에 쌓기(추가 쉽지만 찾기 어려움) vs 색깔별 정렬(찾기 빠름) vs 라벨 서랍(즉시 접근). 가장 자주 하는 연산을 가장 빠르게 만드는 구조를 고르는 것이 핵심 — 잘못 고르면 O(n) 해법이 O(n²)가 된다.

5.1 List (Array) — 순서·위치 접근

index 0부터 시작, 연속 메모리(contiguous memory)에 저장. 그래서 위치 접근이 빠르다.

5.2 Stack — LIFO — Last In, First Out

접시 더미 비유. 맨 위에서만 넣고 뺀다 — 중간 접근 불가. 세 연산 모두 O(1): push(x)=append, pop()=top 제거+반환, peek()=stack[-1](제거 없이 확인).

# 문자열 뒤집기 — stack의 대표 용도
stack = []
for ch in "HELLO":
    stack.append(ch)
result = ""
while stack:
    result += stack.pop()
# "OLLEH"

5.3 Queue — FIFO — First In, First Out

카페 줄 비유. 뒤로 들어와 앞으로 나간다. enqueue=append, dequeue=popleft, peek=q[0] — 모두 O(1).

from collections import deque
q = deque()
q.append("A"); q.append("B")   # enqueue
front = q.popleft()              # dequeue → "A", O(1)

5.4 Dictionary & Set — 해싱으로 O(1)

둘 다 hash function으로 메모리 위치를 직접 계산 → 평균 O(1). Dict는 key→value, Set은 unique values.

5.5 자료구조 선택 가이드 & Case Study — 매우 중요

# O(n²) — nested loop            # O(n) — set
for i in range(len(nums)):           seen = set()
    for j in range(i+1,len(nums)):     for x in nums:
        if nums[i]==nums[j]:                if x in seen: return True
            return True                    seen.add(x)

§6 Memory Model — Stack vs Heap — 메모리 모델

The Key Idea

"O(n) 공간"이 실제로 어디에 사는가? 메모리는 거대한 바이트 배열이다 — 각 바이트에 주소(index)와 값(0–255). 변수 x = 5는 "이름 x → 주소 0x1000 → 값 5"의 연결이다. 타입은 몇 바이트를 읽을지를 정한다(bool 1, int 보통 4, long/float/double 8, 객체 참조 보통 8 — 데이터가 아니라 주소를 담음).

6.1 Stack vs Heap — 두 영역

def f():
    n = 5                # int 객체는 HEAP, 슬롯 n(참조)은 STACK
    items = [1,2,3,4,5]   # list 객체는 HEAP, 슬롯 items(주소)는 STACK
    return items[0]

6.2 The Call Stack — 함수 호출의 동작

함수가 호출되면 frame이 stack에 push된다. frame 안에는 ① 매개변수(인자 복사본) ② 지역변수 ③ return 주소(끝나면 돌아갈 곳). 함수가 return하면 frame이 즉시 pop되고 지역변수는 사라진다.

def sum(a,b):     return a+b
def average(a,b): total = sum(a,b); return total/2
def main():      result = average(4,6)

# sum(4,6) 실행 중 stack 상태:
  sum:     a=4, b=6           ← top
  average: a=4, b=6, total=?
  main:    result=?
# sum이 10 반환 → sum frame pop → average의 total=10

§7 Recursion — 재귀

The Key Idea

"이 폴더의 모든 파일을 세라(하위·하위의 하위 폴더 포함)" — 반복문으로는 worklist+stack을 손수 흉내내야 하지만, 재귀로는 두 줄이다. 재귀 함수는 자기 자신을 호출하는 함수이고, tree·자기유사(self-similar) 구조에 자연스럽다.

7.1 Factorial — 표준 패턴 — trace까지

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

# 내려가며 쌓임:                  되돌아오며 곱함:
# factorial(4)→4*factorial(3)     factorial(0)=1
#   factorial(3)→3*factorial(2)   factorial(1)=1*1=1
#     factorial(2)→2*factorial(1) factorial(2)=2*1=2
#       factorial(1)→1*factorial(0) factorial(3)=3*2=6
#         factorial(0)→1 (base)   factorial(4)=4*6=24

가장 깊을 때 5개 frame(factorial 4,3,2,1,0)이 동시에 stack에 존재 → 하나씩 pop. 이게 §6의 call stack이 그대로 일하는 모습이다. 재귀는 마법이 아니라 함수가 함수를 부르는 것이고, bookkeeping은 stack이 한다.

7.2 Fibonacci — 가장 중요한 빈출 — Time/Space 함정

def fib(n):
    if n == 0: return 0          # base 1
    if n == 1: return 1          # base 2
    return fib(n-1) + fib(n-2)    # ← 두 번 재귀 → trace가 tree
# 0,1,1,2,3,5,8,13,21,34,55,...

7.3 재귀 vs 반복, 흔한 버그 — 동등하지만 다름

§8 Memoization & DP 입문 — O(2ⁿ) → O(n)

The Key Idea

naive fib가 느린 이유는 같은 subproblem을 반복 계산하기 때문(fib(3)을 여러 번). 고치는 법: 처음 계산한 답을 기억(cache)해 두고, 같은 입력이 또 오면 다시 계산하지 않고 꺼낸다. 이게 memoization — 전형적인 "공간을 써서 시간을 산다(space-for-time)".

memo = {}
def fib(n):
    if n in memo: return memo[n]   # cache hit → 즉시 반환
    if n < 2: return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

§9 손코딩 훈련 뱅크 — Hand-Coding Bank · 현실 사례 15제 ⭐

기말 코딩 10문항 대비. 핵심 패턴은 — 현실적인 상황(사례)이 주어지고, 거기서 수업에 배운 개념이 무엇인지 알아채 코드로 구현하는 것이다. 그래서 아래 문제는 모두 실생활 시나리오 → 떠올릴 개념 → 구현 순서다. 각 문제는 먼저 직접 손으로 짜 본 뒤 "Show Solution"을 펼쳐 모범답안·복잡도를 확인하세요.

자료구조를 알아채는 사례 — Stack · Queue · Set · Dict

def current_page(actions):
    history = []                      # stack
    for kind, page in actions:
        if kind == "visit":
            history.append(page)      # push
        elif kind == "back" and len(history) > 1:
            history.pop()             # pop
    return history[-1] if history else None

from collections import deque
def serve(orders):
    q = deque(orders)
    while q:
        drink = q.popleft()          # dequeue, O(1)
        print(f"made {drink}")

def register(emails):
    seen = set()                     # O(1) 포함검사
    accepted = []
    for e in emails:
        if e not in seen:
            seen.add(e)
            accepted.append(e)
    return accepted

def top_event(logs):
    freq = {}                        # dict: 이벤트 → 횟수
    for ev in logs:
        freq[ev] = freq.get(ev, 0) + 1   # O(1) 갱신
    return max(freq, key=freq.get)

복잡도·탐색을 알아채는 사례 — Binary Search

def find_user(names, target):
    lo, hi = 0, len(names) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if names[mid] == target: return mid
        elif names[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

재귀를 알아채는 사례 — "안에 같은 모양"이 들어있을 때

def count_files(folder):
    total = folder["files"]              # 직속 파일
    for sub in folder["subfolders"]:
        total += count_files(sub)          # 같은 문제, 더 작은 입력
    return total

def team_size(person):
    total = len(person["reports"])       # 직속 부하
    for r in person["reports"]:
        total += team_size(r)              # 그 부하의 팀까지
    return total

메모이제이션·2D 격자를 알아채는 사례

cache = {}
def get_rate(currency):
    if currency in cache:            # cache hit → 즉시
        return cache[currency]
    rate = fetch_rate(currency)        # 느린 실제 조회 (1회만)
    cache[currency] = rate
    return rate

def flip_horizontal(img):
    for row in img:
        l, r = 0, len(row) - 1
        while l < r:                    # two-pointer 제자리 교환
            row[l], row[r] = row[r], row[l]
            l += 1; r -= 1

def merge_scores(a, b):
    res, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]: res.append(a[i]); i += 1
        else:           res.append(b[j]); j += 1
    res.extend(a[i:]); res.extend(b[j:])   # 남은 꼬리
    return res

교수님 연구분야(NLP·데이터) 맛 — 현실 사례 심화

def build_vocab(words):
    vocab = {}
    for w in words:
        if w not in vocab:        # 새 단어 → 다음 ID
            vocab[w] = len(vocab)
    return vocab

from collections import deque
def moving_average(prices, k=3):
    window = deque(maxlen=k)        # 꽉 차면 가장 오래된 게 자동 pop
    out = []
    for p in prices:
        window.append(p)
        out.append(sum(window) / len(window))
    return out

def to_recommend(all_movies, watched):
    seen = set(watched)            # O(1) 포함검사
    return [m for m in all_movies if m not in seen]

입문 명강의 단골 — 한 단계 위 (MIT 6.0001 · Berkeley CS61A)

def count_change(amount, coins):
    memo = {}
    def helper(amt, i):
        if amt == 0: return 1           # 딱 맞춤 → 1가지
        if amt < 0 or i == len(coins): return 0
        if (amt, i) in memo: return memo[(amt, i)]
        memo[(amt, i)] = (helper(amt - coins[i], i)   # i동전 쓰기
                          + helper(amt, i + 1))        # i동전 그만
        return memo[(amt, i)]
    return helper(amount, 0)

def find_pair(prices, budget):
    lo, hi = 0, len(prices) - 1
    while lo < hi:
        s = prices[lo] + prices[hi]
        if s == budget: return (lo, hi)
        elif s < budget: lo += 1      # 합 부족 → 왼쪽을 키움
        else: hi -= 1                  # 합 초과 → 오른쪽을 줄임
    return None

§10 시험 직전 핵심 요약 · A4 치트시트 — 그대로 손글씨로 옮기기

아래는 A4 양면(영어 손글씨) 치트시트 압축본. 시험장 반입용으로 그대로 옮겨 적으세요.