코드업 풀때 repl it을 함께 사용하여 푸는 것이 매우 효율적이다.
답은 하기 참고..
Coding/Python
- Reference) Codeup과 replit 2023.03.15
- Reference: 부분합 / 연속 구간 부분수열 최대합 / 동적 계획법 2023.03.15 2
Reference) Codeup과 replit
2023. 3. 15. 18:44
Reference: 부분합 / 연속 구간 부분수열 최대합 / 동적 계획법
2023. 3. 15. 18:43
외우기 쉽게
1) 동적 최대 합
def dy_part_max_sum(arr):
temp=[0]*len(arr)
temp[0]=arr[0]
for i in range(0,len(arr)):
temp[i]=max(0,temp[i-1])+arr[i]
return max(temp)
scores = [-14, 7, 2, 10, -4, 9, -10]
res=dy_part_max_sum(scores)
print("result:",res) #24
2) 동적 구간 합
def dy_part_sum(arr,s,end):
temp=[0]*len(arr)
temp[0]=arr[0]
for i in range(0,len(arr)):
temp[i]=temp[i-1]+arr[i]
if i==(s-1):
s_sum=temp[i]
elif i==end:
end_sum=temp[i]
break
return (end_sum - s_sum)
scores = [100, 95, 80, 100, 70, 65]
print("result:",dy_part_sum(scores, 3, 4)) # 235
==================================================
o 부분합
def partial_sum(arr, a, b):
arr = [0] + arr #초기화
partial_sum = [0] * len(arr) #초기화
for i in range(1, len(arr)):
partial_sum[i] = partial_sum[i-1] + arr[i]
partial_sum = partial_sum[1:]
print("partial_sum", partial_sum)
print("total sum", partial_sum[-1])
return partial_sum[b] - partial_sum[a-1]
scores = [100, 95, 80, 100, 70, 65]
print("result:",partial_sum(scores, 3, 5)) # 235
# partial_sum [100, 195, 275, 375, 445, 510]
# total sum 510
o 연속 구간 부분수열 최대합
def partial_sum(arr):
arr = [0] + arr
partial_sum = [0] * len(arr)
for i in range(1, len(arr)):
partial_sum[i] = partial_sum[i-1] + arr[i]
partial_sum = partial_sum[1:]
print("partial_sum", partial_sum)
max_partial_sum = partial_sum[0]
for b in range(0, len(arr)-1):
for a in range(0, b):
print(a, b, partial_sum[b] - partial_sum[a-1])
max_partial_sum = max(max_partial_sum, partial_sum[b] - partial_sum[a-1])
print("max partial sum", max_partial_sum)
scores = [-14, 7, 2, 10, -4, 9, -10]
print("list", scores)
res=partial_sum(scores)
print("result:",res)
#
list [-14, 7, 2, 10, -4, 9, -10]
partial_sum [-14, -7, -5, 5, 1, 10, 0]
0 1 -7
0 2 -5
1 2 9
0 3 5
1 3 19
2 3 12
0 4 1
1 4 15
2 4 8
3 4 6
0 5 10
1 5 24
2 5 17
3 5 15
4 5 5
0 6 0
1 6 14
2 6 7
3 6 5
4 6 -5
5 6 -1
max partial sum 24
o 동적 계획법 최대값
def dynamic_partial_sum(arr):
cache = [0] * len(arr)
cache[0] = arr[0]
for i in range(0, len(arr)):
cache[i] = max(0, cache[i-1]) + arr[i]
print(i, arr[i], cache)
print(cache)
return max(cache)
scores = [-14, 7, 2, 10, -4, 9, -10]
print("list", scores)
res=dynamic_partial_sum(scores)
print("result:",res) #24
#
list [-14, 7, 2, 10, -4, 9, -10]
0 -14 [-14, 0, 0, 0, 0, 0, 0]
1 7 [-14, 7, 0, 0, 0, 0, 0]
2 2 [-14, 7, 9, 0, 0, 0, 0]
3 10 [-14, 7, 9, 19, 0, 0, 0]
4 -4 [-14, 7, 9, 19, 15, 0, 0]
5 9 [-14, 7, 9, 19, 15, 24, 0]
6 -10 [-14, 7, 9, 19, 15, 24, 14]
[-14, 7, 9, 19, 15, 24, 14]