https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 알고리즘 분류 수학 그리디 정렬 풀이 그리디 알고리즘과 정렬을 이용해 문제를 풀었다. 먼저 삼각형의 성립 조건을 알아야 한다. 삼각형의 성립 조건: a, b, c(가장 긴 변)이 있을 때 a + b > c 이어야 삼각형이 성립이 된다. 그래서 입력받은 배열을 정렬 후 뒤에서부터 차례로 삼각형이 성립이 되는지 if 조건문을 사용해 구했다. Arrays.sort(arr); fo..

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