[Algorithm] 알고리즘 / 욕심쟁이, 분할정복, 동적프로그래밍 방법
알고리즘(algorithm)
-
주어진 문제를 해결하기 위한 일련의 단계적인 처리 과정
-
일상적인 언어, 순서도, 의사 코드, 프로그래밍 코드 등의 다양한 방법으로 표현되고 기술될 수 있음
-
알고리즘을 기반으로 컴퓨터가 주어진 데이터를 어떻게 처리할지 작성된 컴퓨터 프로그램 + 올바른 입력 → 컴퓨터가 정확하고 유용한 결과를 생성
-
즉, 프로그램 = 알고리즘을 적절한 프로그래밍 언어로 표현해 컴퓨터가 이해하고 실행할 수 있도록 만든 명령어의 모임
-
알고리즘이 만족해야 하는 조건
-
입출력 : 외부에서 0개 이상의 입력을 받아 하나 이상의 출력을 생성해야 함
-
명확성 : 각 명령은 모호하지 않고 단순, 명확해야 함
-
유한성 : 한정된 수의 명령을 거친 후에는 반드시 끝나야 함
-
유효성 : 모든 명령은 컴퓨터에서 수행 가능해야 함
→ 알고리즘 = 주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 단순 명확하며 컴퓨터가 수행할 수 있는 유한개의 일련의 명령어들을 순서에 따라 구성한 것
-
욕심쟁이(greedy) 방법
-
전후 단계의 선택과는 상관없이 각 단계마다 정해진 기준에 따라 가장 최선이라고 여겨지는 국부적인 최적해를 선택 → 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취함
-
각 단계에서 전후 단계의 선택에 대해서는 아무런 고려 없이 단지 현재 상태에서만 만족하는 최적해를 선택 → 국부적인 최적해가 항상 전체적인 최적해를 만들지 못할 수도 있음
-
ex) 거스름돈 문제, 배낭 문제, 크루스칼 알고리즘, 프림 알고리즘, 데이크스트라 알고리즘 등
분할정복(divide-and-conquer) 방법
-
순환적으로 문제를 푸는 하향식 접근 방법
-
주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제들로 순환적으로 분할 → 분할된 작은 문제들을 각각 해결 → 이들의 해를 결합해 원래 문제의 해를 구하는 방식
-
각 순환 호출마다 ‘분할-정복-(결합)’ 세 단계의 작업이 이루어짐
-
분할(divide) : 주어진 문제의 입력을 여러 개의 작은 문제로 분할
-
정복(conquer) : 작은 문제들을 순환적으로 분할, 더 이상 분할되지 않을 정도로 충분히 작으면 순환 호출 없이 작은 문제의 해를 구함
-
결합/합병(combine) : 작은 문제에 대한 해를 결합해 원래 문제의 해를 구함
-
-
쪼개진 문제들은 원래 문제에 비해 입력 크기만 작아졌을 뿐 문제 자체는 원래 문제와 동일, 서로 독립적
-
ex) 퀵 정렬, 합병 정렬, 이진 탐색 등
동적 프로그래밍(dynamic programming) 방법
-
입력 크기가 가장 작은 부분 문제부터 해를 구하여 저장 → 이를 이용해 입력 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법
-
작은 문제들은 서로 독립일 필요가 없고, 한 번 사용한 작은 문제의 해가 다음에 또 사용될 수 있음 → 작은 문제의 해를 테이블에 저장해 두고 필요할 때마다 바로 사용하는 방식을 취함