✏️ 서론
어제의 연장선으로 오늘도 그리디 문제들을 풀어보자.
책에 나와있는 문제들을 풀어볼 것이다.
✏️ 본론
📍 [ 문제 1 ] 숫자카드게임
숫자 카드게임은 여러 개의 숫자 카드 중 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.
룰은 다음과 같다.
- 숫자가 쓰인 카드들이 N X M 형태로 놓여있다. 이때, N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
- 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
- 그 다음 선택된 행에 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
- 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
그리디 알고리즘 유형의 문제는 문제 해결을 위한 아이디어를 떠올렸다면 정답을 찾을 수 있다.
이 문제의 아이디어는 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것이다.
가장 작은 수를 찾아주는 min()함수를 사용하거나 2중 반복문을 사용하자.
n, m = list(map(int, input().split()))
result = 0
# n만큼 열 생성
# data로 입력을 받음.
# min_value중에서 큰 수를 기존의 result와 비교한뒤에 새로운 result에 저장함
for i in range(n):
data = list(map(int, input().split()))
min_value = min(data)
result = max(result, min_value)
print(result)📍 [ 문제 2 ] 1이 될 때까지
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
- N에서 1을 뺀다.
- N을 K로 나눈다.
N과 K가 주어질 때, N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
✏️ [ 문제 ] 1이 될 때까지
문제: 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고한다. 단, 두 번째 연산은 N이 K로 나누어떨어 질 때만 선택할 수 있다.
while문을 사용하면 간편하게 해결 할 수 있었는데, 그 방법을 잘 몰랐던 문제다. while문으로 전체를 묶고 먼저, 거짓조건을 넣자. 이후에 참인 조건을 넣으면 되는 문제다.
n, k = map(int, input().split())
count = 0
# 전체 while문을 사용해서 거짓 조건으로 먼저 빼고 이후 참인 조건을 넣자.
# 마지막으로 남은 수는 1씩 빼기
while n >= k:
while n % k != 0:
n = n - 1
n = n / k
n = n / k
count = count + 1
while n > 1:
n = n - 1
count = count + 1
print(count)
✏️ 결론
알고리즘 문제를 풀다 for문을 응용할 수 있는 문제는 뭐가 있을까 하다 백준의 알고리즘 단계 중 for문을 전부 풀었다!
재밌었다.
어떻게 풀어나갈지 고민하는과정이 재밌었다.
그런데, 문제가 어려워지면 이런 고민도 바뀌겠지?? 🥲 🥲
끗
YW_Tech