그리디(Greedy)

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

예제1 거스름돈

카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정할 때 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types :
	count += n//coin
    n %= coin
print(count)

최소 개수이므로 큰 단위의 동전부터 거슬러주면 된다

예제2 큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙

# n = 입력받을 수, m = 더 할 숫자의 수, k = 한번에 더할 수 있는 같은 수 횟수
n, m, k = map(int, input().split())

data = list(map(int, input().split())
data.sort()
first = data[n-1]
second = 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)

예제3 숫자 카드 게임

숫자 카드 게임은 선택한 행에서 가장 낮은 수를 뽑으며 그 중에서 제일 큰 수를 뽑아야 하는 게임이다.

n, m = map(int, input().split())

result = 0

for i in range(n)
	data =list(map(int, input().split()))
    min_value = min(data)
    result = max(result, min_value)
    
print(result)

예제4 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
1. N에서 1을 뺀다.
2. N을 K로 나눈다.

n, k = map(int, input().split())
result = 0

while n >= k:
	while n % k != 0:
    	n-=1
        result +=1
    n //= k
    result +=1
# 마지막으로 남은 수에 대하여 1씩 빼기
while n>1:
	n -=1
	result +=1
    
print(result)

예제5 상하좌우

NxN 크기의 정사각형 공간위에 있을 때 공간을 벗어나는 움직임은 무시되며 L,R,U,D에 따라 움직일 때 위치 출력

ex
입력 예시
5
RRRUDD

출력 예시
3 4

----------------------------
n = int(input()) //정사각형 크기
x,y = 1,1 //처음 위치
plans = input().split() //움직임

dx = [0,0,-1,1]
dy = [-1,1,0,0]
move_type = ["L","R","U","D"]

for pan 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)

예제6 시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램

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)

예제7 왕실의 나이트

8 x 8 크기의 평면에서 나이트는 2가지 경우로만 이동할 수 있다

• 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
• 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기
  이때 나이트의 위치가 입력되었을 때 이동할 수 있는 경우의 수를 구하는 프로그램(평면 외부로 나갈 수 없다.)

<입력예시>
a1
<출력예시>
2

-------------------------

input_data = input() //나이트 위치
row = int(input_data[1]) //a1에서 1
column = int(ord(input_data[0])) - int(ord("a")) + 1
//a1에서 a의 유니코드 - a의 유니코드 값(a = 97) + 1로 a,b,c,d,e...를 1,2,3,4,5... 로 표현

steps = [(-2,-1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)] //나이트가 움직일 수 있는 경우의 수

result = 0
for step in steps :
	next_row = row + step[0]
    next_column = column + step[1]
    if next_row >= 1 and next_row <=8 and next_column >=1 and next_column <=8 :
    //나이트가 밖으로 안나가면 +1
    	resukt +=1
print(result)

예제8 게임 개발

게임 캐릭터가 맵안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 캐릭터는 바다로 되어 있는 공간에는 갈 수 없다. 아래는 캐릭터의 움직임의 설정이다.
1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가본칸이거나 바다로 되어 있는 칸인 경우에는 바라보는 방향을 유지한 채로 한칸 뒤로 가고 1단계로 돌아간다. 단 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

매뉴얼에 따라 캐릭터를 이동시킨 뒤에 캐릭터가 방문한 칸의 수를 출력하는 프로그램

• 0 : 북쪽

• 1 : 동쪽

• 2 : 남쪽

• 3 : 서쪽

• 0 : 육지

• 1 : 바다

<입력예시>
4 4 //맵 크기
1 1 0 //(1,1)에 북쪽(0)을 바라보고 서 있는 캐릭터
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1
//여기서 맵의 외곽은 반드시 바다로 둘러쌓여있어야 에러가 안난다.
<출력예시>
3
-------------------------------------------------
n, m = map(int, input().split())

d =[[0] * m for _ in range(n)]
//방문한 칸을 확인하기 위해 0으로 이루어진 맵 생성

x, y, direction = map(int, input().split())
d[x][y] = 1 
//캐릭터의 초기위치는 방문한 것으로 설정

array = []
for i in range(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
        //북이 0 이므로 -1이면 서쪽(3)

//시뮬레이션 시작
count = 1
turn_time = 0
while True :
	turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    if d[nx][ny] == 0 and array[dx][dy] == 0 :
    	//한번도 가지 않은 곳 + 육지인경우
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1 
        turn_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
        turn_time = 0
print(count)