패스트캠퍼스 환급챌린지 12일차 : 네카라쿠배 취업 끝장내는 파이썬 코딩테스트 마스터

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.

 

강의 목록

Chatper 3. 응용 알고리즘

1강.누적합 배열 자료 구조 소개 

2강. 누적합 배열 사용 예제 1

 

 

누적합 배열 자료 구조

배열 a: 3, 2, 1

누적합 배열: 3, 5, 6

 

누적합 배열 인덱스 i에 들어있는 값은 a[0]+ ... + a[i] 를 의미

누적합은 prefix sum의 약자인 psum을 변수로 주로 사용

 

사용 예제

배열 A의 연속한 구간 합을 구하는 경우

ex) a[2] + a[3] + ... a[8] 을 구하고 싶은 경우, psum[8] - psum[1]로 쉽게 구할 수 있음

 

 

문제

2559번: 수열

 

 

내 풀이

N, K = list(map(int, input().split()))
temperature = list(map(int, input().split()))

# 누적합 계산
psum = [0] * N
psum[0] = temperature[0]
for i in range(1, N):
    psum[i] = psum[i-1] + temperature[i]

print(f"psum: {psum}")

# K가 5일때는
# t[0]~t[4]: psum[4]
# t[1]~t[5]: psum[5] - psum[0]
# t[2]~t[6]: psum[6] - psum[1]
# t[3]~t[7]: psum[7] - psum[2]
# t[4]~t[8]: psum[8] - psum[3]
# t[5]~t[9]: psum[9] - psum[4]
# t[6]~t[10]: psum[10] - psum[5]

candidates = [psum[K-1]]
for i in range(N-K):
    candidates.append(psum[i+K] - psum[i])

print(max(candidates))

정답 맞춤

 

 

강사님 풀이

# 연속된 K일 온도 합
temp_sum = []
for i in range(0, N-K+1):
    # i~ i+K-1
    if i == 0:
        sum = psum[i+K-1]
    else:
        sum = psum[i+K-1] - psum[i-1]

    temp_sum.append(sum)

print(max(temp_sum))

누적합 구하는 부분까지는 동일해서 안 썼다.

 

 

 

 

내 풀이에서 gpt가 조금 더 리팩토링한 코드

max_sum = float('-inf')
for ...:
    curr = 누적합 구간합
    max_sum = max(max_sum, curr)
print(max_sum)

 

차이

나는 candidates라고 리스트에 넣고 마지막에 max로 구했는데, gpt는 루프를 돌면서 바로 max 비교를 했다.

이렇게 하면 리스트에 저장하지 않아도 되니까 메모리가 더 효율적이다.

 

또 내 풀이의 경우 루프돌면서 O(N) + 마지막 max 구할 때 O(N)으로 O(2N)인데 

gpt의 경우 루프 돌 때 O(N) + 2개 수 max 비교 O(1) = O(N) 으로 연산이 더 효율적이다. 

 

보면서, max 계산에서 시간복잡도가 좀 궁금해져서 물어봤다. 

 

max 연산 시간복잡도

코드	시간복잡도	설명
max(1, 2)	O(1)	상수 개수 비교
max(1, ..., 1000)	O(N)	인자 1000개 → 순차 비교
max([1, ..., 1000])	O(N)	리스트 비교 → 동일
max(tuple_of_1000_elements)	O(N)	마찬가지

 

max 비교 시 인자가 적으면 시간차가 거의 안나서 O(1)처럼 느껴진다.

하지만 max(1,2,3,...,1000) 이렇게 인자가 많아지면 얘도 결국 O(N)이다. 

 

 

 

 

 

https://abit.ly/lisbva