그리디 - 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
그리디 알고리즘은 현재 순간 가장 좋아 보이는 것을 선택하고 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는 알고리즘이다.
어떤 문제가 그리디 알고리즘 문제인지 의심된다면 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 풀 수 있는 문제인지를 판단한 후에 적용해야 한다. 그리디 알고리즘을 위한 문제가 아닌 대부분의 문제는 그리디로는 최적의 답을 찾을 수 없기 때문이다.
정해진 방법이 있는 알고리즘이 아니라 아이디어만 떠오른다면 비교적 간단하게 풀 수 있는 유형이기 때문에 문제를 풀어보면서 감을 잡아보려고 한다.
다음은 백준 단계별로 풀어보기 - 그리디 알고리즘 파트의 문제들이다.
[11047] 동전 0 - Python
/* 문제 */ 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하
ant-hill.tistory.com
[1931] 회의실 배정 - Python
/* 문제 */ 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게
ant-hill.tistory.com
[11399] ATM - Python
/* 문제 */ 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사
ant-hill.tistory.com
[1541] 잃어버린 괄호 - Python
/* 문제 */ 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
ant-hill.tistory.com
[13305] 주유소 - Python
/* 문제 */ 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려
ant-hill.tistory.com