[알고리즘] 코드잇 - 빠르게 산 오르기(Python)

실습설명

신입 사원 장그래는 마부장님을 따라 등산을 가게 되었습니다.

 

탈수를 방지하기 위해서 1km당 1L의 물을 반드시 마셔야 하는데요. 다행히 등산길 곳곳에는 물통을 채울 수 있는 약수터가 마련되어 있습니다. 다만 매번 줄서 기다려야 한다는 번거로움이 있기 때문에, 시간을 아끼기 위해서는 최대한 적은 약수터를 들르고 싶습니다.

 

함수 select_stops()는 파라미터로 약수터 위치 리스트 water_stops와 물통 용량 capacity를 받고, 장그래가 들를 약수터 위치 리스트를 리턴합니다. 앞서 설명한 대로 약수터는 최대한 적게 들러야 겠죠.

 

(탈수로 인해서 정상에 도달하지 못하는 경우는 없다고 가정합니다.)

 

참고로 모든 위치는 km단위이고 용량은 L단위입니다. 그리고 등산하기 전에는 이미 물통이 가득 채워져 있으며, 약수터에 들르면 늘 물통을 가득 채운다고 가정합시다.

 

예시를 하나 볼게요.

# 약수터 위치: [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)

처음에 4L의 물통이 채워져 있기 때문에, 장그래는 약수터에 들르지 않고 최대 4km지점까지올라갈 수 있습니다. 탈수 없이 계속 올라가기 위해서 1km지점이나 4km 지점에서 물통을 채워야겠죠?

 

최대한 적은 약수터를 들르면서 올라가야 하고, 마지막에 산 정상인 26km 지점의 약수터를 들르면 성공적인 등산입니다.

 

실습결과

[4, 7, 11, 13, 16, 20, 24, 26]
[5, 8, 12, 17, 23, 28, 32, 38, 44, 47]

힌트1

Brute Force 방식으로 풀면 어떻게 될까요?

 

특정 약수터를 들를 수도 있고 안 들를 수도 있기 때문에, 각 약수터에 대해서는 두가지 경우의 수가 있습니다. 총 약수터 개수(리스트 water_stops의 길이)를 n이라고 하면, 모든 경우의 수는 2^n입니다.

 

물통이 텅텅 빈 상태로는 더 이상 나아갈 수 없다는 제약을 고려하면, 그 2^n개의 경우 중에 실제로 가능한 몇 개를 추려낼 수 있을텐데요. 그중에서 가장 짧은 리스트를 고르면 정답을 구할 수 있습니다.

 

하지만 이 방법은 O(2^n)으로 굉장히 비효율적이죠?

 

힌트2

# 약수터 위치: [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 약수터

이 두방법중 더 효율적인 방법을 선택하면 되겠네요.

 

부분 문제의 최적의 솔루션을 이용해서 기존 문제의 최적의 솔루션을 구할 수 있기 때문에, 이문제에는 최적 부분 구조가 있습니다.

 

힌트3

최적 부분 구조가 있는 문제가 탐욕적 선택 속성까지 있다면 Greedy Algorithm으로 문제를 풀 수 있습니다. 

 

혹시 이문제에 탐욕적 선택 속성이 있는지 고민해보세요.

 

힌트4

# 약수터 위치: [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)

처음 등산길에 오를 때, 물이 다 떨어지기 전에 갈 수 있는 약수터는 1km지점과 4km 지점 입니다. 두 약수터 중 어디서 채우는게 더 좋은 선택일까요?

 

1km 지점에서 물을 채우면, 다음 갈 수 있는 약수터는 4km지점과 5km지점입니다. 4km 지점에서 물을 채우면 다음 갈수 있는 약수터는 5km지점이나 7km 지점입니다. 1km 지점과 4km 지점 중 어디로 가는게 좋을까요?

 

1km 지점에서 갈 수 있는 약수터는 모두 4km 지점에서도 갈 수 있습니다. 따라서 1km 지점에서 물통을 채울 이유가 전혀 없죠.

 

항상 가능한 먼 약수터로 가는 것이 가장 좋은 선택이라고 확신할 수 있기 때문에, 이문제에는 탐욕적 선택 속성이 있습니다. 따라서 이 문제는 Greedy Algorithm을 이용해서 효율적으로 해결 할 수 있는거죠!

 

답안

def select_stops(water_stops, capacity):
    # 약수터 위치 리스트
    stop_list = []

    # 마지막 들른 약수터 위치
    prev_stop = 0

    for i in range(len(water_stops)):
        # i 지점까지 갈 수 없으면, i - 1 지점 약수터를 들른다
        if water_stops[i] - prev_stop > capacity:
            stop_list.append(water_stops[i - 1])
            prev_stop = water_stops[i - 1]

    # 마지막 약수터는 무조건 간다
    stop_list.append(water_stops[-1])

    return stop_list


# 테스트 코드
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))