python 최대구간

조회수 1725회

def deQuote(list): for i in range(0, len(list)): list[i] = int(list[i])

def findMaxSpan(list, k): size = len(list) max = list[0]

for start in range(0, size - k + 1): sum = list[start]

for i in range(1, k): sum += list[start + i]

if sum > max: max = sum

return max list = raw_input("정수들의 목록을 입력하세요: ").split() deQuote(list) k = input("최대 k-구간합을 구할 구간 수: ")

max = findMaxSpan(list, k)

print "최대", k,"-구간합: ", max

요래 최대구간합은 구했는데 최대 구간을 구하기가 어렵네요.

mavVal = -99999 (int.min?) i = 0 선언해두고 그냥 for j in range len(list) 돌려서 maxVal > 구간합 maxVal = 구간합 i = j

return (i, i + 2) 이러면 되는거 아닌가요?>

라고 누가 설명해주시기는 했는데 더 이해가 안가요 ㅠㅠ

명쾌한 답 부탁드립니다.,

  • 최대 구간이 뭔가요? 정두식 2016.5.15 11:55

1 답변

  • 인자 list에서 길이가 k인 subarray 중 가장 합이 큰걸 찾아내는 코드 아닌가요?

    def findMaxSpan(list, k):
        size = len(list)
        max = list[0] #문제
    
        for start in range(0, size - k + 1):
            sum = list[start]
    
            for i in range(1, k):
                sum += list[start + i]
    
            if sum > max: #답변
                max = sum
    
            return max
    

    우선 최대구간을 구하는 코드 자체에 문제가 있습니다. max = list[0]와 같이 설정하면, list = [3,-1,-3,-2] 같이 리스트에 음수 정수가 있을 경우 원하는 리턴값이 안나옵니다.


    질문하신 최대구간으로 넘어오면,

    subarray의 길이 k가 주어져 있으니 최대구간은 [최대합을 가지는 subarray가 시작하는 인덱스 i, i+k-1] 까지일거고, 그렇다면 i를 알아내는 코드를 추가해줘야합니다.

    sum > maxTrue일 경우 max가 바뀌고, 이 때 인덱스 i을 변경해 주면됩니다.

    for문 하나로 리스트에 값과 인덱스를 조회하는 방법은 다음과 같습니다.

    for idx, value in enumerate(list):
    
    • (•́ ✖ •̀)
      알 수 없는 사용자

답변을 하려면 로그인이 필요합니다.

Hashcode는 개발자들을 위한 무료 QnA 사이트입니다. 계정을 생성하셔야만 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 계정을 생성하셔야만 글을 작성하실 수 있습니다.