-
[알고리즘] 탐욕적 기법(Greedy Algorithm)프로그래밍/알고리즘 2019. 5. 29. 16:02
Goal
1. 탐욕적 기법(Greedy Algorithm)의 개념
2. 탐욕적 기법(Greedy Algorithm)의 특징
3. 탐욕적 기법(Greedy Algorithm)의 구현서론
가장 유명하지만 가장 기초적이어서, 알고리즘에 입문하기 가장 좋은 녀석입니다. 접근법이 굉장히 직관적이고 단순하기 때문에 알고리즘 대회, 코딩 테스트에서 적지 않게 볼 수 있습니다. 그래서 저는 그리디 알고리즘 문제를 적어도 10 문제 정도는 풀어보고 다른 알고리즘을 풀어보시는 걸 추천드립니다. 왜냐하면 10문제 정도 풀어보시면, 내가 생각하는 것을 코드로 구현하는 능력과 문제를 직관적으로 보는 능력이 생기기 때문입니다.
개념
서론이 길었습니다. 탐욕적 기법(Greedy Algorithm), 욕심쟁이 기법 혹은 그냥 그리디 알고리즘이라고도 불리는 이 기법은 말 그대로 항상 눈 앞의 가장 큰 이익만을 쫒는 방법입니다. 물론, 이 방법이 항상 먹히는 건 아닙니다. 하지만, 이 방법이 통하는 문제들이 많고, 이 방법을 사용하였을 때 간단하게 해결이 가능한 문제들이 많기 때문에 대회나 테스트에 자주 나오겠죠?
그렇다면, 어떤 문제들에 탐욕적 기법을 사용할까요? 탐욕적 기법을 사용하여 최적의 해를 구할수 있는 문제들의 특징은 한 번의 선택을 한 이후에도 선택 전의 성질이 계속해서 유지되는 문제들입니다. 대표적인 문제들로는 도시락 데우기, 캠핑 날짜 계산하기 등이 있습니다.
그리디 문제의 어려운 점은 문제를 보고 이 문제가 그리디인지 파악하기가 쉽지 않습니다. 대부분 느낌이 "이거 BFS 사용하면 될것 같은데? " 정도의 감이 옵니다. 하지만 그리디 문제는 그런 감을 찾는데 시간이 조금 오래 걸립니다. 그리디 문제들은 대체로 풀이가 단순하다 보니 시간 복잡도도 작은 편인데, 이 부분을 감추려는 건지 문제의 크기가 작은 문제들도 많습니다.
아무리 말을 많이 해도 한번 해보는게 좋겠죠? 예제를 한번 살펴봅시다.
예제 : BOJ 4796_캠핑
구글 이미지 검색 문제 : 캠핑장을 연속하는 P일 중, L일 동안만 사용할 수 있다. 강산이는 이제 막 V 일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠 동안 사용할 수 있을까? (1 < L < P < V)
예를 들어, 캠핑장이 연속하는 20일 중 10일 동안만 사용할 수 있고 강산이는 28일짜리 휴가를 막 시작했다고 합시다.
강산이는 캠핑장을 최대로 이용하고 싶어합니다. 그러기 위해서는 반드시 휴가 첫날부터 캠핑을 시작해야 합니다. 이것은 자명한 사실이며, 어떠한 L, P, V 값이 주어져도 달라지지 않습니다. 이런 식으로 주어지는 값에 따라서 문제의 접근방식이 변하지 않으며, 현재의 결정이 다음 결정에 영향을 끼치지 않는 문제들에 대해서 그리디 기법을 사용합니다. 해당 문제의 자세한 풀이과정은 여기로 가시면 볼 수 있습니다.
예제
4796번: 캠핑
문제 등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다. 캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다. 강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까? 강산이는 조금 더 일반화해서 문제를 풀려고 한다. 캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대
www.acmicpc.net
1931번: 회의실배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
1700번: 멀티탭 스케줄링
기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어
www.acmicpc.net
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] 동적 계획법(Dynamic Programming) (0) 2019.06.07 [알고리즘] 집합 찾기(Union Find) (0) 2019.06.05 [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) (0) 2019.05.26 [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) (0) 2019.05.23 [알고리즘] 해시 테이블 (Hash Table) (0) 2019.04.30