이코테 CHAPTER 03 그리디 실전 문제

실전문제

숫자 카드 게임

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

1. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

카드들이 N x M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

 

• 나의 풀이

n, m = map(int,input().split())
min_n = []
for i in range(n):
    numbers = list(map(int,input().split()))

    min_n.append(min(numbers))

print(max(min_n))

- 숫자의 총 개수가 10,000개.. append와 max를 사용하면 쓸데없는 시간이 추가되는 느낌

- 예시 코드처럼 result로 매번 max 값으로 교체하는 게 조금 더 시간+공간이 줄어들 듯

- 시간복잡도 : append O(1), max O(n)

 

• 답안 예시 코드(min() 함수를 이용)

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

result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = min(data)
    # 가장 작은 수'들 중에서 가장 큰 수 챂기
    result = max(result, min_value)

print(result) # 최종 답안 출력

 

• 답안 예시 코드(2중 반복문 구조를 이용)

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

result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
    data = list(map(int/ input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result) # 최종 답안 출력

 

1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

 

• 나의 풀이

n, k = map(int,input().split())

cnt = 0

while n!=1:
    if n%k==0:
        n = n//k
    else:
        n -= 1
    cnt+=1

print(cnt)

- 답안 코드와 다른데, 제대로 작동하는 것인지 모르겠다ㅠ

- 그래도 5번 정도 확인했을 때는 제대로 정답이 나왔다.

 

• 답안 예시 코드(단순한 버전)

n, k = map(int,input().split())
result = 0

# N이 K 이상이라면 K로 계속 나누기
while n >= k:
	# N이 K로 나누어 떨어지지 않는다면 N에서 1 씩 빼기
	while n % k != 0:
		n -= 1
		result += 1
	# K로 나누기
	n //= k
	result += 1

# 마지막으로 남은 수에 대하여 1 씩 빼기
while n > 1:
	n -= 1
	result += 1

print(result)

 

• 답안 예시 코드
  • N이 100억 이상의 큰 수인 경우에도 빠르게 동작하는 코드
  • N이 K의 배수가 되도록 만들기

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

while True: 
	# (N == K로 나누어떨어지는 수)가 될 때까지 1 씩 빼기
	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)

 

 

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저