Greedy Algorithm
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 정당성이 중요하다. (항상 최적의 해를 갖지 않기 때문)
대표적인 문제 1 : 거스름 돈
문제
1260원을 500원, 100원, 50원, 10원으로 거슬러줄 때 최소한의 개수
Solution
n = 1260
count - 0
array = [500, 100, 50, 10]
for coin in array:
count += n // coin
n %= coin
print(n)참고
- 화폐의 종류에서 각각의 화폐가 이전 화폐의 배수라서 그리디 알고리즘이 가능
- 500 400 100 이렇게 있을 경우 DP를 활용해야 한다.
- 시간복잡도 : O(n) n은 동전 종류의 개수
대표적인 문제 2 : 1이 될 때까지
문제
어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행한다. 단, 두 번째 연산은 N이 K로 나누어 떨어 질 때만 선택할 수 있습니다.
1. N에서 1을 뺍니다.
2. N을 K로 나눕니다.
Solution
n, k = map(int, input.split())
result = 0
while True:
target = (n//k) * k
result += (n - target)
n = target
if n < k:
break
result += 1
n//= k
result += (n - 1)
print(result)
대표적인 문제 3 : 곱하기 더하기
문제
각 자리가 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x'혹은 '+'연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.
Solution
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)구현
- 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
- 구현 유혀으이 예시
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
- 좌표를 사용하는 경우 행렬을 사용, 방향 벡터가 자주 활용
대표적인 문제 1 : 시각
문제
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요
Solution
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)대표적인 문제 2 : 상하좌우
문제
여행가 A는 N x N 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당합니다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있습니다.
Solution
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)참고
- 시뮬레이션 유형으로 분류
- 요구사항대로 구현하면 되는 문제
대표적인 문제 3 : 문자열 재정렬
문제
알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.
Solution
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))