탐욕적기법2 BOJ 4796 캠핑 문제 링크 : https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 요약 캠핑장을 연속하는 P일 중, L일동 안 만 사용할 수 있다. 강산이는 이제 막 V일자리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠 동안 사용할 수 있는지 구하는 문제다. 풀이 V일의 휴가동안 캠핑장을 최대로 사용하려면 P일이 젤 많이 포함되게 하여야 한다. P일중 가장 빠른 날부터 L일동 안 사용한 후 P-L일만큼 쉰 후 바로 다시 L일 동안 사용해야지 가장 많이 포함.. 2022. 3. 10. 탐욕적 기법(Greedy Algorithm) 탐욕적 기법(Greedy Algorithm)은 이름 그대로 항상 눈앞의 가장 큰 이익만을 좇는 방법입니다. 어떤 경우에 사용할까? 그리디 알고리즘으로 최적의 해를 구할 수 있는 문제는 많지는 않다. 하지만 이런 방법이 통하는 문제들이 분명 존재하고 전략을 파악했을 때 간단히 해결이 가능한 문제가 많기 때문에 대회나 코테에 자주 나온다. 문제를 해결하는 과정에서 한 가지의 전략을 선택을 하였을 때 그 이후에도 원래 문제와 동일한 성질이 성립하여야 한다. 성질이 동일하게 보존되어야 썼던 전략을 계속 취해도 답을 구할 수 있기 때문이다. 보통 풀이가 가장 큰, 긴, 빠른~ 것부터 해결해야 하는 경우가 많은 편이다 보니 정렬이 필요할 때가 많다. 예시 그리디 알고리즘의 대표적인 예시로 동전 문제가 있다. 백준 .. 2022. 3. 10. 이전 1 다음
