[C++] 그리디

탐욕 알고리즘이라고 불리는 그리디 알고리즘이란 무엇일까?

그리디 알고리즘이란, 지금 상황에서의 최선의 선택이 곧 정답이라는 알고리즘이다.

시간적으로 효율적이지만, 매번 그리디로 푼 풀이가 정답이 아닐 수도 있다!!

 

그리디 알고리즘을 사용하려면 현재 최선의 선택이 전체 문제의 정답이어야한다.

O(N) 시간복잡도를 가지고, 백만 이상의 입력도 받을 수 있다. 주로 정렬과 우선순위 큐를 함께 이용한다.

 

그리디임을 확인하기 위해서는 많은 수학적 증명이 필요하다고 한다.

그러므로 보통의 경우, 직관적으로 판단하여 그리디를 사용한다고 한다.

 

 

 

 

 

 

[C++] 백준 알고리즘 1931 회의실 배정 (그리디) (tistory.com)

[C++] 백준 알고리즘 1931 회의실 배정 (그리디)