알고리즘 이론 정리

이진 탐색과 선택 알고리즘에 대해서 알아보자.

분할 정복 알고리즘은 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘이다. 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산한다. 이 때, 분할된 입력에 대한 문제를 부분 문제(subproblem)이라고 하고, 부분 문제의 해를 부분 해라고 한다

그리디 알고리즘은 최적화 문제를 해결하는 알고리즘이다. 그리디 알고리즘은 입력 데이터 간의 관계를 고려하지 않고, 수행 과정에서 최소값 또는 최대값을 가진 데이터를 선택한다. 최적화(optimization) 문제: 가능한 해들 중에서 최대 또는 최소의 해를 찾는 문제이

동적 계획 알고리즘(Dynamic Programming)은 입력크기가 작은 부분 문제들을 해결한 후에, 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결해나가는 알고리즘 방식이다. DP 알고리즘은 문제의 최적해 속에 부분 문제의 최적해가 포함되어 있음을 활용하며,

선택 정렬은 입력의 정렬 여부와 상관없이 항상 일정한 시간 복잡도를 나타낸다.입력에 민감하지 않은 (input insensitive) 알고리즘이며, 원소 간의 자리바꿈 횟수가 최소인 정렬이다.배열의 첫 번째 원소만이 정렬된 부분에 있는 상태에서 정렬을 시작한다.삽입 정

다항식 시간보다 큰 복잡도를 가진 알고리즘으로 해결되는 문제의 집합 중에서,지수 시간 복잡도를 가진 알고리즘으로 해결되는 문제들을 NP-완전 문제라고 한다.NP-완전 문제는어느 하나의 NP-완전 문제에 대해서 다항식 시간에 해를 찾을 수 있는 알고리즘을 찾아내면,모든