알고리즘 문제

1. 주요 알고리즘 문제들 例)

  ㅇ 거스름돈 문제 (Coin Change Problem)
     - 최소 동전 수로 금액 만들기
     - 문제 유형  :  최적화 문제
     - 해결 기법  :  욕심쟁이 알고리즘, 동적계획법

  ㅇ 배낭 문제 (Knapsack Problem)
     - 배낭 내 합이 최대가 되도록 물건을 넣는 방법 
        . 배낭에 담을 최대 무게에 따라, 배낭에 넣을 가치가 최대가 되는 조합을 찾음
        . 제한된 무게 내 최대 가치 선택
           .. 용량을 초과 않으면서 담을 수 있는 물건의 총 가치를 최대화
     - 문제 유형  :  조합 최적화 문제 (combinatorial optimization)
     - 해결 기법  :  동적계획법, 백트래킹

  ㅇ 외판원 문제 (Traveling Salesman Problem, TSP)
     - 모든 도시들을, 단 한 번씩 만 방문하고, 원래 시작점으로 돌아오는, 최소 비용의 이동 순서
     - 종류  :  대칭 TSP (양방향 동일 길이를 갖는 간선), 비대칭 TSP
     - 문제 유형  :  NP 문제에 속함
        . 계산 복잡도 이론에서, 해를 구하기 어려운 문제의 대표적인 예
     - 해결 기법  :  동적계획법, 분기한정법, 근사 알고리즘