그리디 알고리즘 (탐욕법)
1) 개요
- 현재 상황에서 가장 좋은 것만 고르는 방법
- 최적의 해를 구할 수 있는지 정당성 분석이 요구됨
- 코딩테스트의 경우에 한해서, 이를 이용한 방법이 최적의 해가 구해지는 상황이라고 생각해야함
2) 샘플 문제
- 임의의 수 N이 1이 될 때가지 두 과정 중 반복 선택하여야 하는데 두번째는 나누어 떨어질 때만 선택 가능
(1) N 에서 1 빼기 (2) N에서 K 나누기
n, k = map(int, input().split())
# 내가 푼 방법 (숫자가 커지면 시간복잡도가 높아짐)
cnt = 0
while True:
if n == 1:
break
elif n % k == 0:
n //= k
cnt += 1
else:
n -= 1
cnt += 1
print(cnt)
# -----------------------------
result = 0
while True:
# n이 k로 나누어 떨어지는 경우의 수 만큼 빼기
target = (n // k) * k
result += (n - target)
n = target
if n < k:
break
result += 1
n //= k
result += (n - 1)
print(result)
3) 샘플문제
- 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어짐
- 왼쪽부터 오른쪽으로 하나씩 숫자를 확인하고 'x' 또는 '+' 연산자를 넣어 결과가 가장 큰 수를 구해야 하는데 왼쪽부터
순서대로 연산
# 'x'가 제일 값을 크게 하지만, 수가 0 또는 1이라면 더하는 것이 효율적
s = [int(i) for i in input()]
result = s[0]
for i in s[1:]:
if i <= 1 or result <= 1:
result += i
else:
result *= i
print(result)
4) 샘플문제
- 모험가 N명이 있는데 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야함
- N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최대값을 구함
- 모든 모험가를 그룹에 넣을 필요는 없음
N = int(input())
li = list(map(int, input().split()))
li.sort()
result = 0
cnt = 0
for i in li:
cnt += 1
if cnt >= i:
result += 1
cnt = 0
print(result)
구현 (시뮬레이션, 완전탐색)
1) 개요
- 알고리즘은 간단한데 코드가 지나치게 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력하는 문제
- 문자열을 특정 기준에 따라 끊어 처리하는 문제
- 적절한 라이브러리 사용 문제
2) 샘플문제
- L, R, U, D에 따라 이동시키는데 좌표 범위를 벗어날 경우 스킵
N = int(input())
li = list(map(str, input().split()))
me = [1, 1]
for i in li:
if i == 'R':
me[1] += 1
if me[1] < 1 or me[1] > N:
me[1] -= 1
elif i == 'U':
me[0] -= 1
if me[0] < 1 or me[0] > N:
me[0] += 1
elif i == 'L':
me[1] -= 1
if me[1] < 1 or me[1] > N:
me[1] += 1
else:
me[0] += 1
if me[0] < 1 or me[0] > N:
me[0] -= 1
print(me[0], me[1])
3) 샘플문제
- N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 시각 중 3이 하나라도 포함되는 모든 경우의 수를 구해라
- 해당 문제는 완전 탐색하는 문제 (greedy)
N = int(input())
cnt = 0
for i in range(N + 1): # 시간
for j in range(60):
for k in range(60):
if '3' in str(i) or '3' in str(j) or '3' in str(k):
cnt += 1
print(cnt)
4) 샘플문제
- 8 x 8 좌표 평면에서 L자 형태로만 이동하며 좌표 밖을 나갈 수 없다.
- 이동 방법은 가) 수평으로 두 칸 이동 후 수직으로 한 칸 나) 수직으로 두 칸 이동 후 수평으로 한 칸
- 위치가 주어졌을 때, 이동할 수 있는 경우의 수를 출력해라 (행 : 1 ~ 8, 열 : a ~ h)
coo = input()
col = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
row = ['1', '2', '3', '4', '5', '6', '7', '8']
pos = [col.index(coo[0]) + 1, row.index(coo[1]) + 1]
dx = [2, 2, 1, -1, -2, -2, -1, 1]
dy = [1, -1, 2, 2, 1, -1, -2, -2]
cnt = 0
for i in range(8):
nx = pos[0] + dx[i]
ny = pos[1] + dy[i]
if nx > 8 or nx < 1 or ny > 8 or ny < 1:
continue
else:
cnt += 1
print(cnt)
#-----------------------------------------------
column = int(ord(coo[0])) - int(ord('a')) + 1
# 위와 같이 한다면 리스트를 2 개 만들 필요가 없어서 더욱 효율적
5) 샘플문제
- 알파벳 대문자와 숫자 (0 ~ 9)로 구성된 문자열이 입력된다.
- 모든 알파벳을 오름차순으로 정렬하고 출력한 뒤, 그 뒤에 모든 숫자를 더하여 출력 ( K1KA5CB7 -> ABCKK13)
num = 0
coo = input()
li = []
for i in coo:
if int(ord(i)) < 65: # i.isalpha() : True if it is alphabet
num += int(i)
else:
li.append(i)
li.sort()
li.append(str(num))
print(''.join(li))나동빈님의 유튜브를 보고 정리한 내용입니다. www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2
'Python > Coding Test' 카테고리의 다른 글
| 그래프 탐색 알고리즘 (DFS / BFS) (0) | 2021.01.22 |
|---|
