그리디 알고리즘

특정한 공식이 있는 게 아니라서 너무 어려움 => 다른 알고리즘 실버 10문제, 골드 10문제 풀고 다시 돌아오겠음

Q1) BOJ 5585 B2

• 문제: https://www.acmicpc.net/problem/5585

money = int(input())  #구매

coin = 1000 - money  #거스름돈 총액
count = 0  #잔돈 갯수

while coin > 0:  #거슬러 줘야 할 잔액이 0원일 떄까지 돌겠다
  if coin >= 500:
    num = coin // 500
    count += num
    coin -= num * 500
  elif coin >= 100:
    num = coin // 100
    coin -= num * 100
    count += num
  elif coin >= 50:
    num = coin // 50
    coin -= num * 50
    count += num
  elif coin >= 10:
    num = coin // 10
    coin -= num * 10
    count += num
  elif coin >= 5:
    num = coin // 5
    coin -= num * 5
    count += num
  elif coin >= 1:
    num = coin // 1
    coin -= num * 1
    count += num

print(count)

그리디 알고리즘의 핵심 조건

• 매순간 가장 큰 선택(최적의 선택)을 하는 것
• 큰 단위의 동전부터 최대한 많이 사용하는 전략

더 간결한 코드

for c in [500, 100, 50, 10, 5, 1]:
    count += coin // c
    coin %= c

Q2) BOJ 2720 B3

• 문제: https://www.acmicpc.net/problem/2720

T = int(input())  #테스트 케이스 갯수

#쿼터 0.25 -> 25센트
#다임 0.10 -> 10센트
#니켈 0.05 -> 5센트
#페니 0.01 -> 1센트

lst_money = [25, 10, 5, 1]

for i in range(T):  #테스트 케이스 갯수만큼 반복
  sol = []
  C = int(input())
  for i in lst_money:
    C >= i
    num = C // i
    sol.append(num)
    C -= num * i

  print(*sol)

Q3) BOJ 11047 S4

• 문제: https://www.acmicpc.net/problem/11047

N, K = map(int, input().split())
A = []

for _ in range(N):
    A.append(int(input()))

A.sort(reverse=True)
count = 0

for coin in A:
    if K >= coin:
        num = K // coin
        count += num
        K -= num * coin

print(count)

Q4) BOJ 2875 B3

• 문제: https://www.acmicpc.net/problem/2875

N, M, K = map(int, input().split())
#N명의 여학생 M명의 남학생
#k명이 인턴십 프로그램 참여 -> 대회 참여 X

#1. 여학생을 뽀개서 팀을 만든다
team_w = N//2
team = 0 #팀의 수

if team_w > M: #남학생이 부족하면
  team = M
else: #여학생이 부족하면
  team = team_w

# if 잉여 인원 > K -> 팀 뽀개기 X
people = (N - team*2) + (M - team)
if people > K:
  print(team)
  #잉여 인원 < K -> K - 잉여 인원, K//3해서 몫만큼 팀 뽀개기
#K%3 > 0 -> 1팀 뽀개기
else:
  K = K - people
  team = team - (K//3)
  if K % 3 > 0:
    team = team - 1
  print(team)

Q5) BOJ 10610 S4

• 문제: https://www.acmicpc.net/problem/10610

1. 오답

1.1 초기 코드

import random
import math

N = input()
num_N = int(N)
lst_N = []
random_lst = []
random_lst_sol = []
lst_sol = []

fac = math.factorial

for i in N:
  lst_N.append(i)

while len(lst_sol) == math.factorial(num_N):
  random_lst = random.sample(lst_N, len(lst_N))
  radom_lst_sol = map(int, ''.join(random_lst))
  if random_lst_sol not in lst_sol:
    lst_sol.append(random_lst_sol)

if len(lst_sol) == 0:
  print(-1)
else:
  print(max(lst_sol))

1.2 코드의 방향성

