2강. 그리디 & 구현

📌 그리디 알고리즘이란?

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

• 문제를 풀기 위한 최소한의 아이디어를 떠올리는 능력이 필요하다.
• 정당성 분석이 중요 — 단순히 가장 좋아 보이는 선택을 반복해도 최적의 해가 나오는지 검토해야 한다.
• 일반적인 상황에서는 최적의 해를 보장할 수 없는 경우가 많다.
• 단, 코딩 테스트에서는 탐욕법으로 얻은 해가 최적의 해가 되는 상황으로 출제된다.

---

🪙 문제 1. 거스름돈

아이디어

큰 단위의 화폐부터 최대한 사용하면 항상 최소 동전 개수를 보장한다.

n = 1260
count = 0

array = [500, 100, 50, 10]

for coin in array:
    count += n // coin  # 해당 화폐로 거슬러 줄 수 있는 동전의 개수
    n %= coin

print(count)

시간 복잡도

• 화폐의 종류가 K개일 때 O(K)
• 거슬러줘야 하는 금액과 무관하고, 동전의 종류 수에만 영향을 받는다.

---

🔢 문제 2. 1이 될 때까지

문제

N과 K가 주어졌을 때, N에서 1을 빼거나 K로 나누는 연산을 반복해 1로 만드는 최소 연산 횟수를 구하라.

아이디어

• K로 나누는 것이 1을 빼는 것보다 훨씬 빠르게 N을 줄인다.
• 따라서 최대한 많이 나누기를 수행하는 것이 최적이다.
• K로 나누어 떨어지지 않을 때는 나누어 떨어지는 수까지 1씩 뺀다.

정당성

K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄인다. N은 항상 1에 도달하게 된다.

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

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n // k) * k  # K의 배수 중 N보다 작거나 같은 가장 큰 수
    result += (n - target)
    n = target

    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break

    # K로 나누기
    result += 1
    n //= k

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

핵심 포인트

target = (n // k) * k → K로 나누어 떨어지는 가장 가까운 수를 한 번에 계산해, 1씩 빼는 횟수를 줄인다.

---

✖️ 문제 3. 곱하기 혹은 더하기

문제

숫자로 이루어진 문자열이 주어졌을 때, 각 숫자 사이에 + 또는 ×를 넣어 결과값을 최대로 만들어라.

아이디어

• 대부분의 경우 +보다 ×가 더 값을 크게 만든다. (ex. 5+6=11, 5×6=30)
• 단, 두 수 중 하나라도 0 또는 1이면 더하기가 유리하다.

케이스	더하기	곱하기	선택
5, 6	11	30	✅ 곱하기
0, 6	6	0	✅ 더하기
1, 6	7	6	✅ 더하기

data = input()

result = int(data[0])

for i in range(1, len(data)):
    num = int(data[i])
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)

---

🧙 문제 4. 모험가 길드

문제

공포도가 X인 모험가는 반드시 X명 이상으로 구성된 그룹에 참여해야 한다. 최대 몇 개의 그룹을 만들 수 있는지 구하라.

아이디어

• 그룹 수를 최대화하려면 각 그룹을 최대한 작게 만들어야 한다.
• 오름차순 정렬 후 공포도가 낮은 모험가부터 확인한다.
• 현재 그룹 인원 수 ≥ 현재 모험가의 공포도가 되는 순간 그룹을 결성한다.

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0  # 총 그룹의 수
count = 0   # 현재 그룹에 포함된 모험가의 수

for i in data:
    count += 1
    if count >= i:  # 현재 그룹 인원이 공포도 이상이면 그룹 결성
        result += 1
        count = 0

print(result)

핵심 포인트

오름차순 정렬 덕분에 현재 i가 그룹 내 최대 공포도임이 보장된다. 따라서 count >= i 조건 하나로 그룹 결성 가능 여부를 판단할 수 있다.

---

📌 구현(Implementation)이란?

풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제

• 코드가 지나치게 길어지는 문제
• 실수 연산 및 특정 소수점 자리 출력 문제
• 문자열을 특정 기준으로 끊어 처리하는 문제
• 적절한 라이브러리를 찾아 사용해야 하는 문제

💡 시뮬레이션 및 완전 탐색 문제에서는 2차원 방향 벡터가 자주 활용된다.

# 상하좌우 방향 벡터
dx = [0, 0, -1, 1]   # 행 변화량 (L, R, U, D)
dy = [-1, 1, 0, 0]   # 열 변화량

---

🗺️ 문제 5. 상하좌우

문제

N×N 격자에서 (1,1)부터 시작해 L/R/U/D 명령어를 따라 이동할 때, 격자를 벗어나는 이동은 무시한다. 최종 위치를 구하라.

아이디어

요구사항대로 구현하는 시뮬레이션 문제. 방향 벡터를 리스트로 정의해 이동을 처리한다.

n = int(input())
x, y = 1, 1
plans = input().split()

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

for plan in plans:
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    x, y = nx, ny

print(x, y)

---

⏰ 문제 6. 시각

문제

00:00:00부터 N:59:59까지의 모든 시각 중 숫자 3이 하나라도 포함된 경우의 수를 구하라.

아이디어

하루는 86,400초. 모든 경우의 수를 직접 탐색하는 완전 탐색 문제.

h = int(input())

count = 0
for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

핵심 포인트

'3' in str(i) + str(j) + str(k) → 시/분/초를 문자열로 합쳐서 '3'이 포함되는지 한 번에 확인한다.

---

♞ 문제 7. 왕실의 나이트

문제

8×8 체스판에서 나이트의 위치가 주어졌을 때, 이동 가능한 경우의 수를 구하라. 나이트는 L자로만 이동한다.

아이디어

나이트의 8가지 이동 방향을 모두 시도하고, 체스판을 벗어나지 않는 경우만 카운트한다.

input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 나이트의 8가지 이동 방향
steps = [(-2,-1), (-1,-2), (1,-2), (2,-1),
         (2,1), (1,2), (-1,2), (-2,1)]

result = 0
for step in steps:
    next_row = row + step[0]
    next_column = column + step[1]
    if 1 <= next_row <= 8 and 1 <= next_column <= 8:
        result += 1

print(result)

핵심 포인트

ord(input_data[0]) - ord('a') + 1 → 알파벳 열 좌표를 숫자로 변환한다. (a→1, b→2, ...)

---

🔤 문제 8. 문자열 재정렬

문제

알파벳 대문자와 숫자로 구성된 문자열이 주어졌을 때, 알파벳은 오름차순 정렬, 숫자는 모두 더해서 뒤에 붙여 출력하라.

• 예시: K1KA5CB7 → ABCKK13

아이디어

문자를 하나씩 확인하며 알파벳과 숫자를 분리한 뒤, 알파벳은 정렬하고 숫자 합계를 뒤에 붙인다.

data = input()
result = []
value = 0

for x in data:
    if x.isalpha():
        result.append(x)
    else:
        value += int(x)

result.sort()

if value != 0:
    result.append(str(value))

print(''.join(result))

---

📝 정리

유형	핵심 전략
그리디	현재 최선의 선택 반복 + 정당성 검토 필수
시뮬레이션	요구사항 그대로 구현, 방향 벡터 활용
완전 탐색	가능한 모든 경우 탐색 (경우의 수가 적을 때)