Untitled

Fold the Video

13강 그리디 알고리즘 유형 문제 풀이

n은 1이상 10만이하의 수고 k는 2이상 10만 이하의 수임

나누면 되는 겁니다

우리는 n이 k로 나누어 떨어질때 이 n을 k로 나눌수가 있다고 했음 따라서 나누어 떨어진다면 그때마다 바로 나누기를 우선적으로 수행하면 되는 것입니다

1을 빼는 방식을 반복하면 되겠죠 이제 이러한 아이디어가 성립할수 있는 이유는

n의 값을 줄때 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 훨씬 빠르게 수를 줄일수 있기 때문입니다

예를 들어 n이 100이라하고 k가 5라고 해볼게요 이때 5로 나눈다면 한번에 20이 되겠지만 1을 빼는 경우에는 n은 99로 얼마 줄어들지 않게 되는 것임

다른 예시로는 n이 25 k가 3일때 위 처럼 확인가능함

나눌수 있도록 하는 겁니다 이게 항상 옵티멀(최선의, 최상의)한 솔루션을 보장할수 있는 이유는 무엇일까요

문제의 조건상 k가 항상 2이상의 수이기 때문에 n이 아무리 큰수라고 해도 그냥 k로 계속해서 나누기만 한다면 기아 급수적으로 빠르게 줄일수 있기 때문입니다.

즉 문제의 조건에 해당하는 n과 k에 대해서 항상 k로 나누는 것이 이를 빼는 것 보다 빠르게 n을 줄일수 있기 때문에 이러한 아이디어가 최적의 이를 보장할 수 있습니다.

또한 결과적으로 n은 항상 k에 도달할수 있습니다 애초에 n이 양의 정수라는 가정하에 n을 그냥 1씩 뺀다면 언젠가는 n이 1로 바뀌겠죠 그렇기 때문에 n이 항상 1이 될수 있다는 것 또한 자명합니다(설명하거나 증명하지 아니하여도 저절로 알 만큼 명백하다.)

내가 작성한 코드 (시간때문에 풀다가 완성못함)

"""

수행 시간 측정 소스코드 예제

일반적인 알고리즘 문제 해결 과정은 다음과 같습니다.

import time

start_time = time.time() # 2Y |

# 프로그램 소스코드

end_time = time.time() #

print("time:", end_time - start_time) # +

알고리즘 성능 평가

"""

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

total = 0

while n == 1:

if n > k and n % k == 0 :

n = n / k

total += 1

else:

n = n - k

total += 1

print(total)

<문제> 1이 될 때까지: 답안 예시 (Python)
# N, K을 공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())
result = 0
while True:
# N이 K로 나누어 떨어지는 수가 될 때까지 빼기
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)
그리디 알고리즘

문자열을 공백기준으로 나눈 뒤에 맵함수를 이용해서 각각 인트 즉 정수로 바꾼 뒤에

n과 k에 넣은 것을 확인할 수 있습니다.

먼저 target이라는 변수에다가 n을 k로 나눈 몫의다가 다시 k를 곱한 값을 넣어줍니다

이렇게 해주게 되면 만약에 n이 k로 나누어 떨어지지 않는다고 했을때 가장 가까운 k로 나누어 떨어지는 수가 어떤건지를 찾고자 할때 사용 할수 있는겁니다

즉 우리는 n에서 1을빼는 과정을 몇번 반복해서 이 target이라는 값까지 만들수가 있고 이 target이라는 값은 k로 나누어 떨어지는 수가 되겠습니다

자 그래서 이렇게 타겟을 구한뒤에 이어서 이 result 라는 변수가 우리가 총 연산을 수행하는 횟수라고 할수 있는데 이렇게 일을 빼는 연산을 몇번 수행 할지 한번에 계산해서 넣어주는 겁니다 그래서 이렇게 일을 빼는 연산 횟수를 한번에 더해주고 이제 n이 target이 될수 있도록 만듭니다 ( n = target)

n을 k로 나눌수 있도록 하면 되는 것입니다 이렇게

result += 1

n //= k

이렇게 k로 나누는연산 한번 수행하기 때문에 result에다가 1을 더해주는걸 확인할수 있고요

그래서 결과적으로 n이 k보다 작아졌을때 탈출 하게 되고 우리는 이제 n이 1보다 크다면 1이될수 있도록 만들기 위해서 남은 수에 대래서 1씩 빼는 연산을 이렇게 한번에 또 계산 할수가 있는 것입니다

result += (n-1)

print(result)

다만 이제 이문제같은 경우는 문제조건을 확인해 보시면 이n과 k가 10만 이하의 정수이기 때문에 사실 이렇게 작성하지 않고 그냥 매번 n을 확인해서 n이 k로 나누어 떨어진다면 나눠주고 그렇지 않다면 일을 빼주고 하는 방식으로 간단하게도 작성할수가 있는데요

n이 k로 나누어 지는 연산

n이 빠르게 로그 시간복잡도가 나올수가 있는것

백억 천억이 넘어가는 매우 큰수

자 이어서 c++로도 마찬가지의 로직을 이용해서 문제를 해결할수 있습니다

이렇게 와일 문을 통해서 n이 k로 나누어 떨어지는 수가 될때까지 1씩 뺼수 있도록 만드는 거고 n이 k의 배수가 되었을때 k로 나눌수 있도록 합니다

그래서 결과적으로 이렇게 반복문을 탈출한 이후에 최종적으로 n이 1이 될수 있을때까지 1번 연산을 반복하면 되는것입니다.

