[이것이 취업을 위한 코딩 테스트다 with 파이썬] Ch3. 그리디 알고리즘

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법

 

실전문제 1- 큰 수의 법칙

주어진 수들을 M번 더 해서 가장 큰 수 만들기 (특정 인덱스에 해당하는 수가 연속해서 K번 초과 X)

## 내가 작성한 코드
N,M,K = map(int, input().split())

numbers=list(map(int, input().split()))

numbers.sort(reverse=True)

cnt = 0
result = 0

if numbers[0]==numbers[1]:
    while cnt < M:
        result+=numbers[0]
        cnt+=1

else:
    while cnt < M:
        for _ in range(K):
            result += numbers[0]
            cnt+=1
            if cnt == M: break
        result+=numbers[1]
        cnt+=1

print(result)

답안 예시

## 해답
# N, M, K를 공백을 기준으로 구분하여 입력 받기
n, m, k = map(int, input().split())
# N개의 수를 공백을 기준으로 구분하여 입력 받기
data = list(map(int, input().split()))

data.sort() # 입력 받은 수들 정렬하기
first = data[n - 1] # 가장 큰 수
second = data[n - 2] # 두 번째로 큰 수

result = 0

while True:
	for i in range(k):
    	if m == 0:
        	break
        result += first
        m-=1
    if m == 0:
    	break
    result += second
    m -= 1

print(result) # 최종 답안 출력

 

실전 2- 숫자 카드 게임

NXM 카드들 중에 가장 높은 숫자 카드 한장 뽑기 (행을 선택하고 선택된 행에서 가장 숫자가 낮은 카드 뽑아야 한다)

## 내가 작성한 코드
N, M = map(int, input().split())

cards=[]
for _ in range(N):
    cards.append(list(map(int, input().split())))

result=0
for row in cards:
    if min(row) > result:
        result = min(row)

print(result)

답안 예시

## 해답
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)

 

실전 3- 1이 될 때까지

N이 1이 될 때까지 최소 과정 횟수 구하기 (과정1. N에서 1을 뺀다, 과정2. N을 K로 나누어질때 N을 K로 나눈다) 

## 내가 작성한 코드
N, K = map(int, input().split())

cnt=0
while N != 1:
    if N % K:
        N-=1
    else:
        N/=K
    cnt+=1
    
print(cnt)

답안 예시

## 해답
# N, K을 공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())
result = 0

// N이 K 이상이라면 K로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1

# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
    n -= 1
    result += 1

print(result)