← SO25 객관식 전체 목차

Algorithmen-Entwurfsparadigmen und Metaheuristiken

알고리즘 설계 패러다임: Divide & Conquer, Backtracking, Dynamic Programming, Greedy, Metaheuristics

중요한 독일어·영어 용어는 유지하되 설명과 학습 동선은 한국어 중심으로 제공합니다.

이 챕터의 문항별 독립 학습 페이지

단원 페이지에는 개요와 학습 순서만 둡니다. 각 문항의 용어·비유·수식·단계별 풀이·실제 채점은 아래 독립 페이지에서 이어집니다.

  1. II-15 · 2개 선택

    알고리즘 설계 패러다임에 대한 설명 중 정확히 두 개를 고르시오.

    독립 개념 강의와 실제 채점 열기 →

  2. II-16 · 2개 선택

    알고리즘 설계 방법에 대한 설명 중 정확히 두 개를 고르시오.

    독립 개념 강의와 실제 채점 열기 →

  3. II-17 · 2개 선택

    알고리즘 설계 방법에 대한 설명 중 정확히 두 개를 고르시오.

    독립 개념 강의와 실제 채점 열기 →

30초 핵심 요약

30초 핵심

D&C는 부분문제를 재귀로 풀고 결합한다. DP는 겹치는 부분문제의 답을 저장해서 반복 계산을 없앤다. Greedy는 매 단계 local best를 고르지만 별도 증명 없이는 항상 최적이 아니다. Backtracking은 해 공간을 깊이우선으로 탐색하며 막히면 되돌린다. Metaheuristic은 임의의 최적화 문제 탐색을 이끄는 일반적 방법이며, Hill Climbing은 local optimum에 갇힐 수 있다.

핵심 수식·규칙

동적 계획법(DP)의 실행시간은 상태 수 × 상태 전이 비용으로 계산한다. 탐욕법(Greedy)의 정확성은 지역 최선 선택(local choice)만으로 보장되지 않으며, 그 선택이 안전하다는 별도 증명이 필요하다.

시험에서 알아볼 신호

강한 단어를 먼저 표시하라: nur, immer, jede, gleich groß, durchschnittlich, optimal, nicht überlappend.

시험 연결

시험 영역

II

문항별 배점

2

선택 규칙

\(\text{exactly}_{\text{two}}\)exactly(two)

복기 원문 문항
  • II-15
  • II-16
  • II-17
복기 시험에서의 역할

시험 복기 자료(Gedächtnisprotokoll)는 당시 문항 표현을 추정하는 근거일 뿐 정답지는 아니다. 각 선택지의 참·거짓은 2026년 여름학기 강의와 공식 연습 자료를 기준으로 독립적으로 판정한다.

다른 문제로 옮겨 쓰는 목표

정답 라벨을 외우는 것이 아니라, 문장 안의 'nur', 'immer', 'durchschnittlich', 'gleich große', 'nicht überlappend' 같은 단어가 어떤 전제나 반례를 요구하는지 즉시 판정한다.

먼저 알아야 할 용어와 전제

개념 강의

한국어 직관 설명

이 단원의 핵심은 '문제를 어떻게 쪼개거나 탐색하거나 고를 것인가'이다. D&C는 나눠서 재귀로 풀고 합치는 구조, DP는 같은 작은 문제를 또 풀지 않도록 기억하는 구조, Greedy는 지금 좋아 보이는 선택을 확정하는 구조, Backtracking은 선택을 해 보고 막히면 되돌리는 구조, Metaheuristic은 최적화 문제의 탐색을 일반적으로 안내하는 구조다.

정의

분할 정복(Divide & Conquer)은 입력을 부분문제로 나누고 재귀적으로 푼 뒤 결과를 결합하며, 실행시간은 분할·재귀 호출·결합 전체의 점화식으로 결정된다. 백트래킹(Backtracking)은 해 공간을 깊이 우선 탐색처럼 따라가다가 현재 경로가 완전한 해가 될 수 없으면 결정을 취소한다. 동적 계획법(Dynamic Programming)은 겹치는 부분문제의 중간 결과를 저장하고 재사용하며 최적 부분 구조(optimal substructure)가 중요하다. 탐욕법(Greedy)은 현재 가장 유리해 보이는 후보를 고르지만 전역 최적성을 위해 별도의 탐욕 선택 성질이 필요하다. 메타휴리스틱(Metaheuristik)은 다양한 최적화 문제의 탐색을 이끄는 문제 독립적 상위 전략으로, 좋은 해를 찾을 수 있어도 보통 최적 보장은 없다.

