📌 그리디 알고리즘
현재 상황에서 지금 당장 좋은 것만 고르는 방법으로, 매 순간 가장 좋아 보이는 것을 선택한다. 이 때, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시한다.
거스름돈
n원의 돈을 500, 100, 50, 10원짜리로 거슬러 줄 때, 가능한 최소 동전의 개수를 구하는 문제다.
거스름돈은 항상 동전의 최소 단위인 10원의 배수이기 때문에 가장 큰 단위부터 가장 작은 단위까지 차례로 확인하여 거슬러 주는 작업을 수행하면 된다.
내가 작성한 코드
n = int(input())
ans = 0
while n > 500:
n -= 500
ans += 1
while n > 100:
n -= 100
ans += 1
while n > 50:
n -= 50
ans += 1
while n > 0:
n -= 10
ans += 1
print(ans)예시 코드
n = int(input())
coins = [500, 100, 50, 10]
count = 0
for coin in coins:
count += n // coin
n %= coin
print(count)처음에는 동전의 개수만큼 while문을 작성하여 거스름돈을 줄여나가는 방법을 선택했다. 하지만, 동전의 단위를 배열에 담아 for 반복문을 돌리고, 나눗셈, 나머지 연산자를 사용하면 시간복잡도도 줄어들 뿐만 아니라, 코드도 훨씬 직관적이고 간결하게 작성할 수 있다.
큰 수의 법칙
큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 m번 더하여 가장 큰 수를 만드는 법칙이다. 이 때, 배열의 특정한 인덱스에 해당하는 수가 연속해서 k번을 초과하여 더해질 수는 없다.
예를 들어, m이 8, k가 3이고, 배열 arr가 [2, 4, 5, 4, 6]이라고 할 때, 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5로, 46이 된다.
이 때, 다른 인덱스에 있는 값이 같은 경우에도 이는 서로 다른 것으로 간주한다. 따라서 arr가 [3, 4, 3, 4, 3]일 때, 두번째 4와 네번째 4는 서로 다른 것이므로 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4가 가능하다.
아이디어
해당 문제에서 필요한 값은 배열의 가장 큰 값과 두번째로 큰 값, 둘 뿐이다. 따라서 sort()메서드를 활용하여 가장 큰 값과 두번째로 큰 값을 구하고, 이를 m과 k에 맞게 더해주면 된다.
내가 작성한 코드
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
arr = list(map(int, input().split()))
ans = 0
arr.sort()
a = arr.pop()
b = arr.pop()
cntA = m // k
cntB = m % k
ans = a * (k * cntA) + (b * cntB)
print(ans)예시 코드
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
first = arr[n-1]
second = arr[n-2]
count = int(m / (k+1)) * k
count += m % (k + 1)
ans = 0
ans += count * first
ans += (m - count) * second
print(ans)가장 큰 수를 더하기 위해 사용한 논리는 같지만, 나는 변수를 하나 더 사용했기 때문에 메모리적인 부분에서 차이는 발생할 수 있겠다.
숫자 카드 게임
N * M 형태로 카드가 놓여 있을 때, 각 행의 가장 작은 수들을 선택한다. 이 때, 선택한 수들 중 가장 큰 수를 출력한다.
아이디어
파이썬 내장 함수 중 max()와 min()을 활용하면 쉽게 해결할 수 있다. for 반복문을 통해 각 행에 접근하여 최소값을 구하고, 이들 중 최대값을 출력한다.
내가 작성한 코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
cards = [list(map(int, input().split())) for _ in range(n)]
temp = []
for card in cards:
temp.append(min(card))
print(max(temp))예시 코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
result = 0
for i in range(n):
card = list(map(int, input().split()))
min_value = min(card)
result = max(min_value, result)
print(result)2차원 배열 cards를 만들고, 해당 배열의 각 원소(배열)마다 min()함수를 실행하여 최소값을 구했다. 이를 빈 배열 temp에 삽입한 뒤 max()함수를 실행하면 원하는 값을 구할 수 있다.
예시 코드에서는 입력값을 받자마자 해당 배열의 최소값을 구하고, 현재까지의 최소값들과 비교하여 즉각적으로 최대값을 구해주었다.
1이 될 때까지
n이 1이 될 때까지 아래의 과정 중 하나를 반복적으로 선택하여 수행한다.
1. n에서 1을 뺀다.
2. n을 k로 나눈다.이 때, 2번 연산은 n이 k로 나누어떨어질 경우에만 실행가능하다.
아이디어
직관적으로 알 수 있는 것은 2번 연산이 많을수록 수행 횟수는 줄어든다. 그렇기 때문에 n을 k의 배수로 만드는 것이 중요하다.
처음에는 단순히 n을 확인하고, 1, 2번 연산 중 하나를 선택하도록 했다. 하지만 아래에서 확인할 수 있듯이 n이 커질수록 문제가 생길 수 있다. 아래 코드에서 확인하자.
내가 작성한 코드
n, k = map(int, input().split())
cnt = 0
while n != 1:
if n % k == 0:
n //= k
else:
n -= 1
cnt += 1
print(cnt)예시 코드
n, k = map(int, input().split())
cnt = 0
while True:
# n이 k로 나누어떨어질 때까지 1 빼기
target = (n // k) * k
cnt += n - target
n = target
# 더 이상 n을 k로 나눌 수 없으면 반복문 탈출
if n < k:
break
# n을 k로 나누기
cnt += 1
n //= k
# 남은 수에 1씩 빼기
cnt += n - 1
print(cnt)n이 100억 이상의 큰 수가 되는 경우라면, 반복문을 돌리며 1을 빼는 것이 문제가 될 수 있다. 이 경우에는 n이 k의 배수가 되도록 한번에 빼는 방식이 효율적이다.
문제에서 요구하는 답을 얻는 데에만 매달리지 않고, 어떻게 효율적인 코드를 작성할 수 있는지 고려하는 사고를 연습하자.
볼링공 고르기
볼링공이 총 n개가 있고, 공의 무게는 1부터 m까지의 자연수 형태로 존재한다. 이 때, 같은 무게의 볼링공이 있을 수 있지만, 이들은 서로 다른 공으로 간주한다. 두 사람이 무게가 서로 다른 볼링공을 고르고자 할 때, 가능한 경우의 수를 요구한다.
아이디어
for 반복문을 통해 balls 배열에 접근하여 볼링공의 무게를 확인한다. 이 때, 지나온 원소들은 이미 확인이 끝났기 때문에 새로 확인할 필요가 없다. 그래서 balls[i+1::]로 뒤쪽의 원소들만 받아온다. 그리고 해당 부분 배열의 원소들 중 현재 볼링공의 무게와 일치하는 볼링공의 개수를 빼면 무게가 다른 볼링공의 개수를 구할 수 있다. 따라서 count() 메서드를 활용하여 무게가 같은 볼링공의 개수를 구해주었다. 이를 cnt 변수에 추가하여 최종 결과값을 얻을 수 있다.
내가 작성한 코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
balls = list(map(int, input().split()))
cnt = 0
for i in range(n):
w = balls[i]
ea = balls[i+1::].count(w)
cnt += n - (i + 1) - ea
print(cnt)예시 코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
balls = list(map(int, input().split()))
result = [0] * (m+1)
cnt = 0
for weight in balls:
result[weight] += 1
for i in range(1, m+1):
n -= result[i]
cnt += n * result[i]
print(cnt)처음에 작성한 방법대로 실행할 경우, 볼링공의 개수만큼 반복문을 돌리게 되고, count() 메서드를 사용하기 때문에 소요 시간이 커질 수 있다.
그래서 예시 코드에서는 볼링공의 무게만큼 반복문을 돌린다.
먼저, 1부터 볼링공의 최대 무게인 m번 인덱스까지 존재하는 배열, result를 만든다. 그리고 반복문을 통해 볼링공의 무게 정보를 담고 있는 balls 배열에 접근하여 볼링공의 무게에 해당하는 result의 인덱스에 해당 무게를 가진 볼링공이 몇 개 존재하는지 저장한다. 이후에 1부터 m+1까지 반복문을 돌려 전체 볼링공 중 같은 무게를 가진 볼링공의 개수를 제외한다. 그리고 해당 볼링공의 개수 * 나머지 볼링공의 개수를 하여 서로 다른 무게의 볼링공을 선택할 경우의 수를 구해준다. 이후 다른 무게의 볼링공에도 똑같은 방법을 적용하여 각 무게별 경우의 수를 구하고, 이를 cnt 변수에 더해준다.
위의 방법을 따른다면, 볼링공을 선택할 때 같은 무게를 가진 볼링공이 있다면 이들을 선택하는 경우의 수를 한번에 처리해주기 때문에 시간적인 측면에서 효율적이다.
--
참고 도서
🙇🏻♂️ 나 동빈, 이것이 취업을 위한 코딩테스트다
