결국 빛나리라

https://www.acmicpc.net/problem/11047 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 > 그리디 알고리즘 가장 큰 단위의 동전가치부터 순회하면서 동전의 가치가 입력받은 k보다 작은 숫자이면 해당 동전으로 k의 가치를 차감할 수 있다는 뜻이다. 따라서 해당 가치로 k를 나눈 몫(몇 번 사용할 수 있는지 그 횟수를 나타냄)을 result에 더해주고 나머지 동전의 가치로 k값을 갱신시킨다. 여기서 중요한 점은 필요한 동전의..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 본 포스팅에서 작성한 코드문제는 해당 저서에 나와있는 문제 일부입니다. https://westshine-data-analysis.tistory.com/30 그리디 알고리즘 (1) / 그리디 알고리즘이란 나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다 ▷그리디 알고리즘이란? 탐욕법으로 번역되는 해당 알고리즘은 현재 주어진 상황에서 가장 좋은 것만 고르는 방 westshine-data-analysis.tistory.com ▷ 동빈이의 큰 수의 법칙 1. 아이디어: 가장 큰 수를 M//K * K만큼 더할 수 있다. 그 외 남은 나머지 횟수만큼은 두번째로 큰수로 더한다. 만약 배열에 가장 큰 수가 중복..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다 ▷그리디 알고리즘이란? 탐욕법으로 번역되는 해당 알고리즘은 현재 주어진 상황에서 가장 좋은 것만 고르는 방법이다. 문제를 보고 해당 문제를 풀 수 있는 아이디어를 떠올리는 것이 중요하다. 코테에서 많이 출제되는 유형이지만 아이디어를 생각하는 것이 중요하기 때문에 사전에 알고리즘을 외우지않아도 충분히 풀 수 있는 문제유형이다. 아이디어를 떠올린 후에는 가장 좋아보이는 걸 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야한다. ▷ 그리디 알고리즘 풀이법 즉 그리디 알고리즘은, 1. 최소한의 아이디어를 생각해내고, 2. 아이디어의 정당성을 분석해야한다. 다른 말로 내가 생각해낸 아이디어로 해를 구하고자 할때 최적의 해를 항상..