그리디 알고리즘이란?
그리디 알고리즘은 탐욕법이라고 불리며 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없는 경우가 많다.
따라서 그리디 해법은 그 정당성 분석이 중요하다.
다시 말해서, 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해가 되는 지를 검토한다.
그리디 알고리즘 문제
1. 거스름 돈
거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다.
손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수는?
단, N은 항상 10의 배수이다.
Key Point)
가장 큰 화폐 단위부터 거슬러 주면 된다!
정당성 분석)
가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
price = int(input())
answer = 0
# 큰 단위의 화폐부터 입력
array = [500, 100, 50, 10]
for coin in array:
answer += price // coin # 해당 화폐로 최대한 거슬러 줄 수 있는 동전의 개수
price %= coin # 거슬러 주고 남은 가격
print(answer)ex) 만약 800원을 거슬러 줘야하는데 화폐 단위가 500원, 400원, 100원이라면?
큰 화폐 단위 부터 거슬러 주면 500원 1개, 100원 3개로 4개가 된다.
하지만 이 경우, 400원 2개로 800원을 만들 수 있으므로 그리디로 해결할 수 없다.
즉, 그리디 알고리즘에서는 항상 정당성 분석을 검토해야 한다.
2. 1이 될 때까지
어떠한 수 N이 1이 될 때까지 다음 두 과정 중 하나를 반복적으로 수행한다.
단, 두 번쨰 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.
1. N에서 1을 뺀다.
2. N을 K로 나눈다.
(1 <= N <= 100,00, 2 <= K <= 100,00)
Key Point)
최대한 많이 나누기를 수행하면 된다!
정당성 분석)
K가 2 이상의 수라면 N을 K로 나누는 작업이 N에서 1을 빼는 작업보다 수를 줄이는데 효과적이다.
# 공백을 기준으로 입력 받기
n, k = map(int, input().split())
count = 0
while True:
# n이 1이 되는 순간 탈출
if n == 1:
break
# n이 K로 나누어 떨어지는 경우, 나눈다.
if n % k == 0:
n //= k
count += 1
# 아닌 경우, 1을 빼준다.
else:
n -= 1
count += 1
print(count)위의 코드는 n에서 1을 빼는 경우가 반복될 수 있다.
하지만 아래 코드에서는 target = (n//k) * k을 통해 나누어 떨어지는 수를 구해서
n - target을 통해 1을 몇 번 빼야하는지 구할 수 있으므로 시간을 단축할 수 있다.
# 공백을 기준으로 입력 받기
n, k = map(int, input().split())
count = 0
while True:
# N이 K로 나누어 떨어지는 수가 될 때를 구할 수 있다.
target = (n//k) * k
# 1을 몇 번 빼야 나누어 떨어지는 수가 되는지를 더해준다.
count += (n - target)
n = target
# N이 K보다 작을 때 (더 이상 나눌 수 없을 때), 탈출
if n < k:
break
# K로 나누고 횟수 증가
count += 1
n //= k
# 탈출하기 전에 count += (n - target)에 의해 1을 더했으므로
count -= 1
print(count)3. 곱하기 혹은 더하기
각 자리가 숫자로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 "x" 혹은 "+" 연산자를 넣어서 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하라.
단, 연산 방식은 일반적인 방식과 달리 무조건 왼쪽에서부터 순서대로 이루어진다.
Key Point)
두 수 중 하나라도 0이거나 1인 경우 더하기 연산을, 나머지는 곱하기 연산을 한다.
정당성 분석)
둘 중 하나라도 0인 경우는 아래와 같다.
곱하기 연산 : 0 x a = a x 0 = 0
더하기 연산 : 0 + a = a + 0 = a
둘 중 하나라도 1인 경우는 아래와 같다.
곱하기 연산 : 1 x a = a x 1 = a
더하기 연산 : 1 + a = a + 1
s = str(input())
# 첫 번째 문자를 숫자로 대입
answer = int(s[0])
# 두 번째 문자부터 비교
for num in s[1:len(s)]:
# 두 수 중 하나라도 0이거나 1인 경우, 더하기 연산
if int(num) <= 1 or answer <= 1:
answer += int(num)
# 나머지 경우, 곱하기 연산
else:
answer *= int(num)
print(answer)4. 모험가 길드
공포도가 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야 모험을 떠날 수 있도록 법이 규정되었다.
N명의 모험가들에 대한 정보가 주어졌을 때,
여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하라.
Key Point)
현재 그룹에 포함된 모험가의 수 >= 현재 확인하고 있는 공포도 => 같은 그룹
정당성 분석)
5
2 3 1 2 2
오름차순 정렬을 한다면 1 2 2 2 3이다.
첫 번째 경우는 현재 그룹에 한 명, 공포도 1이므로 혼자서 그룹 A가 된다.
두 번째 경우는 현재 그룹에 한 명, 공포도 2이므로 다음으로 넘어간다.
세 번째 경우는 현재 그룹에 두 명, 공포도 2이므로 둘이서 그룹 B가 된다.
네 번째 경우는 현재 그룹에 한 명, 공포도 2이므로 다음으로 넘어간다.
다섯 번째 경우는 현재 그룹에 두 명, 공포도 3이므로 다음으로 넘어간다.
이후 종료되므로 그룹의 최대 수는 2그룹이 된다.
n = int(input())
data = list(map(int, input().split()))
data.sort() # 오름차순 정렬
answer = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가 수
for i in data:
count += 1 # 현재 그룹 수 증가
# 현재 그룹 수가 공포도보다 크거가 같다면
if count >= i:
answer += 1 # 총 그룹 증가
count = 0 # 현재 그룹 초기화
print(answer)
구현 문제란?
풀이를 떠올리는 것은 쉽지만 소스 코드로 만들기 어려운 문제를 지칭한다.
- 알고리즘은 간단한데 코드가 지나치게 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리하는 문제 (파이썬 특화)
- 적절한 라이브러리를 활용해야 하는 문제
구현 문제
행렬 (2차원 배열)
1. 상하좌우
A는 N x N 크기의 정사각형 공간 위에 서있다.
이 공간은 1 x 1의 정사각형으로 나누어져 있다.
A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다.
L : 왼쪽으로 한 칸
R : 오른쪽으로 한 칸
U : 위쪽으로 한 칸
D : 아래쪽으로 한 칸
이 때, N x N 크기의 정사각형 범위를 벗어나는 행위는 무시된다.
(1 <= N <= 100, 1 <= 이동 횟수 <= 100)
Key Point)
요구사항대로 충실히 구현하면 되는 문제로써 시뮬레이션 유형이다.
# 이동 횟수
n = int(input())
# 이동 계획 리스트
data = list(map(str, input().split()))
# 초기 위치
x = 1
y = 1
for direction in data:
# L이면서 1이 아닐 때
if direction == 'L' and y != 1:
y -= 1
# R이면서 n-1이 아닐 때
elif direction == 'R' and y != (n - 1):
y += 1
# U이면서 1이 아닐 때
elif direction == 'U' and x != 1:
x -= 1
# R이면서 n-1이 아닐 때
elif direction == 'D' and x != (n - 1):
x += 1
print(x, y)
예시 답안
# N 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()
# L, R, U, D에 따른 이동 방향
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)2. 시각
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하라.
Key Point)
이 문제의 시간 복잡도를 계산하면 60 x 60 x 60 = 86400으로 완전 탐색이 가능한 문제로써 모든 경우의 수에 대해서 3이 포함되는지 판단하면 된다.
파이썬의 경우 1초에 2000천만번 정도의 연산이 가능하다!
n = int(input())
count = 0
for clock in range(n+1):
for min in range(60):
for sec in range(60):
if '3' in str(clock) + str(min) + str(sec):
count += 1
print(count)내 풀이의 경우, '시'에 3이 포함되는 경우 3600을 더하고 '분'에 3이 포함되는 경우 60을 더하는 방식으로 계산량을 줄였다.
n = int(input())
count = 0
for clock in range(n+1):
if '3' in str(clock):
count += 3600
continue
for min in range(60):
if '3' in str(min):
count += 60
continue
for sec in range(60):
if '3' in str(min):
count += 1
print(count)3. 왕실의 나이트
체스판은 8 x 8 좌표 평면이다.
나이트는 이동할 때 L자의 형태로만 이동이 가능하며 체스판을 벗어날 수 없다.
나이트의 이동 방식은 2가지이다.
1. 수평으로 두 칸 이동 후 수직으로 한 칸
2. 수직으로 두 칸 이동 후 수직으로 한 칸
나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하라.
Key Point)
나이트의 이동 가능 거리를 미리 입력한 후 1 ~ 8 사이에 위치하는지 판단.
알파벳의 경우, 정수형으로 변환을 해줘야 한다.
# 위치 입력
position = str(input())
# 아스키 코드로 바꾸어서 계산
x = int(ord(position[0]) - int(ord('a'))) + 1
# y는 정수형으로 형변환
y = int(position[1])
# 나이트의 8가지 이동 가능 거리
steps = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
count = 0
for step in steps:
# 해당 위치로 이동이 가능하다면 경우의 수 증가
if 0 < step[0] + x < 8 and 0 < step[1] + y < 8:
count += 1
print(count)ord('a')를 넣으면 정수 97을 반환합니다.
chr(97)을 하면 문자 'a'를 반환합니다.
나는 8가지 알파벳 밖에 없어서 직접 숫자로 변환해줬다.
# 위치 입력
position = str(input())
# x는 알파벳을 숫자로 변환
x = 0
alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
for i in range(len(alphabet)):
if position[0] == alphabet[i]:
x = i + 1
# y는 정수형으로 형변환
y = int(position[1])
# 나이트의 8가지 이동 가능 거리
steps = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
count = 0
for step in steps:
# 해당 위치로 이동이 가능하다면 경우의 수 증가
if 0 < step[0] + x < 8 and 0 < step[1] + y < 8:
count += 1
print(count)4. 문자열 재정렬
알파벳 대문자와 숫자로만 구성된 문자열이 입력된다.
알파벳을 오름차순으로 정렬하여 출력한 후, 모든 숫자를 더한 값을 출력하라.
(1 <= 문자열의 길이 <= 10,000)
아래는 내가 작성한 코드이다.
숫자인지 판별하기 위한 리스트를 만들어서 숫자들을 더해주고
알파벳들은 따로 리스트에 모아 오름차순 정렬한 후 정답 문자열에 붙여주었다.
strings = str(input())
# 숫자인지 판단하지 위한 리스트
num = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
sum = 0 # 숫자들의 합
answer = '' # 정답 문자열
string = [] # 문자열 추출 리스트
for s in strings:
# 숫자라면 sum에 더한다.
if s in num:
sum += int(s)
# 알파벳이라면 리스트에 추가한다.
else :
string += s
# 문자열을 오름차순 정렬한다.
string = sorted(string)
# 문자열 리스트를 정답 문자열에 추가한다.
for s in string:
answer += s
# sum이 0이 아니라면 맨 뒤에 sum도 추가한다.
if sum != 0:
answer += str(sum)
print(answer)아래 코드는 예시 답안으로
1. isalpha()함수를 통해 알파벳을 판별하고
2. print(''. join(result))를 사용하여 리스트를 문자열로 바로 변환하였다.
data = input()
result = []
sum = 0
# 문자를 하나씩 확인하며
for x in data:
# 알파벳인 경우 결과 리스트에 삽입
if x.isalpha():
result.append(x)
# 숫자는 따로 더하기
else:
sum += int(x)
# 알파벳을 오름차순으로 정렬
result.sort()
# 숫자가 하나라도 존재하는 경우 가장 뒤에 삽입
if sum != 0:
result.append(str(sum))
# 최종 결과 출력 (리스트를 문자열로 변환하여 출력)
print(''. join(result))참고 자료
이코테 2021 강의 2편
이것이 코딩 테스트다 교재
