0%
프로그래밍 · 기말 · 실전 모의고사

프로그래밍 기말 — 실전 모의고사 2회분

실제 구성 그대로 — T/F 40 · 객관식 40 · 손코딩 — 정답·해설은 접이식 토글

Table of Contents · 차례

  1. §1 · 시험 안내 & 푸는 전략
  2. §2 · 모의고사 1회 (T/F 20 · 객관식 20 · 코딩 5)
  3. §3 · 모의고사 2회 (T/F 20 · 객관식 20 · 코딩 5)
  4. §4 · 마무리 — 오답 시 돌아갈 곳

§1 How to Use & Strategy — 시험 안내 & 전략

실제 기말과 동일한 구성(T/F 20 · 객관식 20 · 코딩 10/세트)을 2회분 담았습니다. 개념이 흔들리면 짝 노트 교과서형 정리 + 손코딩으로 돌아가세요. 각 문제의 "▸ 정답"을 펼치기 전에 먼저 스스로 답하는 게 핵심입니다.

⚠️ T/F 감점 전략

틀리면 −1점. "always / never / every / cannot / 항상 / 절대" 같은 극단 단어가 든 진술은 대개 거짓(반례 하나면 무너짐). 확신 없으면 비우는 것도 전략. 객관식은 감점 없으니 반드시 표기.

§2 Mock Exam 1 — 모의고사 1회

Part A · True / False (20문항, 오답 −1)
T1. O(2ⁿ)은 O(n²)보다 빠르게 증가한다.
정답
T. 지수 > 다항. 위계상 가장 나쁨.
T2. Binary search는 정렬 안 된 리스트에도 쓸 수 있다.
정답
F. 정렬된 리스트가 전제. 안 되면 결과 보장 X.
T3. Quick Sort는 항상 O(n log n)이다.
정답
F. "항상"이 함정. worst O(n²)(나쁜 pivot).
T4. 파이썬 리스트 끝에 append하는 것은 O(1)이다.
정답
T. 뒤 추가는 shift 없음.
T5. list.pop(0)과 deque.popleft()의 시간복잡도는 같다.
정답
F. list O(n)(전부 shift) vs deque O(1).
T6. naive 재귀 Fibonacci의 공간복잡도는 O(2ⁿ)이다.
정답
F. Time이 O(2ⁿ), Space는 O(n)(stack은 한 경로만).
T7. Selection Sort는 이미 정렬된 입력에도 O(n²)이다.
정답
T. 입력 상태와 무관(최솟값 탐색 항상 수행).
T8. Big-O에서는 가장 큰 항만 남기고 상수는 버린다.
정답
T. 단순화 규칙.
T9. Dictionary의 key 조회는 평균 O(n)이다.
정답
F. 해싱으로 평균 O(1).
T10. Stack은 FIFO 구조다.
정답
F. Stack은 LIFO. FIFO는 Queue.
T11. 모든 재귀 함수는 종료하려면 base case가 필요하다.
정답
T. 없으면 무한 재귀→RecursionError.
T12. Merge Sort는 O(1) 추가 공간만 쓴다.
정답
F. 병합 버퍼로 O(n) 공간.
T13. x in some_set은 평균 O(1)이다.
정답
T. 해싱.
T14. stack에 저장된 지역변수는 함수가 return해도 남아있다.
정답
F. frame이 pop되며 즉시 사라짐.
T15. log₂(1,000,000)은 약 20이다.
정답
T. 2²⁰≈10⁶.
T16. Memoization은 메모리를 써서 시간을 버는 기법이다.
정답
T. space-for-time.
T17. 파이썬에서 int 객체는 stack에 저장된다.
정답
F. 객체는 heap, stack엔 참조(슬롯).
T18. Bubble Sort의 best case는 O(n)이다.
정답
T. 이미 정렬 시 한 번 훑고 종료.
T19. 빈 stack에서 pop하면 IndexError가 난다.
정답
T. if stack:로 방지.
T20. 시간복잡도와 공간복잡도는 항상 같은 Big-O를 갖는다.
정답
F. 독립적(예: rev1은 시간 O(n)·공간 O(n), rev2는 시간 O(n)·공간 O(1); fib는 시간 O(2ⁿ)·공간 O(n)).
Part B · Multiple Choice (20문항)
M1. 2n³ + 100n² + 5n의 Big-O는?
  1. O(n²)
  2. O(n³)
  3. O(n log n)
  4. O(n!)
