그리디
그리디 1-4) 1이 될 때까지
문제 어떠한 수 N이 1이 될 때까지 아래 두 과정중 하나를 반복적으로 수행한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. N에서 1을 뺀다. N을 K로 나눈다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오. 입력조건 첫째 줄에 N과 K가 공백으로 구분되며 각각 자연수로 주어진다. 이 때 입력으로 주어지는 N은 항상 K보다 크거나 같다. 출력조건 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 횟수의 최솟값을 출력한다. 문제해설 주어진 N에 대하여 '최대한 많이 나누기'를 수행하면 된다. 왜냐하면 어떠한 수가 있을 때, '2 이상의 수로 나누는 것'이 '1을 빼는 것'보다 숫자를 ..
그리디 1-3) 숫자 카드 게임
문제 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 입력 조건 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1이..
그리디 1-2) 큰 수의 법칙
실전 1. 큰수의 법칙 문제 해설 이 문제를 해결하려면 일단 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다. # 큰수의 법칙 def maxNum(n, m, k, listNum): result = 0 listNum.sort() max1 = listNum[-1] max2 = listNum[-2] q = 1 while True: if m == 0: break maxN = max(listNum) for t in range(k): if m == 0: break print(max1) result += max1 m -= 1 print(max2) result += max2 m -= 1 return result print(maxNum(5,8,3,[2,4,5,4,6])) 이 문제는 반복되는 수열에 대해서 ..
그리디 1-1) 거스름돈
예제1) 거스름돈 문제 해설 이 문제의 핵심은 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 방법으로 해결할 수 있다. #코드 작성 def exch(money): change = [500, 100, 50, 10] result = [] for i in change: result.append(money // i) money = money % i return result exch(1260) 코드를 보면 화폐의 종류만큼 반복을 수행해야한다. 따라서 종류가 K개라고 할 때 위 소스코드의 시간복잡도는 O(K)이다. 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다는 것을 알 수 있다.
1주차 - 그리디 이론
정의 ‘탐욕스러운’ 혹은 ‘욕심 많은’을 뜻하는 알고리즘으로 선택의 순간마다 바로 눈앞에 보이는 이익만을 좇는 알고리즘을 뜻합니다. 즉, 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법을 말합니다. 결정을 내리는 순간마다 가장 최선의 선택을 통해 전체적인 최적의 해결책을 찾아내고자 하는 노력에서 비롯되었습니다. 각 단계에서의 최선의 선택이 결국 전체적인 최적의 해결책을 제공해주는 경우가 많습니다. 동적 프로그래밍을 사용하게 되면 중복되는 하위 문제를 다루게 되는데 이것이 많은 연산량과 계산 복잡도가 커지게 한다는 한계점을 가지고 있습니다. 이러한 점에 착안하여 고안된 알고리즘입니다. (동적 프로그래밍을 대체하는 것이 아닌 서로 보완하는 개념입니다) 특징 대부분의 경우 계산 속도가 빠르므로 매우 실용적..