그래서 이렇게 소스코드만 c++ 형식으로 작성이되었고 실직적인 로직은 완전히 동일한것을 확인할수 있습니다

입력을 받아서 초기화를 해주고요 이어서 동일한 로직을 반복하는걸 확인할수 있습니다

연산자를 끼워 넣으면서

문자열이 들어왔을때 먼저 더하고 그다음에 곱하고 그럼 이제 여기가

18이 될것임 ((0+2)x9)

알수 있습니다

또한 가장 큰수는 항상 20억 이하의 정수가 되도록 입력이 주어진다고 하네여 이제 이렇게 입력이 주어지는 이유는 일반적인 프로그래밍 언어에서 정수 데이터를 위해 기본 int형을 사용할 경우 약 21억정도 까지 값이 형성될 수 있기 때문에 그런점을 감안하고 이렇게 문제에서 최대값을 명시해 준거라고 볼수 있습니다

예를 들어서 이렇게 모든 숫자가 다 9로 이루어지고 곱하기만 들어간다고 하면 20억보다 더 큰수가 만들어 질 수 있겠죠 그렇기 때문에 이러한 조건도 주어진거라고 예상할 수 있습니다.

사실

없을 테지만 c++ java와 같은 다른 프로그래밍 언어를 사용하는 분들도 배려를 한 문제라고 보시면 되겠습니다

자 이문제를 어떻게 해결할 수 있을까요 마찬가지로 각자 개인적으로 문제를 풀어보시고 코드 작성까지해보세요

내가 쓴 코드 (틀렸음 결과값에서 오류남)

n = list(map(int, input()))

result = 0

print(n)

total = 0

for i in range(len(n)):

print(i)

if n[i] == 0 or n[i+1] == 0:

total += n[i] + n[i+1]

if n[i] == 1 or n[i+1] == 1:

total += n[i] + n[i+1]

else:

total += n[i] * n[i+1]

print(total)

연산

예를 들어 5+6 은 11일이지만 5*6은 32조 물론 이때도 예외가 있는데요

0 혹은 1인 경우에는

두수 중에서 하나라도 0이거나 1인경우에는 더하기를 수행 할수 있도록 하면 될것임

수행하는 두수 중에서 더하고

두수가 모두 2 이상인 경우에는 곱하면 정답 처리를 받을수 있을 겁니다

<문제> 곱하기 혹은 더하기: 답안 예시 (Python)
data = input()
# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])
for i in range(1, len(data)):
#두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
num = int(data[i])
if num <= 1 or result <= 1:
result += num
else:
result *= num
print(result)
그리디 알고리즘

숫자로

이 result 변수의 값과

0혹은1인경우

곱하기 보다는 더하기를 수행하고 그렇지 않다면 곱하기를 수행하는것을 반복하는 것을 확인할 수 있습니다 즉 현재 상태에서 이러한 조건이 맞다면 더하기를 수행하고 그렇지 않다면

c++, java로직으로 문제를 풀 수있습니다

자 이렇게 c++에서는 기본적으로 문자열 형태로 입력을 받은 뒤에 이제

리절트에 대입할 수 있습니다

더하기를 수행하고 곱하기를 수행하는 걸

스트링 (str)

charAt(케릭터 엣) 이라는 메서드를 호출 하는 것을 확인할 수 있습니다

마찬가지로 c++과 동일하게 이 0을 문자로

첫번째 문자의 숫자를 리절트 에 담을수 가 있고요 그래서 마찬가지 로직으로

두수에 대해서 매번 연산을 수행할때 곱하기를 수핼할지 +를 수행할지 이 조건에 다라서 결정하는 걸 확인 할 수 있습니다

모험가 길드

모험가 길드 뒤에는 n명의 모험가가 존재 n명에 모험가는 각각 공포도를 가지고 있다고함 이때 이n명의 모험가 중에서 여러그룹을 만들려고 하는데요 모험가 그룹을 결성할때는 공포도가 x인 모험가는 반드시 x명

모험가

그룹수의

이문제는 어떻게 볼수 있을까여?

예를들어 n이 5이고 각 모험가의 공포도는

넣게

조건상에 몇몇의 모험가는

시간 제한은 1초 메모리 제한 128메가 그리고 첫째줄의 모험가의 수 n이 주어지고

각 모험가에 대한 공포도 값을 차례대로 공백을 기준으로 해서 주어지는 걸 확인 할수 있습니다

n = int(input())

m = list(map(int, input().split()))

print(m)

Max = (m[0])

# Max = 0

t = int(m[0])

for i in range(1, len(m)):

if Max <= m[i]:

Max = m[i]

print(Max)

"""

if max => t + n[i]:

total = 1

total =

"""

# 최대 값을 찾고 다시 원소들 중에서 2개 씩 비교해 최대값 보다 작으면 1나씩

# 그룹을 만들려고 했음 2개 비교한거 제거한다음

그럼 이제 이어서 해설을 해보겠습니다.

자 이 문제는

포함된 무언가의 수가

같다면 바로 그룹을 결성해서 여행을 보낼수 있도록 하면 되는 것입니다

모험가의 수는 한명이지만

이렇게 2이기 때문에

네번째 모험가 다섯번째 모험가는 매번 확인할때 그 그룹에 포함되어 있는 모험가의 수가 현재 확인하고 있는 모험가에 공포도 보나 더작기 때문에

#<문제> 모험가 길드: 답안 예시 (Python)
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) #총 그룹의 수 출력