(Approximation algorithm): 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미한다. 해당 알고리즘은 가장 최적화된 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 간으하며 어느 정도 보장된 근사해를 계산할 수 있다.

• NP-완전 문제 등 현재 알려진 빠른 최적화 알고리즘이 없는 문제에서 주로 사용된다.

NP-완전 문제를 해결하기 위해 아래 세가지 중 한가지는 포기해야한다.

1. 다항식 시간에 해를 찾는 것
2. 모든 입력에 해를 찾는 것
3. 최적해를 찾는 것

• Traveling Salesman Problem (여행자 문제)
• Vertex cover problem (정점 커버 문제)
• Job scheduling problem (작업 스케줄링 문제)

참고문헌

https://throwexception.tistory.com/306

백준 문제

https://www.acmicpc.net/problem/16435

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    int n; // 과일의 개수
    int l; // 초기 길이
    std::cin >> n >> l;

    std::vector<int> h(n); // 정수
    for (int i = 0; i < n; i++) {
        std::cin >> h[i];
    }

    std::sort(h.begin(), h.end());

    for (int i = 0; i < n; i++) {
        if (h[i] <= l) {
            l += 1;
        }
    }
    std::cout << l;

    return 0;
}