정답
b) O(n³) — 최고차항.
M2. 큰 n에서 가장 느린(나쁜) 복잡도는?
  1. O(log n)
  2. O(n²)
  3. O(2ⁿ)
  4. O(n log n)
정답
c) O(2ⁿ).
M3. Quick Sort의 worst-case 시간은?
  1. O(n)
  2. O(n log n)
  3. O(n²)
  4. O(log n)
정답
c) O(n²).
M4. 중첩 for loop(각 n번)의 복잡도는?
  1. O(n)
  2. O(n²)
  3. O(log n)
  4. O(n log n)
정답
b) O(n²).
M5. Undo(LIFO)에 가장 알맞은 자료구조는?
  1. Queue
  2. Stack
  3. Dict
  4. Set
정답
b) Stack.
M6. list.insert(0, x)의 복잡도는?
  1. O(1)
  2. O(log n)
  3. O(n)
  4. O(n²)
정답
c) O(n) — 전부 shift.
M7. 정렬된 데이터가 반드시 필요한 것은?
  1. Linear search
  2. Binary search
  3. Hashing
  4. Stack push
정답
b) Binary search.
M8. naive 재귀 Fibonacci의 공간복잡도는?
  1. O(1)
  2. O(n)
  3. O(2ⁿ)
  4. O(log n)
정답
b) O(n) — 재귀 깊이.
M9. key로 빠른 조회에 가장 좋은 구조는?
  1. List
  2. Stack
  3. Dictionary
  4. Queue
정답
c) Dictionary.
M10. O(n) 추가 공간을 쓰는 정렬은?
  1. Bubble
  2. Selection
  3. Merge
  4. Quick
정답
c) Merge Sort.
M11. deque.popleft()의 복잡도는?
  1. O(1)
  2. O(n)
  3. O(log n)
  4. O(n²)
정답
a) O(1).
M12. Memoization 적용 Fibonacci의 시간은?
  1. O(2ⁿ)
  2. O(n)
  3. O(n²)
  4. O(log n)
정답
b) O(n).
M13. Big-O의 "O"가 뜻하는 것은?
  1. Operation
  2. Order of
  3. Output
  4. Optimal
정답
b) Order of.
M14. n=1,000,000에서 binary search 최악 비교 횟수 ≈?
  1. 20
  2. 1,000
  3. 1,000,000
  4. 100
정답
a) 약 20.
M15. RecursionError를 일으키는 것은?
  1. 빈 리스트
  2. base case 누락
  3. 큰 dict
  4. O(n²) loop
정답
b) base case 누락(또는 도달 불가).
M16. 중복 제거를 가장 빠르게?
  1. 중첩 loop
  2. set
  3. bubble sort
  4. stack
정답
b) set — O(n).
M17. "접시 더미" 비유에 해당하는 것은?
  1. FIFO
  2. LIFO
  3. 무작위
  4. 정렬
정답
b) LIFO(Stack).
M18. O(1) 공간으로 리스트 뒤집기에 쓰는 방법은?
  1. 새 list 생성
  2. 슬라이싱
  3. in-place swap
  4. 재귀
정답
c) in-place swap(two-pointer).
M19. fib(5)의 call tree 노드 수는 약?
  1. 5
  2. 15
  3. 32
  4. 2
정답
b) 약 15.
M20. 다음 중 O(1)인 것은?
  1. x in list
  2. len(my_list)
  3. bubble sort
  4. linear search
정답
b) len(my_list).
Part C · Coding (5문항)
C1. Factorial (recursive)★☆☆

factorial(n)을 재귀로 구현(n≥0).

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

Time O(n), Space O(n)(재귀 깊이).

C2. Reverse a string with a stack★☆☆

스택을 이용해 문자열을 뒤집어 반환.

def reverse(s):
    stack = list(s)
    out = ""
    while stack:
        out += stack.pop()
    return out

Time O(n), Space O(n). LIFO가 순서를 뒤집는다.

C3. Count occurrences (dict)★★☆

리스트에서 각 원소의 등장 횟수를 dict로 반환.

