그리디
BOJ 2457 공주님의 정원 [Java]
BOJ 2457 공주님의 정원 1. 문제 링크 https://www.acmicpc.net/problem/2457 2. 문제 해설 그리디 알고리즘을 이용하여 푸는 문제이다. 백준 문제 중 1931번 회의실 배정과 비슷한 결을 가진 문제이다. 1931번을 풀어보지 않았다면 먼저 풀어보도록 하자. https://www.acmicpc.net/problem/1931 다시 문제로 돌아와서, 일단 그리디를 이용해서 풀면 될 것 같다는 생각은 들었지만 그리디를 이용하려면 검증이 필요하다. 매번 최선의 선택을 한 것이 전체적으로 봤을 때도 최선의 답이라는 것을 검증해야한다. 그 전에 일단 내가 어떻게 문제를 그리디적으로 접근했는지 살펴보자. 1. 3월 1일을 기준일로 잡는다. 2. 기준일보다 일찍 피는 꽃들 중에서 가장..
그리디 알고리즘
그리디 알고리즘 그리디 알고리즘이란 지금 주어진 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 결과를 선택한 결과 값이 전체적으로도 최선이기를 바라는 알고리즘이다. 일반적인 그리디 알고리즘 풀이 방법을 적어보자면 아래와 같은 흐름을 따른다. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 탐색 범위를 줄여도 올바른 답을 낸다는 것을 수학적으로 증명한다. 알고리즘을 구현한다. 그리디 알고리즘은 모든 경우에서 통하는 알고리즘은 아니다. 현재에 약간 손해보더라도 전체적으로 봤을 때는 이득인 경우에 통하지 않는데, 예를 들자면 유명한 마시멜로 이야기와 같이 지금 당장은 마시멜로를 1개를 받을 수 있지만 조금 기다리는 경우 2개를 받을 수 있는 경우 그리디 알고리즘으로 풀면 틀린 경우가..