• 입력받은 수의 자릿수를 모두 순열로 섞어서, 30의 배수가 되는 수 중 가장 큰 수를 찾으려는 시도
• random.sample()를 이용해서 모든 경우의 수를 탐색하려 함
• 리스트에 담아 최댓값을 출력하려고 함

1.3 문제점

• 시간 복잡도가 O(n)으로, 자릿수가 커지면 실행 불가능
• random.sample()을 써서 중복 없는 순열을 시도 => 하지만 비효율적
• 30 배수의 조건 직접적으로 활용 X
• map(int, ''.join(...))은 결과가 map 객체`이며 비교에 적합 X
• 그리디 알고리즘 접근이 아니라 완전 탐색 느낌으로 접근

2. 정답 도출

2.1 최종 코드

N = input()
lst = list(N)
digit_sum = sum(map(int, lst))

# 1. 30의 배수 조건 확인
if '0' in lst and digit_sum % 3 == 0:
    lst.sort(reverse=True)  # 2. 그리디 정렬: 가장 큰 수 만들기
    print(''.join(lst))
else:
    print(-1)

2.2 풀이 포인트

30의 배수 판별 조건

조건	설명
끝자리 0	→ 자릿수 중 '0'이 포함되어 있어야 함
전체 자릿수 합이 3의 배수	→ sum(자릿수)가 3으로 나누어져야 함

가장 큰 수 만들기

• 조건만 만족하면, 자릿수를 내림차순 정렬해서 이어붙인 수가 정답
• 그리디 전략: 가장 큰 수를 만들기 위한 자릿수 선택 순서

2.3 피드백 정리

항목	오답 시도	개선 방향
접근 방식	순열 완전탐색	수학적 조건 + 정렬 기반 그리디
시간 복잡도	O(n!)	O(n log n)
조건 활용	직접 판별 안 함	'0' 포함 여부 + 자릿수 합 % 3
출력 방식	리스트 풀어서 print(*lst)	''.join(lst)로 하나의 문자열 출력

유니온 파인드

Q6) BOJ 1976 여행 가자 (G4)

• 문제: https://www.acmicpc.net/problem/1976

1. 오답

1.1 내가 생각한 문제 설계

• 도시 N개 -> 그래프의 정점
• 각 도시 간 연결 여부 -> 1: 연결, 0: 연결 X
• 여행 계획에 포함된 도시가 같은 집합 안에 속해 있는지 판별
• 따라서 유니온 파인드로 풀 수 있음

핵심 로직 설계

1. 초기엔 모든 도시가 독립된 집합이라고 가정 => parent[i] = i로 초기화
2. 인접 행렬을 순회하며 i<->j가 연결된 경우 => union(i, j)
3. 최종적으로 여행 경로에 주어진 도시들에 대해:
   • 모든 도시의 find(x) 값이 같다면 ->YES
   • 하나라도 다르면 -> NO

1.2 초기 코드

import sys
sys.setrecursionlimit(10**6)

N = int(input())
M = int(input())
lst_trip = []
lst_union = []

parent = [i for i in range(N+1)]  # 도시 번호: 1부터 N

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
        return parent[x]

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_y] = root_x

for i in range(N):
    lst_union.append(map(int, input().split()))
    for j in range(N):
        if lst_union[i][j] == 1:
            union(i, j)

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

for i in range(1, len(lst_trip)+1):
    for j in range(i+1, len(lst_trip)+1):
        if find(lst_trip[i-1]) != find(lst_trip[j-1]):
            print("NO")
            exit()
        else:
            print("YES")

1.3 문제점 -> 해결 방안

문제	설명	해결 방법
map(int, input().split()) append 이후 리스트처럼 접근 불가	map 객체는 한 번만 순회 가능, 인덱싱 불가	list(map(...))로 바꾸기
lst_union[i][j] 접근 시 에러 발생	위 문제와 연결됨	리스트 형태로 저장 필요
for i in range(1, len+1) 이중 루프	모든 쌍 비교는 필요 없음	모든 도시가 하나의 대표 root를 공유하는지만 확인하면 됨
find 함수에서 return 위치가 잘못됨	재귀 호출 후 return이 안 될 수도 있음	들여쓰기 수정 필요

2. 정답

2.1 최종 코드

import sys
sys.setrecursionlimit(10**6)

N = int(input())
M = int(input())

parent = [i for i in range(N+1)]  # 1-based index

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_y] = root_x

# 인접 행렬 입력
for i in range(1, N+1):  # 1-based
    connection = list(map(int, input().split()))
    for j in range(1, N+1):
        if connection[j-1] == 1:
            union(i, j)

# 여행 계획 입력
trip = list(map(int, input().split()))
root = find(trip[0])  # 첫 도시의 루트를 기준

for city in trip[1:]:
    if find(city) != root:
        print("NO")
        exit()

print("YES")

2.2 틀린 개념 & 몰랐던 부분 정리

개념	설명
map()과 list(map()) 차이	map()은 iterator이므로 한 번 쓰면 사라짐. 리스트처럼 쓰려면 list(map())으로 감싸야 함
union에서 인접 행렬을 순회할 때 i, j에 주의	1부터 시작하는 도시 번호를 쓰기 위해 i와 j에 +1 처리
도시 간 연결 관계는 union(i, j)로 누적해서 적용	결국 같은 그룹이 되도록 병합해야 함
여행 계획 비교는 “모두 같은 루트를 가지는지” 한 번만 검사하면 충분	매 쌍 비교 불필요. 첫 도시 기준 find() 값만 비교

Q7) BOJ 4195 친구 네트워크 (G2)

• 문제: https://www.acmicpc.net/problem/4195

1. 오답

1.1 내가 생각한 문제 설계

• 각 사람(이름)을 정점으로 보기
• 친구 관계가 생기면 두 사람을 같은 집합으로 묶자 -> union(x, y)
• 민혁이는 친구 관계가 생길 때 그 집합에 몇 명 있는지 궁금함
• 따라서 핵심:
  - 문자열 이름을 정수 인덱스로 매핑
  • 각 집합의 크기 관리

1.2 초기 코드

import sys
sys.setrecursionlimit(10**6)

T = int(input()) #테스트 케이스
F = int(input()) #친구 관계의 수

total_f = 1
lst_f = []

parent = [i for i in range(F+1)]

def find(x):
  if parent[x] != x:
    parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
  root_x = find(x)
  root_y = find(y)
  if root_x != root_y
    parent[root_y] = root_x

for i in range(F):
    lst_f.append(i)

for i in range(F):
  if find(lst_f[i][0]) not in lst_f:
    union(i, lst_f[i][0])
    total_f += 1

print(total_f)

1.3 문제점 -> 해결 방안

문제	설명	해결 방안
🔸 문자열 이름 처리 없음	이름이 문자열인데 인덱스를 그대로 쓰려고 함	dict로 이름 → 인덱스 매핑 필요
🔸 집합 크기 추적 없음	집합의 인원 수를 관리하지 않음	size[] 배열로 루트별 크기 관리
🔸 테스트케이스 구분 안 됨	T는 여러 테스트케이스인데 1번만 처리함	테스트케이스 반복 구조 필요
🔸 if root_x != root_y 구문 문법 오류	: 빠짐	문법 수정 필요
🔸 lst_f.append(i) 구조 이상	관계가 저장되지 않음	(name1, name2) 형태로 관계 입력받기 필요

2. 정답

2.1 최종 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    F = int(input())
    parent = dict()
    size = dict()

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x != root_y:
            parent[root_y] = root_x
            size[root_x] += size[root_y]

    for _ in range(F):
        a, b = input().strip().split()

        for name in [a, b]:
            if name not in parent:
                parent[name] = name
                size[name] = 1

        union(a, b)
        print(size[find(a)])

2.2 틀린 개념 & 놓친 포인트 정리

개념	설명
문자열을 인덱스로 직접 쓰면 안 됨	문자열 → 정수 인덱스 or 딕셔너리 매핑 필요
집합 크기 추적은 size[root]로 관리	union할 때 root 기준으로 size 합침
여러 테스트케이스 처리 필요	T개의 TC마다 독립적인 parent, size dict 필요
union 이후 결과는 size[find(x)]로 출력	x와 y는 이제 같은 집합이므로 find(x) 기준으로 size 출력

2.3 요약

개념	설명
문자열을 인덱스로 직접 쓰면 안 됨	문자열 → 정수 인덱스 or 딕셔너리 매핑 필요
집합 크기 추적은 size[root]로 관리	union할 때 root 기준으로 size 합침
여러 테스트케이스 처리 필요	T개의 TC마다 독립적인 parent, size dict 필요
union 이후 결과는 size[find(x)]로 출력	x와 y는 이제 같은 집합이므로 find(x) 기준으로 size 출력

Q8) BOJ 20040 사이클 게임 (G4)

• 문제: https://www.acmicpc.net/problem/20040

1. 오답

1.1 설계

• 플레이어가 차례대로 두 점을 선택해 연결선을 그림 → union(x, y)
• 같은 집합(같은 루트)에 있는 두 점을 연결하면 사이클 발생
• 연결 전에 find(x) == find(y)면 사이클이 생기므로 게임 종료
• 각 차례마다 사이클이 생기지 않았다면 union(x, y) 진행
• 플레이어 차례는 홀짝 구분이지만, 문제 요구는 "몇 번째 차례에서 게임이 종료됐는지"이므로 차례만 인덱스로 세면 됨

1.2 초기 코드

parent = [i for i in range(N+1)]

def find(x):
  if parent[x] != x:
    parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
  root_x = find(x)
  root_y = find(y)
  if root_x != root_y
    parent[root_y] = root_x

N, M = map(int, input().split())

for i in range(M):
  if i % 2 == 0: #짝수 플레이어
    x, y = map(int, input().split())
    if find(x) != find(y):
      union(x, y)
    else:
      print(i//2)
  else: #홀수 플레이어
    x, y = map(int, input().split())
    if find(x) != find(y):
      union(x, y)
    else:
      print(i//2)

1.3 문제점 -> 해결 방안

문제	설명	해결 방법
❌ N 선언 전에 parent 리스트 생성	변수 참조 순서 오류	N과 M 먼저 입력받고 초기화해야 함
❌ union 함수에서 : 누락	문법 에러	if root_x != root_y:로 수정
❌ 플레이어 홀/짝 조건은 필요 없음	출력은 “몇 번째 차례” (0부터 시작)	i만 출력하면 됨, i//2 아님
❌ 사이클 생긴 이후에도 계속 진행	게임은 즉시 종료해야 함	exit() 또는 break 필요
❌ 사이클이 안 생겼을 경우 출력 없음	문제 요구는 "사이클이 안 생기면 0" 출력	루프 종료 후 print(0) 추가 필요

2. 정답

2.1 최종 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M = map(int, input().split())
parent = [i for i in range(N)]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_y] = root_x
        return False  # 사이클 없음
    else:
        return True  # 사이클 발생

for i in range(M):
    x, y = map(int, input().split())
    if union(x, y):  # 사이클 생김
        print(i + 1)  # 0-based → +1차례 출력
        exit()

print(0)

2.2 틀린 개념 & 몰랐던 부분 정리

개념	설명
유니온 파인드에서 사이클 판별	find(x) == find(y) → 사이클 발생
차례 번호 출력	0-based 인덱스 그대로 출력 (홀짝 무관)
즉시 종료 처리	exit() 또는 break로 첫 사이클 발생 시 종료
초기 입력 순서	N, M을 먼저 받아야 parent 초기화 가능
게임이 끝나지 않는 경우	출력은 0이어야 함

2.3 요약

포인트	설명
union 전에 find(x) == find(y)인지 확인	이미 연결된 집합이면 사이클 발생
사이클 발생 시점 = 종료 시점	그때 차례 번호 출력
사이클 없으면 0 출력	게임이 끝나지 않은 경우