선수 개념
  • 재귀 트리(recursion tree)와 점화식(recurrence)
  • 최적 부분 구조(optimal substructure)와 겹치는 부분문제(overlapping subproblems)의 구분
  • 지역 최적해(local optimum)와 전역 최적해(global optimum)의 구분
  • 결정문제(decision problem)와 최적화 문제(optimization problem)의 구분
불변식과 성질

분할 정복의 정확성은 부분문제의 해를 결합했을 때 전체 해가 되는 구조에 의존한다. 동적 계획법은 상태의 의미, 경계값, 전이, 계산 순서, 최종 답 칸, 시간·공간 복잡도를 함께 설명해야 한다. 탐욕법은 현재의 선택이 안전하다는 증명이나 강한 전제가 필요하다. 백트래킹은 visited, used, path 같은 상태를 분기 실패 뒤 정확히 되돌리는 불변식이 중요하다. 메타휴리스틱과 언덕 오르기(Hill Climbing)는 지역 최적해(local optimum)에 멈출 수 있다.

실행시간과 공간 복잡도

분할 정복은 \(T(n)=\)T(n)=부분문제 비용의 합+분할·결합 비용과 같은 점화식으로 분석한다. 백트래킹은 최악의 경우 지수 시간이 들 수 있으며 가지치기(pruning)가 실제 탐색량을 줄인다. 동적 계획법의 실행시간은 대개 상태 수와 상태당 전이 비용의 곱이다. 최소 편집 거리(Minimum Edit Distance)는 (m+1)(n+1)개 상태와 \(O(1)\)O(1) 전이를 사용해 \(\Theta(\text{mn})\)Θ(mn)이다. 탐욕법과 메타휴리스틱의 비용은 정렬, 반복 예산, 이웃 탐색 비용 같은 구현 전제에 따라 달라진다.

주요 경우와 경계 사례

분할 정복의 부분문제가 항상 같은 크기일 필요는 없으며 QuickSort는 피벗에 따라 불균형하게 나뉠 수 있다. 분수 배낭(fractional knapsack)에 맞는 밀도 기반 탐욕 규칙이 0/1 배낭에서는 깨질 수 있다. Dijkstra는 탐욕 알고리즘이지만 음수 간선에서는 최소 거리 정점을 확정하는 선택이 안전하지 않다. 언덕 오르기는 지역 최적해, 평탄 구간(plateau), 이웃 선택에 취약하다. 백트래킹은 결정문제뿐 아니라 모든 후보를 검사하며 최선값을 갱신하는 최적화 문제에도 사용할 수 있다.

시험에서 주의할 표현
  • immer
  • nur
  • jede
  • keine
  • durchschnittlich
  • optimal
  • lokal
  • global
  • gleich groß
  • nicht überlappend
직접 해 보는 실험실

설계 패러다임·DP·Greedy 실험실

다음 상태를 먼저 예측한 뒤 한 단계 실행하여 확인하세요.

준비됨

새 문장 판별 체크리스트

능동 회상

구두시험 질문

시험 직전 요약

핵심

분할 정복(D&C)은 나누고 재귀적으로 푼 뒤 결합한다. 동적 계획법(DP)은 겹치는 부분문제의 중간 결과를 저장한다. 탐욕법(Greedy)은 현재의 최선 선택에 더해 정확성 증명이 필요하다. 백트래킹(Backtracking)은 깊이 우선 탐색처럼 진행하며 상태 복원과 가지치기를 한다. 메타휴리스틱(Metaheuristic)은 최적화를 안내하는 일반 탐색 전략이지 최적해 보장이 아니다.

경계와 복잡도

분할 정복은 점화식(recurrence)으로 분석한다. 동적 계획법은 상태 수 × 전이 비용으로 계산한다. 백트래킹은 지수 시간이 걸릴 수 있다. 탐욕법과 메타휴리스틱의 실행시간은 구현과 반복 횟수 제한에 따라 달라진다.

경계 사례

부분문제를 같은 크기로 나눈다고 정확성이 보장되는 것은 아니다. DP로 풀린다고 탐욕 선택도 최적이라는 뜻은 아니다. 언덕 오르기(Hill Climbing)는 지역 최적점에 멈출 수 있다. 확률분포 없이 '평균적으로(durchschnittlich)'라고만 하면 의심해야 한다.

판정 절차

각 선택지를 볼 때 정의, 전제조건, 보장 범위, 최소 반례를 차례로 확인한다.

출처

AI 후속 학습 프롬프트

마지막 생성: 2026-08-03 03:24