[TIL] 99클럽 코테 스터디 13일차 TIL - 이진탐색 : 백준 10561 징검다리 문제 풀이 with python

Today's keyword : 그리디

그리디 알고리즘(Greedy Algorithm)은 문제를 해결하는 과정에서 매 단계에서 가장 최적이라고 생각되는 선택을 하는 방법입니다. 즉, 현재 상황에서 가장 좋은 선택을 하여 최종적인 해답에 도달하는 방식입니다. 그리디 알고리즘은 다음과 같은 특징을 가지고 있습니다

 

• 최적 부분 구조: 문제의 최적 해는 부분 문제의 최적 해로 구성됩니다. 즉, 문제를 해결하기 위해 선택한 부분 해가 전체 문제의 최적 해에 기여합니다.
• 탐욕적 선택 속성: 각 단계에서의 선택이 이후의 선택에 영향을 미치지 않으며, 각 단계에서 최적의 선택을 하여 전체 문제를 해결할 수 있습니다.

 

 

 

 

 

 

이 문제가 왜 그리디 알고리즘에 속하는가?

마도카의 고양이 문제는 그리디 알고리즘의 특성을 잘 보여주는 예입니다. 이 문제에서 그리디 알고리즘이 적용되는 이유는 다음과 같습니다

 

1. 탐욕적 선택 속성:

 

• 매 단계에서 현재 고양이 수 k를 목표 수 n에 도달하기 위해 가장 최적이라고 생각되는 선택을 합니다.
• 현재 고양이 수가 목표 수보다 작을 때는 복제 마법을 사용하여 고양이 수를 두 배로 늘리는 것이 최적의 선택입니다. 이는 가능한 한 많은 고양이를 빠르게 늘리는 방법입니다.
• 현재 고양이 수가 목표 수보다 크거나 같을 때는 생성 마법을 사용하여 고양이 수를 1 증가시키는 선택을 합니다. 이는 목표 수에 도달하기 위한 마지막 단계입니다.

2. 최적 부분 구조:

 

• 문제의 최적 해는 부분 문제의 최적 해로 구성됩니다. 즉, 현재 고양이 수를 두 배로 늘리는 선택이 이후의 선택에 영향을 미치지 않으며, 각 단계에서의 선택이 전체 문제의 최적 해를 보장합니다.
• 예를 들어, 현재 고양이 수가 3이고 목표 수가 10이라면, 3을 두 배로 늘려 6으로 만들고, 다시 두 배로 늘려 12로 만드는 것이 최적의 선택입니다. 이후에는 생성 마법을 사용하여 10에 도달할 수 있습니다.

 

 

 

 

📌 문제설명

https://www.acmicpc.net/problem/27961

📌 문제풀이

이 문제에서 핵심은 최소한의 행동 횟수로 N마리의 고양이를 만든다는 것입니다. 최소 행동을 하기 위해서는 생성 마법보다 복제 마법을 이용해야 합니다. 복제 마법이 0에서 k마리 이하의 고양이를 자유롭게 복제할 수 있기 때문에 처음 생성 마법을 제외하고는 계속 복제마법을 사용하는 것이 최소한의 행동으로 N마리를 만드는 방법입니다. 

# 백준 : 고양이는 많을수록 좋다 
count = 0 
n = int(input())  # 목표 고양이 수 
k = 0  # 현재 고양이 수 
if n == 0: 
    print(0)
    exit()
    
# 생성 
k += 1
count += 1
while True: 
    if k >= n :
        print(count) 
        break 
    k += k 
    count += 1

1. 변수 초기화 : 행동 횟수 count, 현재 고양이 수 k 를 각각 0으로 초기화를 합니다. 

2. 특별한 경우 (N = 0) 처리 : 목표 고양이 수가 0일 때는 아무것도 행동하지 않으므로 0을 출력합니다. 

3. 생성 마법 사용 : 복제 마법 전 고양이를 1마리 생성합니다. 

4. N에 도달할 때까지 반복문 실행 : 현재 고양이 수 K가 N에 도달할 때까지 현재 고양이 수를 k마리 씩 복제하고 행동 횟수를 추가하는 반복문을 실행합니다. 

5. 결과 출력 : 현재 고양이 수가 N마리 이상이면 최종 행동 횟수를 출력합니다. 복제하는 마리 수가 k 이하로도 가능하기 때문에 이상일 경우에는 마지막에 N마리에 맞춰 복제하면 되기 때문에 N을 넘는 조건만으로도 답을 구할 수 있습니다. 

📌 오늘의 회고 

그리디 알고리즘이 아직 명확하게 와닿진 않지만 조건에 맞춰서 문제를 푸는 방식을 쉽게 느껴진다. 

 

 

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL