https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 알고리즘 분류 그리디 정렬 풀이 그리디 알고리즘을 사용해 풀었다. 핵심 로직은 이러하다. 먼저 StringTokenizer로 물이 세는 곳을 저장한뒤, 새는 곳이 차례대로 있어야 최소한의 테이프를 쓰게 되니 정렬까지 진행했다. st = new StringTokenizer(br.readLine()); for (int i = 0; i < temp.length; i++) { temp[i..

그리디라는 사전적 의미는 "탐욕스러운" 이다. 즉, 탐욕적으로 "현재 상황에서 가장 베스트인 것만 고르는 방법"인 알고리즘이다. 부분 최적해가 모이면 전체 최적해가 되다는 알고리즘이다. ​ 예를들어 서울 대구 부산을 지나간다고 가정을 해보자 (서울 - 대구 길에서 가장 빠른 길) + (대구 - 부산길에서 가장 빠른길) 를 찾아 더하면 최적해를 구할 수 있다. ​ 이 알고리즘이 쓰이게 된 이유는 속도 때문이다. 완전탐색으로 정답을 찾게 되면 속도가 느리게 되니 DP 알고리즘을 사용하게 됐다. 하지만 DP프로그래밍도 항상 최적해를 보장하기 위해서 모든 경우의 수를 고려한다. 그러다보니 속도가 느려지게 된다. 그래서 항상 최적해를 찾는 그리디를 사용해 좀더 빠르게 문제를 풀 수 있게 되었다. 현실에서는 최적해..