1장 알고리즘 소개 (1) - 방통대, 알고리즘

학습개요

알고리즘의 첫 번째 강의 시간으로서 알고리즘 전반에 걸친 기본적인 개념을 소개한다. 우선 알고리즘의 필요성과 정의를 간단히 살펴본 후, 알고리즘의 대표적인 설계 기법들에 대해서 중점적으로 학습한다.

학습목표

• 알고리즘의 중요성과 개념을 이해할 수 있다.
• 대표적인 알고리즘 설계 기법들의 종류와 개념을 이해할 수 있다.
• 거스름돈 문제와 배낭 문제의 개념, 동작 원리 및 특성을 이해할 수 있다

주요 용어

• 알고리즘 (algorithm)유한개의 일련의 명령을 순서에 따라 구성한 것
• 주어진 문제에 대해 하나 이상의 결과를 생성하기 위해 모호하지 않고 단순 명확하며 컴퓨터가 수행할 수 있는
• 욕심쟁이 방법 (greedy method)결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법
• 해를 구하는 선택 과정마다 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택하여,
• 거스름돈 문제 (coin change problem)
• 가게에서 고객에게 돌려줄 거스름돈을, 고객이 받는 동전의 개수를 최소화하면서 돌려주는 방법을 찾는 문제
• 배낭 문제 (knapsack problem)
  • 0/1 배낭 문제: 물체를 쪼갤 수 없다는 가정 하에 풀며, 이 경우 욕심쟁이 방법으로 해결할 수 없는 NP-완전문제임
• 배낭의 용량을 초과하지 않는 범위에서, 배낭에 들어있는 물체들의 이익의 합이 최대가 되도록 물체를 선택하는 문제
• 분할정복 방법 (divide-and-conquer method)순환적 하향식 접근 방식
• 문제를 작은 문제로 분할하고, 각각 해결한 후 그 해들을 결합하여 원래 문제의 해를 구하는
• 동적 프로그래밍 방법 (dynamic programming method)저장된 결과를 이용해 입력 크기가 큰 원래의 문제를 점진적으로 해결하는 상향식 접근 방식
• 문제의 입력 크기가 가장 작은 부분 문제부터 해를 구하고 이를 저장한 후,

정리하기

1. 기본 개념

• 알고리즘 : 문제 해결이나 함수 계산을 위한 명령어의 단계적 나열
• 필수 조건: 입출력, 명확성, 유한성, 유효성
• 실용적 관점: 효율성 또한 중요

---

2. 알고리즘 설계 과정

1. 설계
   • 문제 해결을 위한 전반적 접근 방법 구상
2. 표현(기술)
   • 알고리즘을 코드나 수식 등으로 구체화
3. 정확성 분석
   • 알고리즘이 올바른 결과를 내는지 검증
4. 효율성 분석
   • 시간 및 공간 복잡도 평가

반응형

---

📌 3. 대표적 알고리즘 설계 방법

3.1 욕심쟁이(그리디) 방법

• 전략: 각 단계에서 국부적 최적해(최선의 선택)를 함으로써 전체 최적해 도출 시도
• 한계: 국부 최적해가 전체 최적해로 이어지지 않을 수 있음
• 적용 사례:
  • 거스름돈 문제: 최소 동전 개수 문제 (단, 모든 동전 액면가에 적용 불가)
  • 배낭 문제: 0/1 배낭 문제에는 부적합
  • 최소 신장 트리: 크루스칼, 프림 알고리즘
  • 단일 출발점 최단 경로: 데이크스트라 알고리즘

3.2 분할정복 방법

• 전략: 문제를 더 이상 분할할 수 없을 때까지 작은 문제로 나눈 후, 각 문제를 해결해 결과를 결합
• 특징:
  • 분할된 문제는 원래 문제와 동일한 성질을 가지며 독립적임
• 단계: 분할 → 정복 → 결합
  • 분할 : 주어진 문제의 입력을 여러개의 작은 문제로 분할
  • 정복 : 작은 문제들을 순환적으로 분할하고, 문제가 더 이상 분할할 수 없을 정도로 충분히 작아지면 순환 호출 없이 직접 해를 구함
  • 결합 : 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함
• 적용 사례:
  • 이진 탐색
  • 퀵 정렬
  • 합병 정렬

3.3 동적 프로그래밍 방법

• 전략: 가장 작은 문제부터 해결하여 결과를 저장(메모이제이션)하고, 이를 이용해 점진적으로 큰 문제 해결
• 특징:
  • 분할된 문제들이 반드시 독립적일 필요는 없음
• 적용 사례:
  • 플로이드 알고리즘(모든 정점 쌍 최단 경로)
  • 행렬의 연쇄적 곱셈 문제
  • 최장 공통 부분 수열 문제