그리드 알고르즘이란?
매 선택에서 최적이라는 생각되는 값을 또는 지금 이 순간 당장 최적인 답을 선택하는 알고리즘입니다.
그러나 최선의 답을 선택함에도 불구하고, 전체적인 부분을 봤을 때는 최선이 아닐 수 있습니다.
전체적인 부분으로 최선이 아니라는 말은 아래 노드를 보며 설명하도록 하겠습니다.
아래의 그림은 노드의 숫자 합이 가장 큰 선택을 하였습니다.
왼쪽 노드의 경우 일반적으로 전체적인 부분을 봤을 때는 1-2-99가 제일 합이 크기 때문에 최선의 선택이나
오른쪽 노드의 경우 지금 이 순간 당장 최적의 답을 선택한다면 1-10-40 입니다.
그렇기 때문에 매 순간마다 최선의 답을 선택 했지만 전체적인 부분을 봤을 때는 최선이 아니라는 말입니다.
그리드 알고리즘을 사용하는 이유?
N번 그리드를 반복해서 수행 한다면 O(n)이라는 시간 복잡도가 나옵니다.
즉, 그리드의 큰 장점은 계산 속도가 빠르다는 것입니다.
몇몇 문제에서는 최적해를 빠르게 찾아 낼 수 있는데 그리디 알고리즘을 사용할 수 있는 문제는 두가지 속성을 만족해야합니다.
1. 탐욕 선택 속성(greedy choice property)
-> 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 한다. ( 앞의 선택이 이후의 선택에 영향을 주면 안된다. )
2. 최적 부분 구조(optimal substructure)
-> 매 순간의 최적해가 문제에 대한 최적해여야 한다. ( 문제 전체에 대한 최적해가 부분 문제에 대해서도 역시 최적해가 된다.)
예제 문제 및 풀이
https://bokhead.tistory.com/27
[백준 - C#] 11047 동전 0
문제링크 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤..
bokhead.tistory.com
https://bokhead.tistory.com/26
[백준 - C#] 11399 ATM
문제링크 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www..
bokhead.tistory.com
https://bokhead.tistory.com/33
[백준 - C#] 2720번 세탁소 사장 동혁
문제링크 https://www.acmicpc.net/problem/2720 2720번: 세탁소 사장 동혁 각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다. www.acmicpc.net.
bokhead.tistory.com
https://bokhead.tistory.com/32
[백준 - C#] 5585번 거스름돈
문제링크 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가..
bokhead.tistory.com
2839, 1026 작성중
참고 자료