특강) 알고리즘 설계 기법

I. 알고리즘 = '레시피'에 비유.

• 하나의 문제에 대해 여러 Algorithm 기술 가능
  • ex) 곱셈 알고리즘 → Long Multiplation, Lattice multiplation, Peasant multiplation
    

II. 알고리즘의 기술 방법

• 경험, 노하우의 영역

• 알고리즘의 대표적 기술 방법 3가지

  1. 자연어 기술
  2. Pseudo Code
  3. Program Code

• 알고리즘 분석 방법

  1. Correctness Proof
  • '올바른 출력이 나온다' 증명
    수학적 귀납법을 주로 활용.
  2. Runnig Time Analysis
  • 시간 복잡도 분석
  • 실행 시 걸리는 시간 분석

IV. Recursion. '재귀'에 대해서

• 중요 포인트: 하나의 큰 문제가 'Sub Problem (부분 문제)'로 분할된다.
• Divide-and-Conquer, BackTracking, Dynamic Programming, Greedy Algorithm
• 반복문 ↔ 재귀 : 서로 변환 가능
  

V. Reduction의 개념

• 문제 x를 풀기 위한 알고리즘을 기술할 때, 문제 y를 해결하는 알고리즘을 사용(내부 호출) 함.
  →이 때, 함수 y의 내부 동작에는 어느 정도 무시(ignorance), 문제 y를 정확히 해결한다는 사실만 가정.

• Recursion의 개념도 Reduction의 일종!

• Recursion: 같은 함수(문제)로 Reduction 하는 것. 단, 입력 사이즈가 줄어들어야 (reduce) 함.

  ex) Selection 문제 해결을 위해 Sorting 알고리즘을 Subroutine으로 활용
  
  

• Simplyfy & Delegate
  • Simplyfy: 더 작은 instance를 만들고
  • Delegate: 던져버리고 잊어버려!

*요점

• Recursion!

  • 알고리즘 설계에서 가장 중요한 개념

• Divide-and-Conquer!

  • 크게 자르는 recursion

• Backtracking!

  • 하나씩 줄여 나가는 recursion

• Dynamic Programming!

  • 반복 계산을 없앤 recursion

참고 자료/이미 출처

경기대학교 AI 컴퓨터공학부 배상원 교수님 :: 알고리즘 설계 기법