그리디
-
단순히 매 상황에서 가장 큰 값만 고르는 방법 => 최적의 해를 보장할 수 없을 때가 많음
- 단, 코딩테스트에서 그리디(탐욕법)으로 분류되는 경우에는 최적의 해를 보장하는 경우로 추정함
문제 1
당신이 점원이고 카운터에 500, 100, 50, 10 원 짜리 동전이 무한할 때, 손님에게 거슬러 주어야 할 돈 N원을 거슬러 주어야 할 동전의 최소개수를 구하시오. 단, 거슬러 줘야 할 N원은 항상 10의 배수.
해결 아이디어
최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위 부터 거슬러 줄 수 있을 만큼 거슬러 준다.
가장먼저 500원을 거슬러 줄 수 있을만큼, 그다음 100, 50, 10 원 순서대로 거슬러 준다.
정당성 분석
가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 까닭은 큰단위의 동전이 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
ex) 화폐 단위가 500, 400, 100 원이라면 큰 수가 작은 수 동전의 배수가 아니므로 다른 해가 존재. 가장 큰 동전을 우선 거슬러 줄 수 있는 만큼 거슬러 주는 것이 최적의 해가 되지 않음.문제 2 : 1이 될 때 까지
숫자 n(1 <= n <= 100,000), k(2 <= k <= 100,000)가 주어질 때 n 이 1이 될 때 까지 n을 k로 나누거나, n에서 1을 빼는 2가지 과정을 반복해서 n이 1이 되는 횟수의 최솟값을 출력하시오.
해결 아이디어
나누기를 최대한 많이 수행.
정당성 분석
1을 뺄셈하는 것 보다 2이상의 수로 나누는 것이 수를 훨씬 많이 줄일 수 있기 때문
하단 코드 : 반복문이 1번 실행 될 때마다 n이 k로 나눠지는 연산이 실행 되기 때문에 시간 복잡도가 log(n)이 됨.문제 3 : +또는 *
여러개의 숫자로 이루어진 하나의 문자열 S가 주어질 때(1<= S의 길이 <= 20) 왼쪽 부터 순서대로 숫자 사이에 +또는 * 연산을 진행해 만들어 질 수 있는 가장 큰수를 출력하시오.(단 사칙연산의 *연산이 +연산보다 우선되는 법칙은 적용하지 않고 왼쪽 부터 차례대로 적용한다고 가정)
해결 아이디어
연산 양변의 숫자가 0또는 1이 아닐때는 곱하기를 진행, 0또는 1일때는 더하기를 진행.문제 4 :
모험가 N명이 주어지고 (1<= N <= 100,000) 각 모험가의 공포도가 N이하의 자연수로 주어질 때,
공포도가 N인 사람은 N명 이상의 그룹에 속해야 한다면 나올 수 있는 최대 그룹수를 구하시오.
(모든 모험가가 그룹에 포함되어야 하는 것은 아님)
해결 아이디어
공포도가 작은 모험가 부터, 현재 그룹에 포함된 모험가 수가 현재 확인하고 있는 공포도보다 크거나 같으면 그룹으로 설정
정당성 분석
공포도가 오름차순이면, 항상 최소한의 모험가의 수만 포함하여 그룹을 결성할 수 있게 됨
#문제 2
n, k = map(int, input().split())
result = 0
while True:
#n이 k로 나누어 떨어지는 수가 될 때 까지 빼기
target = (n // k) * k
result += (n - target)
n = tartget
if n < k:
break;
#k로 나누기
n //= k
result += 1
#k 로 나눠지지 않은 마지막 남은 수에 대하여 1 씩 빼기
result += (n-1)
print(result)#문제 3
data = input()
#첫번째 숫자를 숫자로 변경 해 대입
result = int(data[0])
for i in range(1, len(data)) :
num = int(data[i])
if num <= 1 or result <= 1 :
result += num
else :
result *= num
print(result)#문제 4
#모험가 수
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( 1 <= N < = 100), 여행가 A가 이동할 계획서 내용이 주어질 때(1 <= 이동횟수 <= 100) (1,1) 에서 시작해 이동계획대로 움직여 A가 최종적으로 도착할 지점의 좌표(X,Y)를 계산 (공간에서 벗어나게 되는 이동은 무시함) |
| 문제2 : 00시 00분 00초 부터 입력되는 N시 59분 59초 까지 모든 시각 중 3이 한번이라도 포함되는 모든 경우의 수 출력 해결 아이디어: 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있음 -> 완전 탐색 정당성 : 하루가 86,400 초, 모든 경우의 수를 세어도 86,400초 인데 파이썬이 1초에 2,000 만번 계산이 가능하므로 문제 없음. |
| 문제3 : 8*8 체스판 위에서 나이트의 위치가 주어졌을 때 움직일 수 있는 경우의 수 출력 해결 아이디어 : 나이트가 이동할 수 있는 8가지 방향에 대해 각각 이동 가능한지 확인 -> 완전 탐색 |
| 문제4 : 알파벳 대문자와 숫자(0~9)로 구성된 문자열이 입력될 때 알파벳을 오름차순으로 정렬, 출력한 뒤에 그 뒤에 숫자들을 더한 값을 이어서 출력 해결 아이디어 : 완전 탐색 |
#문제 1
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
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)#문제3
#나이트 위치 입력
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0]))-int(ord('a')) + 1
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 = row + 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))