01. 알고리즘의 정의와 필요성

1. 알고리즘의 정의
   
   • 어떤 문제를 해결하기 위한 여러 동작들의 모임을 기술한 것
   • 프로그램 = 자료구조 + 알고리즘
2. 알고리즘의 특징
   1. 알고리즘의 요건 
      1. 입출력 : 입력과 출력을 가지고 있어야 함
      2. 정확성 : 주어진 입력에 대해 항상 올바른 답을 주어야 함
      3. 유한성 : 유한 시간 내에 종료되어야 함
      4. 효율성 : 시간적, 공간적 효율성을 가져야 함
      5. 수행성(컴퓨터) : 컴퓨터로 수행이 가능해야 함
   2. 알고리즘의 분석 기준
      1. 정확성
         • 모든 유효한 입력에 대해서 유한 시간 내에 올바른 해를 찾아내는가를 판단
      2. 기억 장소 사용량
         • 해를 찾아내는 데 사용되는 기억 장소의 사용량
         • 입력 개수에 따른 증가율이 중요함
      3. 수행 시간
         • 해를 찾아내는 데 걸리는 시간 절대 시간보다는 입력 개수에 따른 증가율이 중요함
   3. 알고리즘의 분류

      분류 방식	분류
      문제 해결 방법에 따른 분류	① 분할 정복 알고리즘(Divide and Conquer Algorithm) ② 그리디 알고리즘(Greedy Algorithm) ③ 동적 계획 알고리즘(Dynamic Programming Algorithm) ④ 근사 알고리즘(Approximation Algorithm) ⑤ 백트래킹 알고리즘(Backtracking Algorithm) ⑥ 분기 한정법(Branch and Bound) ...
      문제에 따른 분류	① 정렬 알고리즘(Sorting Algorithm) ② 그래프 알고리즘(Graph Algorithm) ③ 기하 알고리즘(Geometric Algorithm) ...

      1. 문제 해결 방법에 따른 분류
         1. 분할 정복 알고리즘
            1. 주어진 문제의 입력을 분할하여 문제를 해결하는 알고리즘
            2. 분할된 입력에 똑같은 알고리즘을 적용함(재귀를 이용하는 경우가 많음)
            3. 예: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 선택 정렬(Selection Sort) 등
         2. 그리디 알고리즘
            • 가능한 해들 중에서 가장 좋은 해를 찾는 알고리즘
            • 수행 시점에서 가장 좋은 해를 찾아 나감
              • 근시안적인 최적해를 찾는다고 할 수 있으며 근시안적인 최적해들을 모아서 문제의 최적해를 찾음
            • 예: 동전 거스름돈 문제, 최소 신장 트리 문제, 최단 경로 찾기 문제, 부분 배낭 문제 등
         3. 동적 계획 알고리즘
            • 최적해 문제 해결 알고리즘
            • 입력 크기가 작은 부분 문제를 해결하고, 이를 이용해서 보다 큰 부분 문제들을 해결하여, 최종적으로 주어진 입력 크기의 문제를 해결하는 방법
            • 예: 모든 쌍 최단 경로, 연속 행렬 곱셈, 배낭 문제, 동전 거스름돈 문제 등
         4. 근사 알고리즘
            • 지수 시간이 걸리는 문제(NP 문제)에 대한 근사해를 찾는 알고리즘
            • 예: 여행자 문제, 정점 커버 문제, 통 채우기 문제, 클러스터링 문제
         5. 백트래킹 기법
            • NP 완전 문제의 해를 탐색하기 위한 알고리즘
            • 예: 여행자 문제, 체스 퀸 배치 문제
         6. 분기 한정 기법
            • 큰 입력에 대해서 백트래킹 기법이 갖는 단점을 보완하기 위해 고안된 기법
            • 예: 여행자 문제 등