그리디 알고리즘

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.

그리디 해법은 그 정당성 분석이 중요합니다.

           단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

 

5-7-9가 가장 큰 값을 가집니다. 하지만 그리드 알고리즘을 사용하면 5-10-4를 선택 됩니다.

 

문제 1이 될 때까지

 

어떠한 수 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, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    target = (n // k) * k #k로 나눈 몫에다 k를 곱하여 target을 k로 나눌 수 있는 값으로 만든다.
    result += (n - target) # 1을 빼는 연산 횟수
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

 

문제

여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임

단, 게임의 룰을 지키며 뽑아야함

 

1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하고, M은 열의 개수를 의미

2. 먼저 뽑고자 하는 카드가 포함된 행을 선택

3. 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑음

4. 처음에 카드를 골라낼 행을 선택할 때, 이후 해당 행에서 가장 숫자가 낮은 카드를 뽑아야 하는 것을 고려해 가장 높은 숫자를 뽑을 수 있도록 해야함

 

입력 조건

첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어짐

(1 <= N, M <= 100)

둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어짐 각 숫자는 1이상 10000이하의 자연수

 

출력 조건

첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력

입출력 예

입력	출력
3 3 3 1 2 4 1 4 2 2 2	2
2 4 7 3 1 8 3 3 3 4	3

문제 해설

각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것이다.

 

n, m = map(int, input().split())

result = 0
for i in range(n):
	data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = min(data)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)
    
   print(result) # 최종 답안 출력