신입 사원 장그래는 마부장님을 따라 등산을 가게 되었습니다.
탈수를 방지하기 위해서 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 지점의 약수터를 들르면 성공적인 등산입니다.
내 코드:
def select_stops(water_stops, capacity):
# 코드를 작성하세요.
result = []
level = 0
i = 0
while level < water_stops[len(water_stops)-1]:
if level + capacity >= water_stops[len(water_stops)-1]:
result.append(water_stops[len(water_stops)-1])
return result
level += capacity
while water_stops[i] <= level:
i += 1
level = water_stops[i-1]
result.append(level)
# 테스트
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))(N + 1)의 크기인 리스트에, 1부터 N까지의 임의의 자연수가 요소로 할당되어 있습니다. 그렇다면 어떤 수는 꼭 한 번은 반복되겠지요.
예를 들어 [1, 3, 4, 2, 5, 4]와 같은 리스트 있을 수도 있고, [1, 1, 1, 6, 2, 2, 3]과 같은 리스트가 있을 수도 있습니다. (몇 개의 수가 여러 번 중복되어 있을 수도 있습니다.)
이런 리스트에서 반복되는 요소를 찾아내려고 합니다.
중복되는 어떠한 수 ‘하나’만 찾아내도 됩니다. 즉 [1, 1, 1, 6, 2, 2, 3] 예시에서 1, 2를 모두 리턴하지 않고, 1 또는 2 하나만 리턴하게 하면 됩니다.
중복되는 수를 찾는 시간 효율적인 함수를 설계해보세요.
내 코드:
def find_same_number(some_list):
# 코드를 쓰세요
inlist = []
for num in some_list:
if num in inlist:
return num
else:
inlist.append(num)
# 중복되는 수 ‘하나’만 리턴합니다.
print(find_same_number([1, 4, 3, 5, 3, 2]))
print(find_same_number([4, 1, 5, 2, 3, 5]))
print(find_same_number([5, 2, 3, 4, 1, 6, 7, 8, 9, 3]))저번 챕터에서 sublist_max 함수를 Brute Force 방식으로 작성했습니다. 이번에는 같은 문제를 Divide and Conquer 방식으로 풀어볼 텐데요. 시간 복잡도는 O(n\lg{n})O(nlgn)이 되어야 합니다.
이번 sublist_max 함수는 3개의 파라미터를 받습니다.
profits: 며칠 동안의 수익이 담겨 있는 리스트 start: 살펴볼 구간의 시작 인덱스 end: 살펴볼 구간의 끝 인덱스 sublist_max는 profits의 start부터 end까지 구간에서 가능한 가장 큰 수익을 리턴합니다.
합병 정렬을 구현할 때 merge_sort 함수를 깔끔하게 작성하기 위해 추가로 merge 함수를 작성했던 것 기억 나시나요? 마찬가지로 퀵 정렬을 구현할 때 quicksort 함수에 추가로 partition 함수를 작성했습니다. 이번에도 sublist_max 함수에 추가로 새로운 함수를 작성하면 도움이 되실 겁니다.
생각:
이 문제를 divide & conquer 방식으로 푼다?
divide & conquer 는 divide > conquer > combine 의 과정으로 진행된다.
그럼 divide 를 생각해보면
이 문제를 쪼개는데 그 부분 문제가 이 문제와 유사해야 한다.
일단 이 문제가 뭘 구하는 거였지?
살펴볼 구간 안에서 가장 수익이 큰 구간을 찾는 거였다.
그럼 만약 구간을 두 개로 쪼갠다면?
"쪼갠 부분 구간에서 가장 수익이 큰 구간을 찾는 것"이 "전체 구간에서 가장 수익이 큰 구간을 찾는 것"과 어떤 관련이 있지?
(!)
두 개로 쪼갰다면 2가지 케이스가 나온다.
1. 정답인 구간이 두 개로 쪼개져서 왼쪽 구간의 최대구간 마지막 인덱스와 오른쪽 구간의 최대구간 시작 인덱스가 연결될 경우
2. 연결되지 않을 경우 - 이 경우에 두 최대구간의 수익을 비교하면 된다.
그렇다면 이 과정을 코드로 구현하기만 하면 된다.
함수를 추가한다면 어떤 함수를 추가하는 게 좋을까?
계속 반복될 작업이 무엇이 있지?
최대구간을 찾는 작업은 재귀적으로 구현될 것이기 때문에 아니다.
2가지 케이스 구분하고 처리하는 작업?
일단 해보자.
음...코드로 구현하는 부분이 어렵다.