def count(items):
    freq = {}
    for x in items:
        freq[x] = freq.get(x, 0) + 1   # O(1) per item
    return freq

Time O(n), Space O(k). dict의 O(1) 갱신 활용.

C4. Linear search (return index)★☆☆

arr에서 target의 첫 index 반환(없으면 −1).

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Time O(n), Space O(1). 정렬 불필요(binary와 대비).

C5. Sum a nested list (recursion)★★☆

[1,[2,[3,4]],5]처럼 중첩된 숫자 리스트의 총합을 재귀로.

def deep_sum(lst):
    total = 0
    for x in lst:
        if isinstance(x, list):
            total += deep_sum(x)       # 가지 → 재귀
        else:
            total += x                  # 잎
    return total

tree 구조의 재귀. base는 "리스트가 아닌 원소".

✦ ✦ ✦

§3 Mock Exam 2 — 모의고사 2회

Part A · True / False (20문항, 오답 −1)
T1. 큰 n에서 O(n log n)은 O(n²)보다 빠르다.
정답
T.
T2. Queue는 First In First Out을 따른다.
정답
T.
T3. 해싱은 dict와 set에 평균 O(1) 조회를 준다.
정답
T.
T4. Merge Sort의 worst case는 O(n²)이다.
정답
F. 항상 O(n log n).
T5. 재귀의 call stack은 call tree 전체를 동시에 담는다.
정답
F. root→leaf 한 경로만(그래서 space O(n)).
T6. 파이썬에서 heap은 GC가 자동 관리한다.
정답
T.
T7. 리스트를 index로 접근하는 것은 O(n)이다.
정답
F. O(1).
T8. 재귀에서는 base case를 먼저 쓰는 것이 권장된다.
정답
T. 버그 대부분이 base-case 버그.
T9. Stack 할당은 heap 할당보다 빠르다.
정답
T. 포인터 이동(1명령).
T10. x in my_list은 O(1)이다.
정답
F. O(n)(set이면 O(1)).
T11. Selection Sort는 정렬된 배열에서는 O(n)이 될 수 있다.
정답
F. 항상 O(n²).
T12. 모든 재귀 함수는 loop로 다시 쓸 수 있다.
정답
T. 표현력 동등.
T13. bool은 보통 1바이트를 차지한다.
정답
T.
T14. Memoization은 함수가 순수(pure)하고 입력이 hashable일 때 안전하다.
정답
T.
T15. 파이썬 기본 재귀 한도는 약 1,000이다.
정답
T. sys.getrecursionlimit().
T16. Quick Sort는 in-place이며 평균 O(log n) 공간을 쓴다.
정답
T.
T17. RecursionError의 traceback은 call stack과 무관하다.
정답
F. traceback이 곧 stack이다.
T18. set으로 중복 탐지는 Time O(n), Space O(n)이다.
정답
T.
T19. Time-space tradeoff란 둘을 동시에 개선하는 것은 절대 불가능하다는 뜻이다.
정답
F. "절대"가 함정 — 더 나은 알고리즘은 둘 다 줄이기도 한다. tradeoff는 흔히 맞바꾼다는 의미.
T20. Binary search는 매 단계 탐색 범위를 절반으로 줄인다.
정답
T. 그래서 O(log n).
Part B · Multiple Choice (20문항)
M1. n²/2 + 100n의 단순화는?
  1. O(n)
  2. O(n²)
  3. O(n²/2)
  4. O(100n)
정답
b) O(n²).
M2. O(log n)을 만드는 패턴은?
  1. 단일 loop
  2. 중첩 loop
  3. 매번 절반씩 줄임
  4. 2갈래 재귀
정답
c) 절반씩 줄임.
M3. enqueue/dequeue에 가장 좋은 것은?
  1. list
  2. deque
  3. dict
  4. set
정답
b) deque — popleft O(1).
M4. dict insert의 평균 시간은?
  1. O(1)
  2. O(n)
  3. O(log n)
  4. O(n²)
정답
a) O(1).
M5. 시간이 항상 O(n log n)인 정렬은?
  1. Bubble
  2. Selection
  3. Merge
  4. Quick
정답
c) Merge Sort.
M6. call frame에 들어있는 것은?
  1. 객체들
  2. return 주소+지역변수+매개변수
  3. heap
  4. 전역변수만
