그리디 알고리즘
일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장하지 않는다. 하지만 코딩 테스트에서의 대부분의 그리디 문제는 그리디 알고리즘으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 한다.
개념
그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법.
예제
1.
💡 아이디어
거스름돈의 동전 갯수가 최소가 되려면 제일 큰 금액의 동전부터 최대한 많이 거슬러주면 된다. 1260원이라면 500원 2개, 100원 2개, 50원 1개, 10원 1개처럼 순서대로 동전의 수를 결정한다.
input = int(input('입력 = '))
result = 0
array = [500, 100, 50, 10]
for i in array:
if input // i >= 1:
result += input // i
input -= (input // i) * i
print(f'남은 거스름돈 = {input}, 거스른 동전의 갯수 = {result}')정해진 동전의 값을 list로 만든다. 그리고 500원부터 순차적으로 500원으로 거슬러 줄 수 있는 최대한의 갯수로 계산한다.
2.
💡 아이디어
어떤 수를 최대한 적은 연산으로 1로 만드려면 나누기를 하는 것이 제일 효율적입니다. 고로 나누기 연산을 최대한 많이 하는 것이 이 문제의 핵심입니다. 입력받은 N이 K의 배수라면 나누기가 가능한데 거듭제곱이 아니라면 나눈 후에 다시 나눌 수 있는 숫자가 될 때까지 1씩 감소 시켜야합니다.
n, k = map(int, input('입력 = ').split())
result = 0
while(True):
if n == 1:
break;
if n % k == 0:
n /= k
else:
n -= 1
result += 1
print(result)while문을 보면 먼저 n이 1일 때 반복문을 탈출해야 함으로 if문을 작성해줍니다. 두번째 if문에서는 n을 k로 나누기가 가능한지 확인해보고 가능하면 나누어주고, 불가능하면 -1을 해줍니다. 이렇게하면 나누어지지 않을 때는 계속 -1을 해주어 나누어지는 값을 찾아가는 로직을 짤 수 있습니다.
3.
💡 아이디어
두 수 중에서 하나라도 0이거나 1이면 덧셈을, 둘 다 0이거나 1이 아니면 곱셈을 할 수록 숫자는 커진다.
s = input('입력 = ')
result = 0
for i in range(1, len(s)):
num = int(s[i])
if num <= 1 or result <= 1:
result += num
else:
result *= num
print(result)위에 기술한 내용을 코드로 구현하면 이렇게된다.
4.
💡 아이디어
먼저 입력받은 공포도를 sort 시킨다. 그러면 공포도가 오름차순으로 바뀔거다. 생각을 해보자 공포도가 높은 사람을 배제하는 것이 가장 효율적일 것이다. 그럼 오름차순으로 정렬한대로 그룹을 묶어주면 최대 그룹의 갯수를 구할 수 있다.
n = int(input('입력 = '))
fear = list(map(int, input().split()))
offset = 0
result = 0
fear.sort()
for i in range(len(fear)):
if i + 1 - offset >= fear[i]:
result += 1
offset = i + 1
print(result)for문이 시작하기 전에 먼저 fear를 오름차순으로 sort 시킨다.
다음으로 if문에서 i + 1 - offset은 이전 그룹이 만들어지고 난 후 현재까지 세어진 길드원의 수라고 생각하면 된다.
이 문제에서는 i가 커짐으로 새로운 길드원이 들어 왔을 때 정렬을 했기에 공포도가 같거나 큰 길드원이 새로 그룹에 들어오게 된다. 고로 그룹에 들어온 마지막 길드원을 기준으로 공포도와 그룹의 길드원 수를 비교하면 되기 때문에 이런 로직을 만들었다.
구현 문제
개념
풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
대표 유형
-
알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
-
실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
-
문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
-
적절한 라이브러리를 찾아서 사용해야 하는 문제
2차원 공간 문제 유형
이러한 2차원 공간에서의 이동 문제는 방향 벡터를 지정해줌으로 손쉽게 문제를 해결할 수 있다.
예제
1.
💡 아이디어
이 문제는 2차원 이동 문제의 대표적인 문제다. 위에 설명한대로 방향 벡터를 정의하고 만약 2차원 평면의 범위 밖으로 나갔다면 이동을 무시하는 로직을 짜면 된다.
n = int(input('입력 = '))
movement = list(input().split())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
direction = ['R', 'L', 'D', 'U']
def move(x, y, movement):
index = direction.index(movement)
movedX = x + dx[index]
movedY = y + dy[index]
if movedX >= n or movedX < 0 or movedY >= n or movedY < 0:
return x, y
else:
return movedX, movedY
x, y = 0, 0
for i in movement:
x, y = move(x, y, i)
print(y + 1, x + 1 )이 문제에서는 동서남북 방향으로 1만큼씩 이동한다. 고로 방향 벡터와 방향을 코드와 같이 같은 index로 정의 해준다. 그리고 move 함수를 정의해서 이 문제를 풀어봤다.
move 함수에서는 방향에 맞는 벡터를 구하기 위해서 index를 정의한다. 그리고 이것을 기준으로 이동을 시킨다. 이동시킨 방향이 좌표의 밖으로 나갔을 경우 이동을 무시하기 위해 기존 x,y를 반환하고 범위 안의 이동이라면 movedX, movedY를 반환한다.
그리고 마지막에 좌표를 출력할 때 로직상에서는 (0,0)을 기준으로 잡았기 때문에 각 +1을 해주고, 행렬을 x,y 좌표로 나타내기 위해서는 뒤집어야 되기 때문에 반대로 출력을 해준다.
2.
💡 아이디어
이 문제는 간단하게 3중 반복문으로 해결할 수 있다. 시간의 범위를 n+1 까지 하는 것에 실수를 하지 않고 간단하게 in을 통해서 3이 포함되는 시간에는 result += 1을 통해서 카운트 해주면 된다.
n = int(input('입력 = '))
result = 0
for i in range(n + 1):
for j in range(60):
for k in range(60):
if '3' in str(i) + str(j) + str(k):
result += 1
print(result)3.
💡 아이디어
이 문제는 이전에 풀었던 이동 문제와 사실상 같은 문제이다. 이제 이런 2차원 공간에서의 이동 문제에서는 무조건 '방향 벡터'를 떠올려야한다. 방향 벡터를 나이트가 이동할 수 있는 방향으로만 지정하면 손쉽게 문제를 풀 수 있다.
from string import ascii_lowercase
dx = [2, 2, -2, -2, 1, -1, 1, -1]
dy = [1, -1, 1, -1, 2, 2, -2, -2]
input = input('입력 = ')
x = int(ascii_lowercase.index(input[0]))
y = int(input[1])
result = 0
for i in range(len(dx)):
movedX = x + dx[i]
movedY = y + dy[i]
if movedX > 8 or movedX <= 0 or movedY > 8 or movedY <= 0:
continue
result += 1
print(result)먼저 입력받은 나이트의 위치를 숫자로 반환하기 위해서 ascii_lowercase를 사용했다.
이 문제에서도 이전에 풀었던 2차원 공간 이동문제처럼 벡터를 지정해주었다. 나이트가 이동할 수 있는 벡터는 총 8가지로 각 경우를 정의한다. 그리고 for문에서 각 경우의 수로 이동하였을 때 범위를 벗어난다면 카운트하지않고, 범위 안이면 카운트를 한다.
3.
💡 아이디어
이 문제도 파이썬의 내장함수가 잘되어 있어 생각보다 쉽게 풀 수 있다. isAlpha와 isNumeric으로 경우의 수를 나눠서 풀면 된다.
s = input('입력 = ')
result = str()
sum = 0
for i in s:
if i.isalpha():
result += i
else:
sum += int(i)
result = sorted(result)
if sum != 0:
result.append(str(sum))
print(''.join(result))알파벳이면 result에 더하고, 숫자면 sum에 더한다. 그리고 result를 정렬하고, sum이 0이 아니면 리스트 뒤에 붙혀준다. 그리고 list to str을 해서 값을 출력한다.
