greedy11 BOJ 1449 수리공 항승 문제 링크 : https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 요약 물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 문제(구멍을 막으려면 좌우 0.5 간격이 필요함, 테이프는 겹쳐도 됨) 풀이 구멍을 막을때 좌우 0.5 간격이 필요함으로 1이 필요하다. 테이프로 한 번에 간격의 길이가 L-1인 구간을 덮을 수 있다. 제일 왼쪽에 있는 점부터 시작하여 오.. 2022. 3. 10. 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 2 3 다음
