greedy algorithm

※"이것이 코딩 테스트다"의 저자인 나동빈 님의 유튜브 강의를 보고 학습을 위해 정리한 글입니다. 예제 어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. N에서 1을 뺀다. N을 K로 나눈다. 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이경우 전체과정을 실행한 횟수는 3이된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오 입력조건 - 첫째줄에 N(2

※"이것이 코딩 테스트다"의 저자인 나동빈 님의 유튜브 강의를 보고 학습을 위해 정리한 글입니다. 개요 그리디 알고리즘을 쉽게 생각해보면 현재 상황에서 가장 좋은 것만 고르는 방법을 뜻한다. 그리디 알고리즘의 정의는 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식이다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다고 한다. 그렇지만 코딩 테스트에서의 대부분의 그리디 문제는 그리디 알고리즘으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제된다고 한다. - 동빈 나- 예제 그리디 알고리즘의 대표적인 예시로는 거스름돈 예제가 있다. 당신은 음식점에서 계산을..