[코딩테스트]Chapter 3. 그리디 - 실전문제

수정중

그리디 알고리즘

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

• 그리디 알고리즘 유형은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

• 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 "가장 큰 순서대로", "가장 작은 순서대로" 처럼 기준을 제시

• 정렬 알고리즘과 짝을 이뤄 출제

• 그리디 알고리즘을 모든 문제에 적용할 수 있는 것은 아님 / 문제의 해법을 찾았을 때, 그 해법이 정당한지 검토 필요

문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

실전문제2. 큰 수의 법칙

# 나의 풀이
n, m, k = map(int, input().split())
num_list = list(map(int, input().split()))

num_list.sort()

first = num_list[-1]
second = num_list[-2]

result = 0
temp = k

for i in range(m):
    if temp == 0:
        result += second
        temp = k
        continue
    
    result += first
    temp -= 1

print(result)


# 예시 답안
first_multi = m // k
second_multi = m % k

result2 = first * k * first_multi + second * second_multi

print(result2)

나의 풀이.. 매우 비효율적이다!!!

실전문제 3. 숫자 카드 게임

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

min_list = []

for i in range(n):
    row = list(map(int, input().split()))
    min_list.append(min(row))

print(max(min_list))

각 열에서 최솟값을 모아놓은 리스트를 만든 후 그 리스트에서 최댓값을 찾도록 하였다.

실전문제 4. 1이 될 때까지

# 나의 풀이
n, k = map(int, input().split())

n1 = n
k1 = k

count = 0

while n > 1:
    if n % k == 0:
        n //= k
        count += 1

    else:
        n -= 1
        count += 1

print(count)


# 예시 답안 
result = 0

while n1 > k1:
    # k의 배수가 되기 전까지 한 번에 빼기
    target = (n1 // k1) * k  # 가장 가까운 k의 배수
    result += (n1 - target)  # target이 될 때까지 1씩 빼주는 계산 횟수
    n1 = target  # k의 배수인 n이 됨

    n1 //= k1  # n을 k로 나눈 몫
    result += 1  # 연산 횟수 더함

# n은 1보다 크거나 같고 k보다 작은 수 >> 1이 될 때까지 1씩 빼야함
result += (n1 - 1)

print(result)

예시 답안과 같은 방식으로 빼기를 한 번에 처리할 생각은 못했다.
이런 방법이..!!!