오늘의 학습 키워드
GREEDY 욕심쟁이!
그리디란?
- 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.
- 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있다.
- 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.
오늘의 문제
백준 31926번
https://www.acmicpc.net/problem/31926
입출력
문제 접근해보기
이 문제에서는 daldidalgo라는 문자열이 총 N번 반복되고 마지막에 daldidan으로 끝나는 형태로 문자열을 입력한다. 가능한 두 가지 작업이 있다:
- 알파벳 하나씩 입력하는 방식.
- 이미 작성된 부분 문자열을 복사 후 붙여넣는 방식.
문제의 목표는 주어진 작업을 통해 전체 문자열을 가장 빠르게 입력할 수 있는 최소 시간을 구하는 것이다.
그리디 접근 방식을 통해 반복적인 구조를 최대한 활용하여 빠르게 문자열을 완성할 수 있는 방법을 찾는다.
1. 기본 설정 및 입력 처리
count = 8
n = int(input())count = 8: daldidalgo 문자열의 길이는 8이다. 따라서 처음 기본 문자열의 길이는 8로 설정.n = int(input()): 반복할 횟수 n을 입력.
2. 문자열 입력 반복문
i = 1
while True:
if n - (2**i) == 0:
count = count + i + 2
break
elif n - (2**i) < 0:
count = count + i + 1
break
i += 1i = 1: 복사 후 붙여넣기를 몇 번 할지를 추적하기 위한 변수 i를 초기화.while True: 반복문을 통해 n번의 반복을 완료할 때까지 문자열을 구성.if n - (2**i) == 0: 현재 남은 반복 횟수가 2의 제곱수와 일치하면 count를 조정하고 반복문을 종료. 여기서 i는 현재까지 몇 번의 복사/붙여넣기를 했는지를 나타냄.count = count + i + 2: 현재까지의 복사 횟수 i와 추가 작업을 고려하여 count 값을 갱신.elif n - (2**i) < 0: 현재 남은 반복 횟수가 2의 제곱수를 초과하는 경우, 반복 횟수를 고려하여 count를 갱신하고 반복을 종료.count = count + i + 1: 복사 횟수를 고려하여 count 값을 조정.i += 1: 복사 횟수를 늘림.
3. 결과 출력
print(count): 최소 작업 횟수를 출력
그리디 적용해보기 (입력 예제1 적용)
- 초기 상태: count = 8 (기본 문자열 daldidalgo의 길이)
- 첫 번째 반복
(i = 1): n - (2**i)가 0보다 큼 (n = 2, 2**1 = 2). count는 11이 됩니다. - 최종 결과: count = 11
왜 그리디로 풀까?
-
이 문제는 매 순간 최적의 선택을 반복하여 전체 작업을 최소화하는 것을 목표로 함. 복사/붙여넣기를 통해 빠르게 문자열을 완성하기 위해 최대한 반복 가능한 부분을 효율적으로 복사하는 것이 중요.
-
따라서 매 순간 가능한 최선의 작업을 반복함으로써, 전체 입력 작업 횟수를 최소화하는 방법으로 문제를 해결하기 위해 그리디 알고리즘을 사용.
전체 풀이
import sys
input = sys.stdin.readline
count = 8
n = int(input())
i = 1
while True:
if n - (2**i) == 0:
count = count + i + 2
break
elif n - (2**i) < 0:
count = count + i + 1
break
i += 1
print(count)오늘의 회고
🔥 그리디로 푸는 것은 여전히 헷갈린다 복습해봐야겠다.
