알고리즘의 정의

📌 주어진 문제에 대해 하나 이상의 결과를 생성하기 위해,
모호하지 않고 단순 명확하며 컴퓨터가 수행할 수 있는 유한개의 일련의 명령을 순서에 따라 구성한 것

• (입출력) 0개 이상의 외부 입력과 1개 이상의 출력을 생성

• (명확성) 각 명령은 모호하지 않고 단순 명확해야 함

• (유한성) 한정된 수의 단계를 거친 후에는 반드시 종료함

• (유효성) 모든 명령은 컴퓨터에서 수행할 수 있어야 함

• 실용적 관점 → (효율성) 알고리즘은 효율적이어야 함

---

알고리즘 생성 단계

1. 설계
   • 상향식 설계, 하향식 설계, …
   • 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법, …
2. 표현/기술
   • 일상 언어, 순서도, 의사코드, 프로그래밍 언어, …
3. 정확성 검증
   • 수학적 증명
4. 효율성 분석
   • 공간 복잡도
   • 시간 복잡도

---

알고리즘 설계

• 주어진 문제와 조건 등이 매우 다양 → 일반적/범용적인 설계 기법은 미존재
  
• 대표적인 알고리즘 설계 기법
  • 욕심쟁이 (greedy) 방법
  • 분할정복 (divide-and-conquer) 방법
  • 동적 프로그래밍 (dynamic programming) 방법

욕심쟁이 방법

탐욕적 방법, 그리디 알고리즘 (greedy algorithm)

• 해를 구하는 일련의 선택 과정에서 전후 단계의 선택과는 상관없이
  단계마다 ‘가장 최선’이라고 여겨지는 국부적인 최적해를 선택해 나가면
  결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법

• 희망적 → 각 단계마다 선택한 국부적인 최적해가 항상 전체적인 최적해를 만들지 못할 수도 있음

• 간단하면서 효율적인 알고리즘을 만들 수 있는 강력한 기법

• 최솟값/최댓값을 구하는 최적화 문제에 주로 사용

• 한계 : 국부적인 최적해들이 전체 최적해를 구성하지 못하는 경우도 있다.

• 응용 문제

  • 거스름돈 문제 : 가게에서 고객에게 돌려줄 거스름돈이 T만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제
  • 배낭 문제 : 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체들의 이익의 합이 최대가 되도록 물체를 넣는 방법(또는 최대 이익)을 찾는 문제
    • 가정 : 물체를 쪼개서 넣을 수 있음

분할정복 방법

• 순환적으로 문제를 푸는 하향식(top-down) 접근 방법

  • 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제들로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후, 이들의 해를 결합하여 원래 문제의 해를 구하는 방식
    

• 특징

  • 분할된 작은 문제는 원래 문제와 동일
    • 입력의 크기만 작아짐
  • 분할된 문제는 서로 독립적
    • 순환적인 분할 및 결과의 결합이 가능

• 각 순환 호출마다 세 단계의 작업을 수행

  • 분할
    • 주어진 문제의 입력을 여러 개의 작은 문제로 분할
  • 정복
    • 작은 문제들을 순환적으로 분할
    • 만약 작은 문제가 더 이상 분할되지 않을 정도로 크기가 충분히 작으면 순환 호출 없이 작은 문제에 대한 해를 구함
  • 결합
    • 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함

• 대표적인 문제

  • 퀵 정렬, 합병 정렬, 이진 탐색

동적 프로그래밍 (DP)

• 입력의 크기가 가장 작은 부분 문제부터 해를 구하여 테이블에 저장해 놓고, 이를 이용해서 입력 크기가 보다 큰 문제의 해를 점진적으로 만들어 가는 상향식(bottom-up) 접근 방법
  • 각각의 작은 문제는 원래 문제와 동일, 입력의 크기만 작음
  • 작은 문제들은 서로 독립일 필요가 없음 (↔ 분할정복 방법)
    • 중복되는 부분이 있어, 그 결과를 테이블에 저장해두고 이용함
• 대표적인 적용 문제
  • 모든 정점 쌍 간의 최단 경로 → 플로이드 알고리즘