그리디(탐욕법): 당장 좋은 것만 고르는 방법
대표적문제 : 거스름돈
예)
500원,100원, 50원, 10원짜리 동전이 무수히 존재한다.
손님에게 거슬러 줘야할 돈이 N원 일때 거슬러 줘야할 동전의 최소개수?(단, 거슬러줘야할 돈 N은 항상 10의 배수다)
n = 1260
count =0
coin_types[500,100,50,10]
for coin in coin_types:
count += n // coin
n %= coin
print(count)
화폐의 개수가 K개라고 할 때, 시간 복잡도는 O(K)이다.
즉, 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다.
거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른해가 나올 수 없기 때문이다.
만약 500,400,100이 화폐단위라면,
그리디알고리즘에서 4개의 동전을 거슬러 줘야한다.(500,100,100,100)
그러나 최적의 해는 2개(400,400)이다.
아이디어는 정당하다. 그러나 해법이 정단한지 검토해야한다.
큰 수의 법칙
다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단 , 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없는 것이 이 법칙의 특닝이다.
# 더했을때 가장 큰 수 출력하기
n,m,k = 5, 8, 3
data=[2, 4, 5, 4, 6]
# m : 총 횟수
# k : 연속횟수
data.sort();
first = data[n-1]
secont- data[n-2]
result = 0
while True:
for i in range(k)
if m == 0:
break
result += first
m-=1
if m == 0:
break
result += second
m-=1
print(result)핵심아이디어 : 연속으로 더할 수 있는 획수는 최대 K번이므로 '가장 큰수를 K번 더하고 두번째로 큰 수를 한 번 더하는 연산'을 반복
M의 크기가 100억이상 커진다면 시간 초과 판정을 받을 것이다. 수학적 아이디어를 이용해 효율적으로 문제를 풀어준다.
이때 핵심은 반복되는 수열에 대해 파악하는 것이다.
반복되는 수열 : {6,6,6,3}
반복되는 수열의 길이 : 4 (K + 1)
수열이 반복되는 횟수 : int( M / (K + 1) )
수열이 반복되는 횟수에서 가장큰수가 등장하는 횟수 : int( M / (K + 1) ) * K
반복횟수로 나누어떨어지지 않는 나머지 (= 가장큰수만 남음) : M % (K + 1)
따라서
가장큰수가 더해지는 횟수 = int( M / (K + 1) ) * K + M % (K + 1)
두번째 큰 수가 더해지는 횟수 = m - 가장큰수가 더해지는 횟수
#...동일...
count = int(m / (k+1)) * k
count += m % (k+1)
result = 0
result += count * first
result += (m-count) * second
print(result)숫자 카드 게임
여러개의 숫자카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를뽑아야하고 룰은 다음과 같다.
n : row, m : col
행을 먼저 선택
행에 포함된 카드중 가장 낮은 숫자를 뽑아야한다.
뽑아진 가장 낮은 숫자들중 가장 높은 숫자를 출력하랑
result = 0
for i in range(m):
arr = list(map(int, input().split()))
minVal = min(arr)
# if result < minVal
# result = minVal
result = max(result, minVal)
print(result)핵심은 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것이다.
1이 될 때까지
N이 1일 될때까지 두 과정 중 하나를 반복적으로 선택하여 수행
1. N에서 1을 뺀다
2. N을 K로 나눈다.
단, 2번 연산은 N이 K로 나누어 떨어질때만 선택할 수 있다.
N= 17, K=4
1번 과정 한 번 수행, N = 16
이후 2번 과정 두 번 수행, N = 1 (16/4 = 4, 4/4 = 1)
총 3번 수행
N이 1일 될때까지, 수행하는 최소횟수를 구하라
#내 코드
while n!=1:
if n % m == 0:
n /= m
else:
n -= 1
result += 1
print(result)핵심, 최대한 많이 나누기
N이 100억 이상의 큰 수가 되는 경우 빠르게 동작할려면 N이 K의 배수가 되도록 한번에 빼는 방식으로 작성하자.
while True:
# ( N === K로 나누어떨이지는 수)가 될 때까지 1씩 빼기
target = (n // k) *k
result+= (n-target)
n = target
# N이 K보다 작을때 (더 이상 나눌 수 없을 때) 반복문 탈출
if n < k:
break
# K로 나누기
result +=1
n //= k
result += (n-1)
print(result)
# ==== 예 =====
17, 4
#loop1
target = 17//4 *4 => 16
result = 1
n = target = 16
16 < 4 X
result = 2
n = 4
#loop2
target = 4//4 * 4 = 4
result = 2+ (4-4) = 2
n = target = 4
4<4 false
result = 3
n = 4//4 = 1
#loop3
target = 0
result = 3 + (1-0) = 4
n = target = 0
0 < 4 break
result += (0-1) == 3상하좌우
시작좌표 (1,1)
NxN 정사각형 공간. 각 방향으로 한 칸씩 이동
x, y = 1,1
#L,R,U,D
dx = [0,0,-1,1]
dy = [-1,1,0,0]
move_typs = ['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)시각
00시 00분 00초~ N시 59분 59초
3이 하나라도 포함될 때, 경우의수
h= int(input())
count = 0
#h
for i in range(h+1)
#m
for j in range(60)
#s
for k in range(60)
if '3' in str(i)+str(j)+str(k):
count+=1
print(count)왕실의 나이트
수평으로 두 칸 이동 뒤에 수직으로 한 칸 이동하기
수직으로 두 칸 이동 뒤에 수평으로 한 칸 이동하기
현재위치에서 가능한 이동 경우의수
#나의 코드
dx = [2, 2, -2, -2, 1, 1, -1, -1]
dy = [1, -1, 1 ,-1, 2, -2, 2, -2]
col = ['a','b','c','d','e','f','g','h']
m = 8
y,x = input.split('')
y = col.index(y)
x = int(x)
result = m
for i in range(m):
nx = x + dx[i]
ny = y + dy[i]
if nx > m or ny > m or nx < 1 or ny <1 :
result-=1
print(result)#답안코드
input_data = input()
steps = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
x = int(input_data[1])
# ord 유니코드 숫자 값을 리턴하는 함수
y = int(ord(input_data[0]))- int(ord('a')) + 1
result = 0
for step in steps:
nx = x + step[0]
ny = y + step[1]
if nx <= 8 or ny <= 8 or nx >= 1 or ny >=1 :
result+=1
print(result)게임개발 (난이도 중)
n x m 직사가형
육지(0) 또는 바다(1)
동(1)서(3)남(2)북(0) 중 한 곳을 바라본다.
n , m = map(int, input().split())
# 방문여부를 저장하는 map 생성
d = [[0]*m for _ in range(n)]
x, y, direction = map(int, input().split())
d[x][y] = 1
# 전체 맵 정보 입력받기
array = []
for i in ragne(n):
array.append(list(map(int, input().split()))
# 북,동,남,서 방향정의 (반시계 적용)
dx = [-1,0,1,0]
dy = [0,1,0,-1]
# 왼쪽 회전 함수
def turn_left():
global direction
direction -= 1
if direction == -1:
direction = 3
count = 1
trun_time = 0
while True:
#왼쪽회전
turn_left();
nx = x + dx[direction]
ny = y + dy[direction]
# 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우
if d[nx][ny] == 0 and array[nx][ny] ==0:
d[nx][ny] = 1
x = nx
y = ny
count +=1
trun_time = 0
continue
# 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
else:
turn_time+=1
if turn_time == 4:
nx = x - dx[direction]
ny = y - dy[direction]
# 뒤로 갈 수 있다면 이동하기
if array[nx][ny] == 0:
x = nx
y = ny
# 뒤가 바다로 막혀있다면
else:
break
print(count)