섹션3의 '수들의 합' 문제 질문

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

작성

221

저는 해당 문제를 풀 때, 현재 인덱스를 시작점으로 잡고 이후 인덱스 요소들을 연속적으로 더하는 식으로 풀었습니다. 이후 인덱스 요소들을 더하다가 조건의 값과 같아지면 count를 증가시킨 후 다음번의 인덱스를 시작점으로 설정하여 연속적으로 더하는 작업을 이어나갔고, 조건의 값보다 커지면 count를 증가시키지 않고 다음번의 인덱스를 시작점을 잡아 연속적으로 더하는 작업을 이어나갔습니다.

해당 방법으로 자동채점기를 돌려보니, 입력 원소들의 개수가 많아지면 time limit이 되는 것을 확인했습니다.

어떤 이유로 강사님이 풀이해주신 방법과 위 방법의 연산 속도차이가 나는지 궁금합니다. 저는 제 방법이 강사님이 풀이해주신 방법과 겉으로 보기에만 다를 뿐, 똑같은 방식이라 생각합니다.

자세한 답변 부탁드립니다.

python 코테 준비 같이 해요!

답변 4

banggoo1152

질문자

답변 이해했습니다.

감사합니다.

김태원

지식공유자

위 코드는 2중 for문을 사용하는 시간복잡도가 O(n^2)인 코드입니다. 제가 영상에서 설명한 방법은 반복문을 하나만 사용하는 시간복잡도가 O(n)입니다.

banggoo1152

질문자

제가 작성한 코드는 다음과 같습니다.

제가 작성한 코드가 강사님이 작성한 코드와 어느 부분에서 다른지 궁금합니다.

import sys

sys.stdin = open("in1.txt", "rt")
n, m = map(int, input().split())
a = list(map(int, input().split()))

def numbers_sum_ocassion(m,number_list):

    count = 0
    for i in range(len(number_list)):

        for j in range(i, len(number_list)):

            if i == j:

                if number_list[i] == m:

                    count = count + 1
                    break

                continue

            if sum(number_list[i:j+1]) == m:

                count = count + 1
                break

            if sum(number_list[i:j+1]) > m:

                break

    return count

print(numbers_sum_ocassion(m, a))

김태원

지식공유자

안녕하세요^^

실제 코드를 봐야 알 수 있지만, 일단 중첩반복문(O(n^2))으로 했다면 시간초과가 납니다.

영상에서 제가 하는 방법은 단일 반복문처리이며 시간복잡도는 O(n)입니다.

인프런 커뮤니티 질문&답변

섹션3의 '수들의 합' 문제 질문