오늘의 학습 키워드
GREEDY 욕심쟁이!
그리디란?
- 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.
- 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있다.
- 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.
오늘의 문제
백준 27961번
https://www.acmicpc.net/problem/27961
입출력
그리디 적용해보기
목표 고양이 수에 도달하기 위해 그리디 접근으로 최소 행동 횟수 계산.
- 초기 상태 설정:
- 마도카의 집에 고양이가 0마리에서 시작한다. 최소한 한 마리의 고양이를 생성하기 위해 생성 마법을 사용한다. 따라서 처음에 고양이 수는 1이 된다.
- 현재 고양이 수를 current로 두고, 행동 횟수를 카운트하는 변수를 count로 설정하여 초기값을 1로 둔다.
- 목표 고양이 수 달성하기 위해 반복:
- 반복문을 사용하여 현재 고양이 수(current)가 목표 고양이 수(n)에 도달할 때까지 계속 복제 마법을 사용하여 고양이 수를 두 배로 늘려 나간다.
- 고양이 수가 목표에 도달할 때마다 count를 증가시켜 행동 횟수를 기록한다.
- 반복문 조건:
- while current < n: 현재 고양이 수가 목표 고양이 수보다 적을 경우 계속 반복한다.
- current *= 2: 현재 고양이 수를 복제하여 두 배로 늘린다.
- count += 1: 복제 마법을 사용할 때마다 행동 횟수를 증가시킨다.
- 결과 출력: 목표 고양이 수에 도달하면 반복을 종료하고 최종적인 행동 횟수를 출력한다.
그리디 탐색 순서 예시 (입력 예제 2 적용)
탐색 과정 (목표 고양이 수 6에 도달하기 위해 최소 행동 횟수 계산)
- 첫 번째 단계:
- 생성 마법을 사용하여 초기 고양이 수를 1마리로 만든다.
- 행동 횟수(count): 1.
- 두 번째 단계:
- 다시 생성 마법을 사용하여 고양이 수를 2마리로 만든다.
- 행동 횟수(count): 2.
- 세 번째 단계:
- 복제 마법을 사용하여 고양이 수를 4마리로 만든다.
- 행동 횟수(count): 3.
- 네 번째 단계:
- 다시 복제 마법을 사용하여 고양이 수를 6마리로 만든다.
- 행동 횟수(count): 4.
따라서 목표 고양이 수 6에 도달하기 위해 최소 행동 횟수는 4번이다.
1. 기본 설정 및 입력 처리
n = int(input())
current, count = 1, 1
if n == 0:
print(0)
exit()n = int(input()): 키우고자 하는 목표 고양이 수를 입력받는다.current, count = 1, 1: 초기 고양이 수를 1마리로 설정하고, 행동 횟수(count)를 1로 설정한다.if n == 0: 만약 목표 고양이 수가 0인 경우, 행동 횟수는 0이므로 바로 출력하고 종료한다.
2. 목표 고양이 수 달성하기 위한 반복
while current < n:
current *= 2
count += 13. 결과 출력
print(count): 목표 고양이 수에 도달했을 때 최소 행동 횟수를 출력한다.
왜 복제만 할까?
목표 고양이 수 N이 주어졌을 때 최적의 행동을 통해 목표에 도달하기 위함이다. 만약 N이 크면, 처음에 생성 마법을 이용하여 한 마리씩 고양이를 추가하는 것은 비효율적이다. 대신, 처음부터 1마리의 고양이로 시작한 후, 복제 마법을 사용하여 빠르게 고양이 수를 늘리는 것이 행동 횟수를 줄일 수 있기 때문에 코드에서는 복제 마법만 반복해서 사용하는 방식으로 구현한 것이다.
즉, 첫 1마리를 생성하고 나서 이후에는 복제만을 사용해 고양이 수를 두 배씩 늘려가도록 하여 최소한의 행동으로 목표 고양이 수를 달성하려고 한 것이다.
전체 풀이
n = int(input())
current, count = 1, 1
if n == 0:
print(0)
exit()
while current < n:
current *= 2
count += 1
print(count)오늘의 회고
🔥 Greedy는 이해가 가면서 가지 않는다. 그냥 최대한 출력값이 나오게 하는듯,.,? 문제를 더 적용해봐야될 듯..
