빠르게 산 오르기

빠르게산오르기.py

def select_stops(water_stops, capacity):
    # 여기에 코드를 작성하세요
    answer = []

    # 마지막으로 들른 약수터 위치
    last_stop = 0
    
    for i in range(len(water_stops)):
        # i 지점까지 갈 수 없으면, i - 1의 지점 약수터를 들른다.
        # (water_stops[i] - last_stop <= capacity 이런식으로 비교해버리면, 해당 코드가 모호해짐. 갈 수 없는 위치를 찾고 바로 전 위치가 최댓 값이라는 설정)
        if water_stops[i] - last_stop > capacity:
            answer.append(water_stops[i - 1])
            last_stop = water_stops[i - 1]
            
    # 마지막 약수터는 무조건 간다
    answer.append(water_stops[-1])
        
    return answer
            
         
# 테스트 코드
list1 = [1, 4, 5, 7, 11, 12, 13, 16, 18, 20, 22, 24, 26]
print(select_stops(list1, 4))

list2 = [5, 8, 12, 17, 20, 22, 23, 24, 28, 32, 38, 42, 44, 47]
print(select_stops(list2, 6))

 
해결과정
 
먼저 Brute Force 방식으로 풀면 어떻게 될까? 특정 약수터를 들를 수도 있고, 안 들를 수도 있기 때문에, 각 약수터에 대해서는 두가지 경우의 수가 있다. 총 약수터의 개수를 n개라하면, 모든 경우의 수는 2^n이 되기 때문에 시간 복잡도는 O(2^n)으로 굉장히 비효율적이다.
 

# 약수터 위치: [1km, 4km, 5km, 7km, 11km, 12km, 13km, 16km, 18km, 20km, 22km, 24km, 26km]
# 물통 용량: 4L
select_stops([1, 4, 5, 7, 11, 12, 13, 16, 18, 20, 22, 24, 26], 4)

위 예시를 살펴보면, 어느 약수터에서 물통을 채워야 할지 어떻게 알 수 있을까?
 
산 정상인 26km 지점에 도착할 때까지 물이 남아 있어야 할 텐데, 그러기 위해서는 최소 22km 지점 이후에 한 번 물을 채워야 한다. 우리의 경우 22km 지점이나 24km 지점에서 물을 채우면 된다.
 
그렇다면 26km 약수터에 가장 효율적으로 가는 방법은 이렇다.
 

1. 24km 약수터까지 최대한 효율적으로 가는 방법 + 26km 약수터
2. 22km 약수터까지 최대한 효율적으로 가는 방법 + 26km 약수터

이 두 방법 중 더 효율적인 방법을 선택하면 된다.
 
부분 문제의 최적의 솔루션을 이용해서 기존 문제의 최적의 솔루션을 구할 수 있기 때문에, 이 문제에는 최적 부분 구조가 있다.
 
최적 부분 구조가 있는 문제가 탐욕적 선택 속성까지 있다? ------> 바로 Greedy Algorithm으로 문제를 풀 수 있다.(이제 모르면 외우자 공식이야 ㅋㅋ)
 
그리디 알고리즘을 사용하려고 코드를 짰는데, 조건을 거리와 capacity와 비교했을때 그 거리가 capacity보다 작거나 같은걸 찾고 그 중 최댓값을 answer에 추가하는 방식으로 코드를 짜니 코드가 모호해지고 너무 복잡해졌다.
 

if water_stops[i] - last_stop <= capacity: # 내가 생각한 방법
if water_stops[i] - last_stop > capacity:

 
거리가 capacity보다 크면 그 아래 값을 추가하는 방식까지는 생각을 못했던 것 같다... 

알고리즘을 풀며 코드가 복잡해지면 뭐가 됐든 원하는 결과를 도출 해보고, 다른 방법과 반대경우도 생각을 해보는 것도 좋을 것 같다.