문제 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 문제 설명 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다. KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다. 자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 ..

문제 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 설명 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 풀이 방식 해당 문제는 주어진 값을 이용하여 어떠한 값을 최소 횟수로 만들어 내는 것이 관건이다. 10 4790 1 5 10 50 100 500 1000 5000 10000 500..

그리디 알고리즘 (탐욕 알고리즘) 이란? Greedy는 '탐욕스러운, 욕심 많은' 이라는 뜻이다. 그리디 알고리즘은 선택하는 순간마다 당장 최적의 상황만을 선택해 최종적인 해답에 도달하는 방법이다. 그리디 알고리즘은 최적의 해를 구하는 데에 사용되는 근사적인 방법이다. 순간마다 선택하는 답은 그 순간에서는 지역적으로 최적의 답일 순 있지만, 그 선택들을 계속 수집하여 나온 최종적인 답은 최적이 아닐 수 있다. 시간적으로 매우 효율적임. 수학적 증명이 요구되는 사항이 많음. 코딩 테스트의 경우 비슷한 문제나 직관에 의해 판단 할 수 있도록 문제가 주어짐. 그렇기에 많은 문제를 풀어서 감을 익힐 수 있도록 해야함. 예시 루트 노드 7에서 시작해서 10과 12의 대소관계를 파악한다. 더 큰 12를 택한 후 다..