[알고리즘] 이코테(1) - 그리디 & 구현

 

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/2zjoKjt97vQ?si=VgYo4fBNuccHh7P5

---

그리디

chatGPT가 생각하는 그리디

정의

현재 상황에서 지금 당장 좋은 것만 선택하는 알고리즘.

정당성 분석이 선행되어야 한다.
--> 단순하게 가장 좋아보이는 것만 선택하면, 최적의 해를 구할 수 있는지?

 

실제로 유형을 모른 채로 문제를 만났을 때, 그리디 알고리즘을 사용해야 하는 근거는 다음과 같다.

 

1. 문제의 구조:

• 최적 부분 구조: 작은 문제의 최적 해결책이, 전체 문제에도 적용될 수 있어야 함.

2. 선택의 기준:

• 탐욕적: 현재 정보에 한해, 제일 좋은 것을 선택.
• 단기적: 각 선택은 현재 정보만을 기반으로 이루어짐. 이전 혹은 미래의 선택을 고려하지 않음.
• 불가역적: 선택이 이루어지고 나면, 이후의 과정에서 그 선택을 되돌릴 수 없음. 모든 선택은 최종 선택임.

 

1. 거스름 돈

큰 단위가 항상 작은 단위의 배수이므로 최적의 해를 보장한다.
예: [500, 400, 100]이라면, 큰 단위(500)가 작은 단위(400)의 배수가 아니므로, 그리디를 적용할 수 없다.

 

2. 1이 될 때까지

1빼기 보다, 나누기를 많이 하는 것이 대부분의 상황에서 유리하다.

현재 값이 2이상이면 나누는 것이 1 빼는 것보다 빠르게 조건을 달성할 수 있으니까.

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

result = 0

while True:
    target = (n // k) % k # n과 가장 가까우면서 작은 k로 나누어 떨어지는 수
    result += (n - target) # 어차피 1씩 빼면서 target까지 가야한다. 그것을 한 번에.
    
    n = target # 1씩 빼서 target까지 도착했다고 치고
    
    if n < k: # 나누는 수보다 작아지면 탈출
        break
        
    result += 1
    n //= k # while을 한 번 반복할 때마다, k로 한 번씩 나누는 셈

result += (n - 1) # 더 이상 나눌 수 없는 상태이므로, 1씩 빼서 1에 도착할 때까지 횟수
print(result)

 

3. 곱하기 혹은 더하기

피연산자가 1 또는 0이 아니라면 항상 곱하기가 유리하다.

 

4. 모험가 길드

배열을 정렬하고, 작은 값부터 임시 그룹에 추가하며, 조건을 만족하는 즉시 마을을 떠나면 최적의 해를 구할 수 있다.

 

그리디 알고리즘을 적용해야 하는지 헷갈릴 수 있다.

그리디 알고리즘 선택 근거를 다시 생각해보자.

 

1. 문제의 구조: [1]인 경우와 [1, 2, 3]인 경우, 모두 같은 풀이를 적용할 수 있다.

2. 선택의 기준: [1]인 경우와 [1, 2, 3]인 경우, 탐욕적으로 선택해도 최적의 해가 나온다. 각 선택은 단기적이고 불가역적이다. 

 

 

구현

chatGPT가 생각하는 구현

 

정의

풀이를 떠올리는 것은 쉽지만 소스 코드로 옮기기 어려운 문제

1. 알고리즘은 간단한데 코드가 지나칠 정도로 길어짐
2. 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 함
3. 문자열을 다룸
4. 적절한 라이브러리를 찾아서 사용해야 함

 

1. 상하좌우

방향 벡터를 사용한 문제.

행렬의 시작 부분인 (0, 0)이 좌상단 임을 기억할 것.

 

2. 시각

h = int(input())

count = 0

for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            if "3" in str(i) + str(j) + str(k): # 이렇게 하면 쉽다.
                count += 1

print(count)

 

완전 탐색.

하루는 86,400초이므로 완탐을 하기에 무리 없다.

파이썬은 1초에 2,000만 번 정도 연산을 수행할 수 있다고 생각하기.

 

3. 왕실의 나이트

8방향 벡터.

 

4. 문자열 재정렬

data = input()
result = []
value = 0

for x in data:
    if x.isalpha(): # 문자면 True 아니면 False # isNumeric()도 있음
        result.append(x)
    else:
        value += int(x)

result.sort()

if value != 0: # 숫자가 없을 경우 표시하면 안 되니까
    result.append(str(value))

print("".join(result)) # 리스트의 원소를 합쳐서 문자열로 만드는 방법