정답
b).
M7. 제곱을 이용한 power(x,n)의 복잡도는?
  1. O(n)
  2. O(log n)
  3. O(n²)
  4. O(1)
정답
b) O(log n) — 매번 절반.
M8. fib(30) naive 호출 수 ≈?
  1. 30
  2. 900
  3. 약 260만
  4. 60
정답
c) 약 260만.
M9. 평균 O(1)이 아닌 것은?
  1. dict[k]
  2. set add
  3. list 검색
  4. stack push
정답
c) list 검색 — O(n).
M10. 괄호 짝 검사기에 쓰는 구조는?
  1. queue
  2. stack
  3. dict
  4. 재귀만
정답
b) stack.
M11. 행렬식의 여인수 전개는 본질적으로?
  1. 반복적
  2. 재귀적
  3. O(1)
  4. 해싱
정답
b) 재귀적(부분행렬로 축소).
M12. index 접근이 없는 구조는?
  1. list
  2. set
  3. array
  4. string
정답
b) set — 무순서.
M13. in-place reverse의 공간은?
  1. O(n)
  2. O(1)
  3. O(log n)
  4. O(n²)
정답
b) O(1).
M14. 정렬된 두 리스트(len n,m) 병합의 시간은?
  1. O(nm)
  2. O(n+m)
  3. O(log n)
  4. O(1)
정답
b) O(n+m).
M15. 잘못된 자료구조 선택은 O(n)을 무엇으로 바꿀 수 있나?
  1. O(1)
  2. O(log n)
  3. O(n²)
  4. O(n)
정답
c) O(n²).
M16. Euclid GCD에서 gcd(48,18) 첫 단계는 gcd(18, ?)?
  1. gcd(18,12)
  2. gcd(18,0)
  3. gcd(48,18)
  4. gcd(12,6)
정답
a) gcd(18,12) — 48 mod 18 = 12.
M17. 가장 느리게 증가하는 것은?
  1. O(n)
  2. O(log n)
  3. O(n log n)
  4. O(n²)
정답
b) O(log n).
M18. 원반 n개 하노이탑에 필요한 이동 횟수는?
  1. n
  2. n²
  3. 2ⁿ−1
  4. log n
정답
c) 2ⁿ−1.
M19. 파이썬에서 객체 참조는 보통 몇 바이트?
  1. 1
  2. 4
  3. 8
  4. 0
정답
c) 8바이트(주소를 담음).
M20. 중복 제거 + O(1) 멤버십을 동시에 원하면?
  1. list
  2. set
  3. stack
  4. queue
정답
b) set.
Part C · Coding (5문항)
C1. Fibonacci with memoization★★☆

memoization으로 fib(n)을 O(n)에 구현.

memo = {}
def fib(n):
    if n in memo: return memo[n]
    if n < 2: return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

Time O(n)(각 fib(k) 1회), Space O(n).

C2. Balanced parentheses (stack)★★★

"({[]})" 같은 문자열이 올바른 괄호 짝인지 True/False.

def is_balanced(s):
    pairs = {')':'(', ']':'[', '}':'{'}
    stack = []
    for ch in s:
        if ch in '([{': stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

Time O(n), Space O(n).

C3. Binary search★★☆

정렬된 arr에서 target index 반환(없으면 −1), O(log n).

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

Time O(log n). 전제: 정렬.

C4. Count files recursively (tree)★★★

폴더를 {"files": int, "subfolders": [folder, ...]}로 표현할 때, 하위 폴더까지 포함한 총 파일 수를 재귀로.

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

tree 구조 → 재귀가 두 줄. 반복문이면 explicit stack을 손수 만들어야.

C5. Merge two sorted lists★★☆

정렬된 a, b를 정렬 유지하며 병합.

def merge(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

Time O(n+m). merge sort의 핵심 단계.

§4 Wrap-up — 마무리 · 오답 시 돌아갈 곳

틀린 문제 유형별로 교과서형 정리 노트의 해당 섹션으로 복귀하세요 — 복잡도 §2–4, 자료구조 §5, 메모리·재귀 §6–8, 손코딩 §9. 그리고 시험장 반입 치트시트는 정리 노트 §10을 손글씨(영어)로 옮기면 됩니다. T/F는 −1 감점이니 확실한 것만, 객관식은 빠짐없이.