그리디 & 구현

[그리디]

예시1) 거스름 돈

가장 큰 화폐 단위부터 돈을 거슬러 주기

: 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

: 800원 거슬러 줘야 하는데 화폐 단위가 500, 400, 100이면 X

n = 1260
count = 0

#큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array :
    count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)

 

예시2) 1이 될 때까지

N에 대하여 최대한 많이 나누기

K로 나누어 떨어지지 않으면 1 빼기, 나누어 떨어지면 K로 나누기

* N이 K로 나누어 떨어지는가 확인 -> target = (n // k) * k  

  n이 k로 나누어 떨어지지 않는다고 할 때, 가장 가까운 k로 나누어 떨어지는 수 찾을 수 있음

#N, K을 공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True :
    #N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    #N이 K보다 작을 때 (더이상 나눌 수 없을 때) 반복문 탈출
    if n < k :
    	break
    #K로 나누기
    result += 1
    n //= k

#마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

 

예시3) 곱하기 혹은 더하기

두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1이하인 경우에는 더하며, 두 수가 모두 2이상인 겨우에는 곱하기

data = input()

#첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)) :
    #두 수 중에서 하나라도 0 혹은 1인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <= 1 or result <= 1 :
    	result += num
    else :
    	result *= num

print(result)

 

예시4) 모함가 길드 : 만들 수 있는 그룹 수의 최댓값 구하기

오름차순 정렬 이후에 공포도가 낮은 모험가부터 하나씩 확인 -> 1 2 2 2 3

항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 됨

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0 #총 그룹의 수
count = 0 #현재 그룹에 포함된 모험가의 수

for i in data : #공포도를 낮은 것부터 하나씩 확인하며
    count += 1 #현재 그룹에 해당 모험가를 포함시키기
    if count >= i : #현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
    	result += 1 #총 그룹의 수 증가시키기
        count = 0 #현재 그룹에 포함된 모험가의 수 초기화

print(result) #총 그룹의 수 출력

 

 

 

[구현]

행렬

방향벡터

 

예시1) 상하좌우

#N 입력 받기
n = int(input())
x, y = 1, 1
plans = input().split()

#L, R, U, D에 따른 이동 방향
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)

 

예시2) 3이 들어간 시각 세기

가능한 모든 시각의 경우를 하나씩 모두 세서 풀기, 완전탐색!

#H 입력 받기
h = int(input())

count = 0
for i in range(h + 1) :
    for j in range(60) :
    	for k in range(60) :
            #매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k) :
            	count += 1

print(count)

 

예시3) 왕실의 나이트

요구사항대로 충실히 구현하기

나이트의 8가지 경로를 하나씩 확인하며 각 위치로 이동 가능한지 확인하기

리스트를 이용하여 8가지 방향에 대한 방향 벡터 정의하기

*ord(A) : 문자의 순서 위치 값으로 변환

*chr(10) : 정수 값을 유니코드 문자로 변환

#현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

#나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

#8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps :
    #이동하고자 하는 위치 확인
    next_row = row + step[0]
    nex_column = column + step[1]
    #해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8 :
    	result += 1

print(result)

 

예시4) 문자열 재정렬

요구사항대로 충실히 구현하기

문자열이 입력되면 문자를 하나씩 확인하고 별도의 리스트에 저장하기

숫자인 경우 따로 합계 계산하기

리스트에 저장된 알파벳을 정렬해 출력하고 합계를 뒤에 붙여서 출력하기

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

 

 

 

 

 

https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2 

불러오는 중입니다...