그리디 알고리즘
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 일반적으로 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구
★ 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.
즉, 그리디 알고리즘으로 최적의 해가 나오는 상황에서만 사용해야 한다.
그리디 알고리즘 예시
1. 거스름 돈 문제
# 거스름 돈 문제
# 거스름 돈을 500 , 100 , 50 , 10 원으로 줄 때 각 동전의 갯수
money_list = [500, 100, 50, 10]
change = int(input())
result = [0, 0, 0, 0]
for i in range(len(money_list)):
result[i] = (change // money_list[i])
change %= money_list[i]
for i in range(len(result)):
print(money_list[i], ' = ', result[i], '개')
2. 곱하기 Or 더하기
# 곱하기 혹은 더하기 알고리즘 문제
# 02984 와 유사한 형태로 문자열 S가 주어지면 왼쪽부터 차례대로 더하거나 곱하여 나올 수 있는 가장 큰 값을 산출하는 문제
s = input()
result = int(s[0])
for i in range(1, len(s)):
print(result)
if result <= 1:
result += int(s[i])
elif result > 1:
result *= int(s[i])
print(result)
3. 1이 될 때까지
# 1이 될 때까지 알고리즘 문제
# N,K과 선택지 2개가 주어진다.
# 1. N을 -1 한다. | 2. N을 K로 나눈다.
# N이 1이 될 떄까지 1번 혹은 2번 과정을 수행해야하는 횟수를 구하는 것이 문제이다.
n, k = map(int, input().split())
result = 0
while n != 1:
if n % k == 0:
n /= k
else:
n -= 1
result += 1
print(result)
4. 모험가 길드
# 모험가 길드 알고리즘 문제
# N명의 모험가를 대상으로 공포도 X를 입력 받는다
# 공포도가 X인 모험가는 X명 이상으로 구성된 모험가 그룹에 참가해야 한다.
# N명의 모험가에 대한 정보가 주어졌을 때 여행을 떠날 수 있는 그룹 수의 최댓값을 구해라
n = int(input())
x = list(map(int, input().split()))
x.sort()
count = 0
result = 0
for i in x:
count += 1
if count >= i:
result += 1
count = 0
print(result)구현 유형 알고리즘
- 흔히 알고리즘 대회에서 구현 유형 문제란 풀이를 떠올리는 것은 쉽지만 코드로 옮겨내기 어려운 문제를 지칭한다.
- 구현 유형의 예시는 아래와 같다.
1. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
2. 실수 연산을 다루고, 특정 소수점 자리까지 출력해야하는 문제
3. 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
4. 적절한 라이브러리를 찾아서 사용해야 하는 문제
구현 알고리즘 예시
1. Three In Time
# 00시 00분 00초부터 N시 00분 00초 사이의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램 작성
# ex) 00시 00분 03초, 00시 13분 01초
n = int(input())
count = 0
for h in range(n+1):
for m in range(60):
for s in range(60):
if '3' in str(h)+str(s)+str(m):
count += 1
print(count)
2. LRUD
# N x N 2차원 공간이 생성됩니다.
# 공간은 (1,1) ~ (5,5) 로 존재합니다.
# 왼쪽 오른쪽 위 아래를 LRUD로 입력받아 최종적으로 도착할 지점의 좌표를 x y 형태로 출력해라
# 공간 밖으로 나가는 움직임은 skip 한다.
n = int(input())
d_list = list(input().split())
# 시작 좌표
x, y = 1, 1
move_type = ['L', 'R', 'U', 'D']
# L R U D 순서
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
for d in d_list:
for i in range(len(move_type)):
if d == move_type[i]:
nx = x + dx[i]
ny = y + dy[i]
# 공간을 벗어나는 경우 무시
if nx < 1 or nx > n or ny < 1 or ny > n:
continue
x, y = nx, ny
print(x, y)3. 왕실의 나이트
loc = input()
locX = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
locY = ['1', '2', '3', '4', '5', '6', '7', '8']
count = 0
dx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]
x = locX.index(loc[0])
y = locY.index(loc[1])
for i in range(len(dx)):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx > 7 or ny < 0 or ny > 7:
continue
count += 1
print(count)