백준 (5) 썸네일형 리스트형 Greedy 접근법 - 백준 16206번 위 문제에 대한 알고리즘은 다음과 같다. 1) 10으로 나누어 떨어지는 케이크부터, 그 중에서도 작은 순으로 커팅을 진행해야한다. (10은 커팅제외) ex) 20이면 1번만 잘라도 2개가 바로 생기는데 50도 나눠떨어지긴 하지만 4번을 잘라야 5개가 생기므로 작은것부터 접근해주어야함. 2) 10으로 나누어떨어지는 케잌들을 다 자르고도 횟수가 남으면 나누어떨어지지 않는 애들도 순차적으로 잘라준다. 처음에는 이런식으로 코드를 짜려고 접근했었다. 이 알고리즘에서 내가 놓쳤던 부분은 다음과 같다. 1) 길이가 10보다 긴 애들로만 크게 그룹지어서 고려해줄 것이 아니라, 그 중에서도(10보다 길이가 길면서도) 10으로 나누어 떨어지고, 그중에서도 길이가 작은 애들부터 잘라주어야 길이가 10인 롤케이크 개수의 최대.. Greedy 접근법 - 백준 20044번 위의 문제에 대해 설정한 알고리즘은 다음과 같다. 1) 우선 학생들의 코딩역량을 오름차순으로 정리한다. 2) 최소값을 최대가 되게 만들어야하므로 1+n, 2+n-1, 3+n-2, 4+n-3... 의 식으로 더해주는 것이 최적의 방법이다. (like 가우스 계산법) 3) 최솟값을 계속해서 업데이트 해주고, 마지막에 최솟값을 출력해준다. 실제 코드는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import java.util.Arrays; import java.util.Scanner; public class project_group { public static void mai.. Greedy 접근법 - 백준 14659번 위 문제에 대해 설정한 알고리즘은 다음과 같다. 기본적으로 왼쪽에서 오른쪽으로만 진행되기 때문에, 만약 기준점으로부터 오른쪽의 봉우리의 높이가 현재의 봉우리보다 낮다면, 그 봉우리의 용은 무조건 최고 활잡이가 될 수 없다. 따라서 오른쪽으로 진행하면서 자신보다 높은 봉우리가 등장했을때만을 고려해주면 된다. 1) 오른쪽으로 진행하면서 (index값을 1씩 증가시켜주면서) 더 높은 봉우리가 나왔을 때 max과 처치한 적의 수를 업데이트해준다. 2) 최고 활잡이를 가리기 위해서는 각각의 max 봉우리들의 적처치수를 비교해야하기 때문에 업데이트 하기 전에, 이전에 처치한 적의 수 중에서 가장 큰 적 처치 수를 result에 저장해둔다. (result는 즉 가장 많이 처치된 적의 수) 3) 마지막 봉우리까지 위의.. Greedy 접근법 - 백준 2847 Greedy접근법의 또 다른 예시문제인 백준 2847번을 풀어봤다. 최소 감소횟수를 구하는 것이기 때문에, 가장 마지막 레벨의 점수를 기준으로 잡고 문제를 풀어갔다. 알고리즘을 다음과 같이 설정하여 접근하였다. 1) 마지막 레벨의 점수를 max로 설정한다. 2) 마지막 레벨부터 처음레벨로 거슬러올라가면서, 순차적으로 감소시켜준다. - 초기 result값을 max-1로 설정 - 단계가 진행됨에 따라 result값을 update 3) 감소가 진행된다면 count(감소횟수를 기록하는 변수)를 update 시켜준다. 실제 코드는 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35.. Greedy 접근법 - 백준 1931번 Greedy 접근법이란 모든 경우(단계)에 대해 최적의 해를 선택하면 그것이 결국 전체의 최적해가 된다는 접근법이다. Greedy 접근법의 대표문제라고 할 수 있는 회의실 배정문제를 풀어보았다. 다음과 같은 문제에서 Greedy 접근법이 성립하는 이유에 대한 증명 - 귀류법을 이용한 증명 cf) 귀류법: 가정을 부정하여 모순을 보임으로써 가정에 대한 결론이 맞음을 보이는 방식 Greedy한 선택이 최적해를 포함하지 않는다고 가정 - 결론 부정 최적해가 존재함은 자명하다. 따라서 그렇다면 Greedy하지 않은 선택이 최적해를 포함할 것이다. 우리가 가정한 최적해의 제일 첫 회의의 끝나는 시간보다 항상 제일 먼저 끝나는 회의의 끝나는 시간이 앞선다. 따라서 그 회의 대신, 제일 먼저 끝나는 회의를 선택하는 .. 이전 1 다음
