런던에 엄청난 폭우가 쏟아진다고 가정합시다. 정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도입니다.
그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 trapping_rain()을 작성해 보려고 합니다.
함수 trapping_rain()은 건물 높이 정보를 보관하는 리스트 buildings를 파라미터로 받고, 담기는 빗물의 총량을 리턴해 줍니다.
예를 들어서 파라미터 buildings로 [3, 0, 0, 2, 0, 4]가 들어왔다고 합시다. 그러면 0번 인덱스에 높이 3의 건물이, 3번 인덱스에 높이 2의 건물이, 5번 인덱스에 높이 4의 건물이 있다는 뜻입니다. 1번, 2번, 4번 인덱스에는 건물이 없습니다.
그러면 아래의 사진에 따라 총 10 만큼의 빗물이 담길 수 있습니다. 따라서 trapping_rain() 함수는 10을 리턴하는 거죠.
3차원 말고, 2차원으로 생각해 주세요! 이번에는 파라미터 buildings로 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]가 들어왔다고 합시다. 그러면 아래의 사진에 따라 총 6 만큼의 빗물이 담길 수 있습니다. 따라서 trapping_rain() 함수는 6을 리턴하는 거죠.
리스트 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
이 정보를 기반으로, trapping_rain() 함수를 작성해 보세요!
더 많은 공간을 쓰더라도 조금 더 효율적인 시간 복잡도로 문제를 풀어 볼까요?
실습 결과
def trapping_rain(buildings):
total_height = 0 # 총 갇히는 비의 양을 담을 변수
n = len(buildings)
# 각각 왼쪽 오른쪽 최대값 리스트 정의
left_list = [0] * n
right_list = [0] * n
# buildings 리스트 각 인덱스 별로 왼쪽으로의 최댓값을 저장한다
left_list[0] = buildings[0]
for i in range(1, n):
left_list[i] = max(left_list[i-1], buildings[i-1])
# buildings 리스트 각 인덱스 별로 오른쪽으로의 최댓값을 저장한다
right_list[-1] = buildings[-1]
for i in range(n - 2, -1, -1):
right_list[i] = max(right_list[i+1], buildings[i+1])
# 저장한 값들을 이용해서 총 갇히는 비의 양을 계산한다
for i in range(1, n-1):
# 현재 인덱스에 빗물이 담길 수 있는 높이
upper_bound = min(right_list[i], left_list[i])
# 현재 인덱스에 담기는 빗물의 양을 계산
# 만약 upper_bound가 현재 인덱스 건물보다 높지 않다면, 현재 인덱스에 담기는 빗물은 0
total_height += max(0, upper_bound - buildings[i])
return total_height
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
(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 하나만 리턴하게 하면 됩니다.
이번 과제에서는 두 가지의 제약이 있습니다.
O(n)이상의 공간을 사용할 수 없습니다. 즉 사전이나 리스트와 같이 인풋 리스트의 길이에 비례하는 공간 저장 도구를 사용할 수 없습니다!
인풋으로 받는 리스트 some_list의 요소들을 바꾸거나 변형할 수 없습니다.
실습 결과
def find_same_number(some_list, start = 1, end = None):
if end == None:
end = len(some_list)
# 반복 요소를 찾으면 리턴한다
if start == end:
return start
# 중간 지점을 구한다
mid = (start + end) // 2
# 왼쪽 범위의 숫자를 센다. 오른쪽은 리스트 길이에서 왼쪽 길이를 빼면 되기 때문에 세지 않는다
left_count = 0
for element in some_list:
if start <= element and element <= mid:
left_count += 1
# 왼쪽과 오른쪽 범위중 과반 수 이상의 숫자가 있는 범위 내에서 탐색을 다시한다
if left_count > mid - start + 1:
return find_same_number(some_list, start, mid)
return find_same_number(some_list, mid + 1, end)
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]))
영훈이는 출근할 때 계단을 통해 사무실로 가는데요. 급할 때는 두 계단씩 올라가고 여유 있을 때는 한 계단씩 올라갑니다. 결국 계단을 오를 수 있는 모든 방법으로 계단을 올라갔는데요.
이제 다르게 계단을 올라갈 수는 없을까 고민하던 영훈이는 특이한 방법으로 계단을 오르려고 합니다.
가령 계단을 한 번에 1, 2, 4 칸씩 올라가 보는 건데요. 예를 들어서 계단을 4개를 올라가야 되면:
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
4
총 6개 방법이 있네요.
함수 설명
함수 staircase()는 파라미터로 총 계단 수 n 그리고 한 번에 올라갈 수 있는 계단 수를 possible_steps로 받고, 올라갈 수 있는 방법의 수를 효율적으로 찾아서 리턴합니다.
그러니까 n이 3, possible_steps 가 [1, 2, 3]이면, 계단 총 3칸을 1, 2, 3칸씩 갈 수 있을 때 오르는 방법의 수를 구하는 거죠. 단, possible_steps에는 항상 1이 포함된다고 가정합니다.
실습 결과
# 높이 n개의 계단을 올라가는 방법을 리턴한다
def staircase(stairs, possible_steps):
# 계단 높이가 0 이거나 1 이면 올라가는 방법은 한 가지밖에 없다
number_of_ways = [1, 1]
# 이 변수들을 업데이트해 주며 n 번째 계단을 오르는 방법의 수를 구한다.
for height in range(2, stairs + 1):
number_of_ways.append(0)
for step in possible_steps:
# 음수 계단 수는 존재하지 않기 때문에 무시합니다
if height - step >= 0:
number_of_ways[height] += number_of_ways[height - step]
return number_of_ways[stairs]
print(staircase(5, [1, 2, 3]))
print(staircase(6, [1, 2, 3]))
print(staircase(7, [1, 2, 4]))
print(staircase(8, [1, 3, 5]))
def staircase(n):
a, b = 1, 1
for i in range(n):
a, b = b, a + b
return a
# 테스트 코드
print(staircase(0))
print(staircase(6))
print(staircase(15))
print(staircase(25))
print(staircase(41))
규식이는 친구들 사이에서 투자의 귀재로 알려져 있습니다. 페이수북과 인수타그램에 자신의 성과를 과시하기 때문인데요. 사실 규식이가 그 정도의 실력자는 아닙니다. 성과가 좋을 때에만 SNS에 공유해서 그렇게 비춰질 뿐이죠.
계속해서 멋진 모습을 보여주기 위해, 특정 기간 중 수익이 가장 큰 구간을 찾아내는 함수 sublist_max()를 작성해 보려고 합니다.
시간 복잡도를 O(n)로 풀어보세요!
실습 결과
def sublist_max(profits):
max_profit_so_far = profits[0] # 반복문에서 현재까지의 부분 문제의 답
max_check = profits[0] # 가장 끝 요소를 포함하는 구간의 최대 합
# 반복문을 통하여 각 요소까지의 최대 수익을 저장한다
for i in range(1, len(profits)):
# 새로운 요소를 포함하는 구간의 최대합을 비교를 통해 정한다
max_check = max(max_check + profits[i], profits[i])
# 최대 구간 합을 비교를 통해 정한다
max_profit_so_far = max(max_profit_so_far, max_check)
return max_profit_so_far
# 테스트 코드
print(sublist_max([7, -3, 4, -8]))
print(sublist_max([-2, -3, 4, -1, -2, 1, 5, -3, -1]))
규식이는 친구들 사이에서 투자의 귀재로 알려져 있습니다. 페이수북과 인수타그램에 자신의 성과를 과시하기 때문인데요. 사실 규식이가 그 정도의 실력자는 아닙니다. 성과가 좋을 때에만 SNS에 공유해서 그렇게 비춰질 뿐이죠.
계속해서 멋진 모습을 보여주기 위해, 특정 기간 중 수익이 가장 큰 구간을 찾아내는 함수 sublist_max()를 작성해 보려고 합니다.
Divide and Conquer 방식으로 풀어볼 텐데요. 시간 복잡도는 O(nlgn)이 되어야 합니다.
함수 설명
이번 sublist_max() 함수는 3개의 파라미터를 받습니다.
profits: 며칠 동안의 수익이 담겨 있는 리스트
start: 살펴볼 구간의 시작 인덱스
end: 살펴볼 구간의 끝 인덱스
sublist_max()는 profits의 start부터 end까지 구간에서 가능한 가장 큰 수익을 리턴합니다.
합병 정렬을 구현할 때 merge_sort() 함수를 깔끔하게 작성하기 위해 추가로 merge() 함수를 작성했던 것 기억 나시나요? 마찬가지로 퀵 정렬을 구현할 때 quicksort() 함수에 추가로 partition() 함수를 작성했습니다. 이번에도 sublist_max() 함수에 추가로 새로운 함수를 작성하면 도움이 되실 겁니다.
실습 결과
def max_crossing_sum(profits, start, end):
mid = (start + end) // 2 # 중간 인덱스
'''
왼쪽에서의 가장 큰 수익 계산
인덱스 mid부터 인덱스 0까지 범위를 넓혀가며 최대 수익을 찾는다
'''
left_sum = 0 # 왼쪽 누적 수익
left_max = profits[mid] # 왼쪽 최고 수익; 왼쪽 반 중 가장 오른쪽 값으로 초기화
for i in range(mid, start - 1, -1):
left_sum += profits[i]
left_max = max(left_max, left_sum)
'''
오른쪽에서의 가장 큰 수익 계산
인덱스 mid+1부터 인덱스 end까지 범위를 넓혀가며 최대 수익을 찾는다
'''
right_sum = 0 # 오른쪽 누적 수익
right_max = profits[mid + 1] # 오른쪽 최고 수익; 오른쪽 반 중 가장 왼쪽 값으로 초기화
for i in range(mid + 1, end + 1):
right_sum += profits[i]
right_max = max(right_max, right_sum)
return left_max + right_max
def sublist_max(profits, start, end):
# 범위에 하나의 항목밖에 없으면, 그 항목을 리턴한다
if start == end:
return profits[start]
# 중간 인덱스
mid = (start + end) // 2
# 상황별로 최대 수익을 구한다
max_left = sublist_max(profits, start, mid)
max_right = sublist_max(profits, mid + 1, end)
max_cross = max_crossing_sum(profits, start, end)
# 위 세 경우 중 가장 큰 결괏값을 리턴한다
return max(max_left, max_right, max_cross)
# 테스트 코드
list1 = [-2, -3, 4, -1, -2, 1, 5, -3]
print(sublist_max(list1, 0, len(list1) - 1))
list2 = [4, 7, -6, 9, 2, 6, -5, 7, 3, 1, -1, -7, 2]
print(sublist_max(list2, 0, len(list2) - 1))
list3 = [9, -8, 0, -7, 8, -6, -3, -8, 9, 2, 8, 3, -5, 1, -7, -1, 10, -1, -9, -5]
print(sublist_max(list3, 0, len(list3) - 1))
list4 = [-9, -8, -8, 6, -4, 6, -2, -3, -10, -8, -9, -9, 6, 2, 8, -1, -1]
print(sublist_max(list4, 0, len(list4) - 1))
(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):
# 이미 나온 요소를 저장시켜줄 사전
elements_seen_so_far = {}
for element in some_list:
# 이미 나온 요소인지 확인하고 맞으면 요소를 리턴한다
if element in elements_seen_so_far:
return element
# 해당 요소를 사전에 저장시킨다
elements_seen_so_far[element] = True
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]))
