[알고리즘] 04/06 알고리즘 공부

종합 시험이 있어 건네 받은 문제 은행을 토대로 DP, Greedy, Divide and Conquer, Master 정리, P,NP,NP-complete,NP-Hard, 정지 문제에 대해 공부한 내용으로 정리하였다. 

 

DP(Dynamic Programming, 동적 계획법)

- 큰 문제를 작은 문제로 나누어 푸는 최적화 기법
- 중복되는 부분 문제가 존재하고, 이를 한번만 계산하고 결과를 저장해둠으로써 중복 계산을 줄임
- Memoization(메모이제이션) 기법을 사용하여 이미 계산된 값을 저장해둠
- 예시: 피보나치 수열, 최장 증가 부분 수열(LIS) 등

Greedy Algorithm(탐욕 알고리즘)

- 각 단계에서 지금까지의 선택이 전체적인 결과를 만족시키는 최적해가 되는 방식
- 각 선택마다 최적이라고 생각되는 것을 선택하여 문제를 해결하는 방식
- 최적해가 항상 보장되지는 않으나, 적은 시간에 대해 빠른 수행 시간을 가짐
예시: 분할 가능 배낭 문제, 최소 신장 트리(MST) 등

Divide and Conquer(분할 정복)

- 문제를 작은 문제로 분할하여 해결하는 방식
- 분할한 작은 문제를 해결한 다음, 이를 결합하여 전체 문제를 해결함
- 재귀적인 호출을 통해 구현되며, 분할과 결합 단계를 구현해야 함
- 일반적으로 O(n log n) 시간 복잡도를 가지며, 큰 문제를 작은 문제로 나누는 방법에 따라 다양한 종류의 알고리즘이 존재함
예시: 병합 정렬, 퀵 정렬, 최대 부분 배열(Maximum-subarray) 문제 등

Master Theorem

- 분할 정복 알고리즘의 시간 복잡도를 계산하는 방법 중 하나
- 점화식의 형태를 T(n) = aT(n/b) + f(n) 으로 가정하고, a, b, f(n)에 대한 조건을 만족할 경우 시간 복잡도를 계산할 수 있는 방법
예시: 병합 정렬, 퀵 정렬 등

 

Master Theorem에서는 점화식의 형태를 T(n) = aT(n/b) + f(n) 으로 가정합니다. 여기서 a는 분할되는 부분 문제의 개수, b는 분할될 때 크기가 줄어드는 비율을 의미합니다. f(n)은 분할이 일어나지 않는 부분의 시간 복잡도입니다.

Master Theorem에서는 a, b, f(n)에 대한 조건에 따라 다음과 같이 3가지 case로 분류됩니다.

Case 1: f(n) = O(n^c), c < log_b(a) 분할되는 문제들의 개수가 전체 문제를 해결하는 데 더 많은 시간이 소요됨
시간 복잡도: O(n^log_b(a))

Case 2: f(n) = Θ(n^c), c = log_b(a) 분할되는 문제들의 개수와 전체 문제를 해결하는 데 필요한 시간이 같음
시간 복잡도: O(n^c log n)

Case 3: f(n) = Ω(n^c), c > log_b(a) 분할되는 문제들의 개수가 전체 문제를 해결하는 데 덜 많은 시간이 소요됨
시간 복잡도: O(f(n))

위 3가지 case는 분할 정복 알고리즘의 시간 복잡도를 계산하는데 유용합니다. 각 case마다 a, b, f(n)에 대한 조건을 만족하는 분할 정복 알고리즘을 찾아서 시간 복잡도를 계산할 수 있습니다.

 

P (Polynomial Time)
P는 다항 시간 내에 해결할 수 있는 문제의 집합을 나타내는 개념입니다. 다항 시간 알고리즘이란 입력의 크기에 대해 다항식 시간 내에 문제를 해결하는 알고리즘입니다. 즉, 입력 크기가 n일 때, O(n^k) 시간 안에 해결할 수 있는 알고리즘이 P에 속합니다. 대표적인 예로 정렬 알고리즘이 있습니다.

NP (Nondeterministic Polynomial Time)
NP는 다항 시간 내에 해결할 수 있는지는 모르지만, 해결된 답이 다항 시간 내에 확인 가능한 문제의 집합을 나타내는 개념입니다. 다항 시간 알고리즘이 존재하지 않지만, 답이 주어졌을 때 답이 맞는지 검증하는 알고리즘이 존재합니다. 대표적인 예로 여행하는 외판원 문제가 있습니다.

NP-complete
NP-complete는 NP에 속하며, 모든 NP 문제가 다항 시간 내에 해결 가능한 알고리즘이 존재한다면 이들 중 가장 어려운 문제를 나타냅니다. NP-complete 문제는 다항 시간 알고리즘이 없는 이론적으로 가장 어려운 문제들 중 하나입니다. NP-complete 문제 중 대표적인 예로는 SAT 문제가 있습니다.

NP-hard
NP-hard는 NP-complete와 같이 다항 시간 알고리즘이 존재하지 않는 이론적으로 어려운 문제를 나타냅니다. 하지만 NP-hard 문제는 NP에 속하지 않을 수도 있습니다. 즉, NP-hard 문제는 NP-complete 문제와 비슷하지만, NP-complete 문제보다 더 어려운 문제를 의미합니다.

 

정지 문제 (Halting Problem)

정지 문제는 주어진 튜링 기계와 입력에 대해 해당 튜링 기계가 멈추는지 (정지하는지) 여부를 결정하는 문제입니다.

정지 문제는 "현재 실행 중인 프로그램이 계산을 끝내고 언젠가 종료하는지 아니면 영원히 계산을 반복하는지 판별하는 기계가 존재할 수 있는지를 묻는 문제"입니다. 아래 영상을 보면 살짝 이해가 가능