그리디

[이것이 코딩 테스트다 with Python ] 그리디 : 큰 수의 법칙

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 3 그리디 실전문제 3-2 큰 수의 법칙 92p 문제 여기서 큰 수의 법칙이란 다양한 수로 이뤄진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과할 수는 없음 입력 조건 첫째 줄에 N (2 ≤ N ≤ 1,000) , M (1 ≤ M ≤ 10,000) , K(1 ≤ K ≤ 10,000) 의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 둘 째줄에 N개의 자연수가 주어집니다. 각 자연수는 공백으로 구분합니다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어집니다. 입력으로 주어지는 K는 항상 M보다 작거나 같습니다. 출력 조건 첫째줄에 큰..

[이것이 코딩 테스트다 with Python] 그리디 : 1이 될 때까지

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 3 그리디 실전문제 3-4 1이 될 때까지 99p 문제 어떠한 수 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번의 과정을 수행해야 하는 최소 횟수를 구하는 프로..

[이것이 코딩 테스트다 with Python] 그리디 : 숫자 카드 게임

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 3 그리디 실전문제 3-3 숫자 카드 게임 96p 문제 설명 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임 단, 게임의 룰을 지키며 뽑아야함 숫자가 쓰인 카드들이 N X M 형태로 놓여 있습니다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미합니다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 합니다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 입력 조건 첫째 줄에 숫자 카드들이 놓인..

[프로그래머스/탐욕법 Greedy] 체육복 - Level 1

코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체..