얼마나 빠른가 - 연산 횟수와 복잡도

이 장에서 배우는 것

앞 장에서 입력과 출력, 조건과 반례를 분리해 문제를 읽었다. 이제 같은 답을 내는 풀이 가운데 어떤 풀이가 입력이 커져도 버틸 수 있는지 살펴본다. 작은 예시에서는 두 풀이가 모두 곧바로 끝날 수 있다. 그러나 입력이 열 배가 되었을 때 해야 할 일이 열 배로 늘어나는지, 백 배로 늘어나는지는 풀이의 실용성을 크게 바꾼다.

시간 복잡도(time complexity)는 이 증가 경향을 설명하는 도구다. 프로그램의 실행 시간을 초 단위로 예언하는 공식은 아니다. 이 장에서는 먼저 손으로 반복 횟수를 세고, 그 결과를 빅오 표기(Big O notation)로 요약한다. 마지막에는 같은 문제를 푸는 세 가지 방법의 작업 횟수를 직접 출력한다.

• 무엇을 한 번의 작업으로 셀지 정하고 반복 횟수를 계산한다.
• 빅오 표기가 설명하는 것과 설명하지 못하는 것을 구분한다.
• 입력 제약에서 가능한 풀이의 복잡도를 거꾸로 추정한다.
• 세 가지 풀이의 답과 작업 횟수를 확인하고 작은 입력 전체를 대조한다.

문제 상황

작은 작업실에서 참여자끼리 서로 작업물을 검토하려 한다. 참여자는 0번부터 N−1번까지 번호를 받는다. 서로 다른 두 사람으로 만들 수 있는 검토 짝의 수를 구하는 것이 첫 번째 문제다. 같은 사람이 두 번 들어가는 짝은 없고, 0번과 2번의 짝은 2번과 0번의 짝과 같다. 참여자가 없거나 한 명이면 답은 0이다.

예를 들어 참여자가 네 명이면 짝은 (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)의 여섯 개다. 여기서 요청한 출력은 짝의 목록이 아니라 짝의 개수 하나다. 이 차이가 중요하다. 목록을 모두 출력해야 한다면 여섯 항목을 실제로 만들어야 하지만, 개수만 필요하다면 목록을 만들지 않고 계산할 여지가 있다.

첫 번째 담당자는 두 사람의 번호를 각각 처음부터 끝까지 바꾸며 조건에 맞는지 확인했다. 두 번째 담당자는 앞사람보다 번호가 큰 사람만 골랐다. 세 번째 담당자는 짝의 수를 식으로 계산했다. 세 방법은 같은 답을 내지만 수행하는 일은 다르다.

두 번째 문제는 재고 점검이다. 선반별 재고 수량이 리스트로 주어지고, 재고가 기준값보다 작은 선반의 수를 구한다. 예를 들어 재고가 [4, 1, 0, 3]이고 기준값이 2이면 답은 2다. 이 문제에서는 모든 선반을 한 번씩 살피는 일이 왜 필요한지 따져 본다. 짝 세기에서는 없앨 수 있었던 반복이 재고 점검에서는 필요한 이유를 비교하는 것이다.

반복 횟수를 손으로 세기

모든 번호 조합을 확인하는 풀이

첫 번째 풀이는 i와 j를 각각 0부터 N−1까지 움직인다. 각 조합에서 i가 j보다 작은지 검사하고, 참이면 답을 하나 늘린다. i < j라는 조건은 같은 사람끼리의 짝을 제외하면서 두 순서 가운데 하나만 남긴다.

N이 4일 때 바깥 반복은 네 번 실행된다. 바깥 반복 한 번마다 안쪽 반복도 네 번 실행된다. 따라서 조건 검사는 4 × 4 = 16번이다. 답을 늘리는 횟수는 6번이지만, 답을 늘리지 않는 나머지 검사도 실행 시간에 영향을 준다. 성공한 경우만 세면 전체 작업을 놓치게 된다.

참여자 네 명일 때 모든 조합을 검사한 결과

i	검사하는 j	조건 검사 횟수	새로 세는 짝
0	0, 1, 2, 3	4	3
1	0, 1, 2, 3	4	2
2	0, 1, 2, 3	4	1
3	0, 1, 2, 3	4	0
합계	모든 조합	16	6

일반적인 N에서는 N × N번 검사한다. 바깥 반복을 한 번 더 진행할 때마다 검사 대상이 N개씩 추가되므로 전체 검사 횟수는 N²이다. 반복문이 두 개라는 사실보다 각 반복이 실제로 몇 번 실행되는가가 계산의 근거다.

이미 제외할 조합은 만들지 않는 풀이

두 번째 풀이는 i를 고른 다음 j를 i+1부터 시작한다. i가 0이면 세 번, 1이면 두 번, 2이면 한 번, 3이면 한 번도 반복하지 않는다. 검사할 필요가 없는 조합을 반복 범위에서 제외한 것이다. 이제 안쪽 반복이 실행될 때마다 유효한 짝이 하나 생긴다.

일반적인 N에서는 (N−1) + (N−2) + … + 1번 방문한다. 이 합을 S라고 하자. 같은 합을 거꾸로 적어 더하면 각 자리가 N이 되고, 그런 자리가 N−1개 있다. 따라서 2S = N(N−1)이며, S = N(N−1)/2이다. N이 0이나 1인 경우에는 방문할 짝이 없으며 이 식도 0이 된다.

이 풀이가 정확한 이유는 간단하다. 서로 다른 두 번호 중 작은 번호를 i, 큰 번호를 j라고 정하면 모든 짝이 반복 범위에 들어간다. 또한 작은 번호와 큰 번호의 위치가 정해져 있으므로 같은 짝을 다시 방문하지 않는다. 빠짐도 중복도 없다.

목록을 만들지 않고 개수만 계산하는 풀이

세 번째 풀이는 방금 구한 N(N−1)/2를 그대로 계산한다. 곱 N(N−1)은 연속한 두 정수의 곱이어서 짝수다. 따라서 Python에서는 n * (n - 1) // 2로 정수 답을 얻는다. 실수로 변환할 이유가 없다.

이 풀이의 정확성 근거는 두 번째 풀이의 방문 횟수 계산이다. 두 번째 풀이가 각 짝을 정확히 한 번 방문하며, 식이 그 방문 수와 같으므로 결과도 같다. 단순히 예시 몇 개에서 값이 맞았기 때문에 식을 선택한 것이 아니다.

세 풀이의 작업 횟수를 출력하려면 무엇을 셀지 먼저 정해야 한다. 첫 번째에서는 후보 조건을 검사한 횟수, 두 번째에서는 유효한 후보를 방문한 횟수, 세 번째에서는 결과식을 평가한 횟수를 센다. 앞의 두 방법은 반복 본문의 실행 수를, 마지막 방법은 반복 없이 답을 계산했다는 사실을 보여 준다.

이 단위들은 계산 비용이 정확히 같은 기계 명령이 아니다. 따라서 16회와 1회라는 출력이 실행 시간도 정확히 열여섯 배라는 뜻은 아니다. 표의 목적은 입력 크기에 따른 작업의 증가를 관찰하는 데 있다. 횟수를 기록하는 변수의 증가 연산도 관찰을 위해 추가한 코드이며, 원래 풀이의 필수 작업과 구분해야 한다.

빅오 표기로 증가 경향 읽기

첫 번째 풀이의 검사 수는 N²이고, 두 번째 풀이의 방문 수는 N(N−1)/2이다. 두 번째가 큰 N에서 대략 절반만 방문하지만, 두 식 모두 N을 두 배로 키우면 주요 작업이 약 네 배로 늘어난다. 두 풀이의 시간 복잡도를 모두 O(N²)이라고 쓴다.

빅오는 입력이 충분히 커졌을 때 작업량을 어떤 증가식의 일정한 배수 아래에 둘 수 있는지 나타낸다. 예를 들어 3N+7은 N이 1 이상일 때 10N 이하이므로 O(N)이라고 할 수 있다. 여기서 상수 배수와 작은 항을 생략하는 이유는 입력이 커질 때의 증가 경향에 집중하기 위해서다.

빅오는 상한을 나타내므로 선형으로 증가하는 작업량을 O(N²)이라고 써도 수학적으로 틀린 말은 아니다. 다만 풀이를 비교할 때 그렇게 느슨하게 쓰면 정보가 줄어든다. 이 책에서는 특별한 설명이 없으면 실제 증가 경향을 잘 드러내는 상한을 선택한다.

식으로 계산하는 세 번째 풀이는 보통의 코딩 테스트 분석에서 O(1)이라고 한다. N이 커져도 같은 개수의 산술 연산으로 답을 구하기 때문이다. 다만 이 설명은 사용하는 정수의 산술 연산을 일정 비용으로 취급한 것이다. Python의 정수는 값이 커지면 필요한 저장 공간도 늘어나므로, 매우 긴 정수를 다룰 때는 자릿수에 따른 계산 비용까지 고려해야 한다.

검토 짝을 세는 세 풀이의 작업량과 복잡도

풀이	기록할 작업 횟수	시간 복잡도	추가 공간
모든 조합 검사	N²	O(N²)	O(1)
큰 번호만 방문	N(N−1)/2	O(N²)	O(1)
결과식 계산	1	O(1)	O(1)

공간 복잡도(space complexity)는 입력이 커질 때 필요한 저장 공간의 증가를 설명한다. 세 풀이 모두 짝의 목록을 저장하지 않고 번호와 개수만 유지하므로 추가 공간은 O(1)이다. 여기에서도 정수 하나를 일정 크기로 보는 통상적인 분석을 사용한다. 정수의 자릿수까지 분석한다면 저장 공간 설명도 그에 맞춰 바꿔야 한다.

빅오 표기만으로 두 프로그램의 실제 속도 순서가 언제나 정해지지는 않는다. 같은 O(N²)이라도 검사와 방문의 수가 다르고, 반복 안에서 수행하는 일도 다를 수 있다. 반대로 작은 입력에서는 준비 작업이 많은 O(N) 풀이가 짧은 O(N²) 풀이보다 느릴 수도 있다. 증가 경향과 실제 구현 비용을 함께 보아야 한다.

재고 점검에는 왜 한 번의 순회가 필요한가

재고 문제에서는 각 수량을 기준값과 비교해 부족하면 답을 하나 늘린다. 재고 리스트 길이를 M이라고 하면 비교는 M번이다. 조건에 맞는 선반이 하나도 없어도 모든 수량을 확인해야 하므로 이 풀이의 시간 복잡도는 O(M)이다.

def count_shortages(stocks, threshold):
    count = 0
    for stock in stocks:
        if stock < threshold:
            count += 1
    return count

반복 도중 앞에서 k개의 선반을 확인했다고 하자. 이때 count는 그 k개 중 부족한 선반의 수다. 처음에는 확인한 선반이 없어서 0이 맞고, 다음 선반이 부족할 때만 1을 더하면 같은 설명이 유지된다. 반복이 끝나면 모든 선반에 대한 답이 된다. 이처럼 반복 중 계속 참인 설명을 불변식(loop invariant)이라고 한다.

추가 정보가 없는 임의의 재고 리스트에서는 확인하지 않은 마지막 수량 하나가 답을 바꿀 수 있다. 그 수량이 기준값 이상인 입력과 기준값 미만인 입력을 구별해야 하므로 최악의 경우 모든 원소를 읽어야 한다. 검토 짝 문제는 번호 범위만으로 답이 정해졌지만, 재고 문제는 개별 데이터가 답에 영향을 준다. 반복을 없앨 수 있는지는 문제의 정보 구조에 달려 있다.

입력 제약에서 가능한 풀이 좁히기

풀이를 구현하기 전에 입력의 최대 크기를 식에 넣어 본다. N이 최대 100이라면 N²은 10,000이다. N이 최대 100,000이라면 N²은 10,000,000,000이다. 같은 이중 반복이라도 예상 작업량은 크게 달라진다. 입력 크기를 먼저 보는 습관은 구현 후에 구조를 다시 바꾸는 일을 줄여 준다.

다음 표의 판단은 특정 실행 환경에서 통과를 보장하는 기준이 아니다. 반복 안의 작업이 단순하다고 가정하고, 어떤 풀이를 먼저 검토할지 정하는 출발점이다. 실행 제한, 언어, 입력 처리량, 자료의 형태를 확인한 뒤 판단을 보완해야 한다.

최대 입력을 작업량 식에 대입해 후보 풀이를 점검하는 예

최대 크기	N번	N²번	먼저 할 판단
100	100	10,000	단순한 이중 반복도 검토한다.
1,000	1,000	1,000,000	반복 본문의 비용을 확인한다.
100,000	100,000	10,000,000,000	이중 반복을 줄일 근거를 찾는다.

반복문이 중첩되어 있어도 안쪽 반복이 항상 세 번이라면 전체 방문 수는 3N이어서 O(N)이다. 반대로 반복문 하나 안에서 길이 N인 리스트 전체를 매번 복사한다면 N번의 반복에 각각 N에 비례하는 일이 들어간다. 겉으로 보이는 반복문의 개수만으로 복잡도를 정하면 이런 비용을 놓친다.

입력이 여러 묶음으로 주어지는 경우에는 묶음 전체의 작업도 더해야 한다. 각 묶음의 크기가 N이고 묶음이 T개라면 O(N²) 풀이의 전체 작업은 O(TN²)이다. 묶음마다 크기가 다르면 각 크기의 제곱을 더해 생각한다. 문제에 전체 입력 크기의 합에 대한 제약이 있는지도 확인한다.

실행 시간을 재는 일도 유용하지만, 시간에는 실행 환경의 상태와 측정 방법이 섞인다. 이번 프로그램은 시간을 재지 않고 반복 횟수를 기록한다. 따라서 실행할 때마다 같은 표가 나오며, 작업량 식이 코드와 일치하는지 확인하기 쉽다. 실제 프로그램의 제한 시간을 판단할 때는 이런 분석을 바탕으로 해당 환경에서 측정한다.

완성 코드

다음 내용을 main.py로 저장한다. 예시 입력은 문자열에 넣고 io.StringIO로 읽는다. 외부 입력을 기다리지 않는다. 표에서 all_checks는 모든 조합의 조건 검사 수, forward_visits는 큰 번호만 고른 방문 수, formula_evals는 결과식 평가 수다. ways는 세 풀이가 공통으로 구한 답이다.

import io


def count_all_pairs(n):
    pairs = 0
    checks = 0
    for i in range(n):
        for j in range(n):
            checks += 1
            if i < j:
                pairs += 1
    return pairs, checks


def count_forward_pairs(n):
    pairs = 0
    visits = 0
    for i in range(n):
        for j in range(i + 1, n):
            visits += 1
            pairs += 1
    return pairs, visits


def count_pairs_by_formula(n):
    pairs = n * (n - 1) // 2
    evaluations = 1
    return pairs, evaluations


def count_shortages(stocks, threshold):
    count = 0
    for stock in stocks:
        if stock < threshold:
            count += 1
    return count


def verify_small_inputs():
    tested = 0
    for n in range(41):
        slow, checks = count_all_pairs(n)
        forward, visits = count_forward_pairs(n)
        formula, evaluations = count_pairs_by_formula(n)

        assert slow == forward == formula
        assert checks == n * n
        assert visits == n * (n - 1) // 2
        assert evaluations == 1
        tested += 1
    return tested


def read_example_sizes():
    example_input = """5
0
1
4
10
100
"""
    stream = io.StringIO(example_input)
    case_count = int(stream.readline())
    sizes = []

    for _ in range(case_count):
        n = int(stream.readline())
        if n < 0:
            raise ValueError("N must be nonnegative")
        sizes.append(n)

    return sizes


def main():
    tested = verify_small_inputs()
    sizes = read_example_sizes()

    print(f"verified: {tested}")
    print("N | ways | all_checks | forward_visits | formula_evals")

    for n in sizes:
        all_pairs, checks = count_all_pairs(n)
        forward_pairs, visits = count_forward_pairs(n)
        formula_pairs, evaluations = count_pairs_by_formula(n)
        assert all_pairs == forward_pairs == formula_pairs
        print(
            f"{n} | {all_pairs} | {checks} | "
            f"{visits} | {evaluations}"
        )

    stocks = [4, 1, 0, 3]
    threshold = 2
    print(f"shortages: {count_shortages(stocks, threshold)}")


if __name__ == "__main__":
    main()

프로그램은 난수를 사용하지 않는다. 검증 대상과 출력 순서도 고정되어 있어 실행 결과가 결정적이다. 세 풀이의 함수는 모두 0 이상의 정수 N을 받는다는 조건으로 작성했다. 예시 입력을 읽는 곳에서 음수를 거부한다.

줄별 해설

import io는 메모리 속 문자열을 파일처럼 읽기 위해 사용한다. 실제 코딩 테스트에서 한 줄씩 읽는 흐름을 유지하면서도 프로그램이 키보드 입력을 기다리지 않게 한다. 첫 줄의 5는 뒤에 이어지는 입력 크기가 다섯 개라는 뜻이다.

count_all_pairs의 pairs는 답이고 checks는 관찰용 횟수다. 두 변수는 역할이 다르다. checks += 1을 조건문 앞에 두었기 때문에 조건이 거짓인 검사도 센다. 이를 조건문 안으로 옮기면 전체 검사 횟수가 아니라 유효한 짝의 수를 다시 세게 된다.

안쪽 반복을 일부 수행한 시점에서 pairs는 지금까지 확인한 조합 중 i < j인 조합의 수다. 다음 조합에서도 조건이 참일 때만 하나를 더하므로 이 설명이 유지된다. 모든 조합을 확인하면 원하는 짝의 수가 된다. 이 함수가 작은 입력에서 비교 기준이 되는 느린 정답이다.

count_forward_pairs에서는 range(i + 1, n)이 핵심이다. 시작점이 i+1이므로 자기 자신과 더 작은 번호는 방문하지 않는다. Python의 range는 끝값을 포함하지 않으므로 가장 큰 번호는 n−1이다. i가 n−1이면 범위가 비어 안쪽 반복이 실행되지 않는다.

두 번째 함수의 pairs와 visits는 이 문제에서는 같은 값이 된다. 방문마다 짝 하나를 세기 때문이다. 그래도 별도 변수로 둔 이유는 답과 작업량의 의미를 구분하기 위해서다. 다른 문제에서는 후보를 방문해도 답이 늘어나지 않을 수 있다.

count_pairs_by_formula의 evaluations는 산술 명령 수가 아니다. 뺄셈, 곱셈, 나눗셈을 포함한 결과식 전체를 한 번 평가했다는 기록이다. N이 0이나 1이어도 식을 한 번 계산하므로 기록 값은 1이다. 다른 두 함수의 안쪽 반복 횟수가 0이라는 사실과 모순되지 않는다.

verify_small_inputs는 0부터 40까지의 모든 입력을 순서대로 검사한다. 이 문제의 입력은 정수 하나이므로 이 구간에는 총 41개의 입력이 있다. 몇 개를 무작위로 뽑는 대신 정한 작은 범위를 빠짐없이 대조한다. 특히 짝을 만들 수 없는 0과 1도 포함한다.

첫 번째 assert는 세 풀이의 답을 비교한다. 이어지는 assert들은 기록한 작업 횟수가 예상 식과 같은지 확인한다. 결과만 맞고 횟수 기록이 틀리는 경우도 잡기 위한 구분이다. 모든 비교가 맞으면 함수는 검사한 입력 수를 돌려준다.

이 전수 대조는 작은 범위의 구현 오류를 찾는 검사다. 41개를 통과했다고 모든 N에서의 정확성이 증명되지는 않는다. 앞에서 설명한 빠짐과 중복의 부재, 합 공식의 근거가 일반적인 정확성을 뒷받침하고, 전수 대조가 실제 코드의 실수를 보완한다.

main은 검증 후 표를 출력한다. 표를 만들 때도 세 답이 같은지 다시 확인한다. 마지막 재고 예시는 기준값보다 작은 두 선반을 센다. 재고 함수의 추가 공간은 O(1)이며, 예시 리스트를 저장하는 공간은 입력 데이터의 공간으로 따로 본다.

완성 프로그램 전체의 비용과 개별 풀이의 비용도 구분해야 한다. 이 프로그램은 비교를 위해 느린 풀이까지 실행한다. 입력 크기 목록이 고정된 다섯 개이고 그중 가장 큰 값이 N이라면 표를 만드는 시간은 O(N²)이다. 식을 사용하는 함수를 포함했다고 프로그램 전체가 O(1)이 되는 것은 아니다.

실행 결과

터미널에서 다음 명령을 실행한다. 첫 명령은 Python 소스의 컴파일 가능 여부를 확인하고, 두 번째 명령은 프로그램을 실행한다. 첫 명령은 정상일 때 출력이 없다.

python3 -W error -m py_compile main.py
python3 main.py

예상 출력은 다음과 같다.

verified: 41
N | ways | all_checks | forward_visits | formula_evals
0 | 0 | 0 | 0 | 1
1 | 0 | 1 | 0 | 1
4 | 6 | 16 | 6 | 1
10 | 45 | 100 | 45 | 1
100 | 4950 | 10000 | 4950 | 1
shortages: 2

N이 10에서 100으로 열 배가 될 때 모든 조합의 검사 수는 100에서 10,000으로 백 배가 된다. 큰 번호만 방문하는 횟수는 45에서 4,950으로 110배가 된다. 정확히 백 배가 아닌 이유는 N(N−1)/2에 N² 항과 N 항이 함께 있기 때문이다. N이 커질수록 제곱 항이 증가 경향을 주도한다.

두 반복 풀이가 같은 O(N²)이라는 설명과, 두 번째 풀이가 더 적게 방문한다는 관찰은 함께 성립한다. 복잡도는 큰 증가 경향을 묶고, 실제 횟수는 그 안의 차이를 보여 준다.

실무에서 자주 틀리는 것

조건이 참일 때만 작업 횟수를 세기

다음 코드는 조건 검사의 전체 횟수를 기록하지 못한다. 거짓으로 끝난 검사도 이미 수행한 작업이다.

if i < j:
    checks += 1
    pairs += 1

검사 횟수를 세려면 조건 평가 전에 기록한다. 무엇을 세는 변수인지 이름과 위치를 맞춘다.

checks += 1
if i < j:
    pairs += 1

안쪽 반복이 언제나 N번이라고 가정하기

큰 번호만 방문하는 코드의 횟수를 다음처럼 계산하면 실제 반복 범위를 반영하지 못한다.

expected_visits = n * n

각 i에서 방문 수는 n−i−1이다. 이를 더한 식을 사용한다. 다만 횟수가 절반 가까이 줄어도 시간 복잡도는 O(N²)이다.

expected_visits = n * (n - 1) // 2

정수 답을 실수로 계산한 뒤 되돌리기

다음 코드는 나눗셈에서 실수로 바뀐다. 작은 값에서는 답이 맞아 보이더라도 큰 정수의 정확한 계산을 불필요한 실수 변환에 맡기게 된다.

pairs = int(n * (n - 1) / 2)

곱이 짝수라는 근거가 있으므로 정수 나눗셈을 사용한다.

pairs = n * (n - 1) // 2

개수를 구하려고 모든 짝을 저장하기

다음 코드는 유효한 짝마다 튜플을 만들어 리스트에 보관한다. 개수만 필요한 문제에서는 O(N²)의 저장 공간을 추가로 사용하는 셈이다.

pairs = []
for i in range(n):
    for j in range(i + 1, n):
        pairs.append((i, j))
answer = len(pairs)

목록이 필요한지 개수가 필요한지 출력 조건을 다시 확인한다. 이 문제는 식으로 개수만 계산하면 된다.

answer = n * (n - 1) // 2

한눈에 보기

작업량을 분석할 때 묻는 질문과 확인 방법

질문	확인 방법	이 장의 예
무엇을 한 번으로 셌는가	횟수 변수의 증가 위치를 본다.	후보 조건 검사 한 번
반복은 총 몇 번인가	각 반복 범위의 길이를 더한다.	N² 또는 N(N−1)/2
입력이 커지면 어떻게 늘어나는가	주요 증가 항을 확인한다.	두 반복 풀이는 O(N²)
저장 공간도 늘어나는가	입력 외에 쌓는 데이터를 본다.	개수만 유지하면 O(1)
코드가 계산한 답은 맞는가	근거를 세우고 작은 입력을 대조한다.	0부터 40까지 41개 검사

작업량을 판단할 때는 출력이 요구하는 정보부터 확인한다. 그다음 실제 반복 수를 세고, 최대 입력을 대입하고, 증가 경향을 복잡도로 요약한다. 다음 장에서 시뮬레이션을 구현할 때도 상태를 몇 번 갱신하는지와 한 번의 갱신에 드는 일을 이 방식으로 살펴볼 수 있다.

연습 문제

1. 참여자가 6명일 때 세 풀이의 답과 기록할 작업 횟수를 각각 구하라. 답을 늘리는 횟수와 조건을 검사하는 횟수를 구분해서 설명하라.
2. 다음 코드의 가장 안쪽 문장이 총 몇 번 실행되는지 N에 대한 식으로 쓰고 시간 복잡도를 구하라. N은 0 이상의 정수다.

   for i in range(n):
       for offset in range(3):
           value = i + offset

3. 재고가 [2, 0, 5, 1, 2]이고 기준값이 2일 때 부족한 선반의 수와 비교 횟수를 구하라. 첫 번째 부족한 선반을 찾은 뒤 반복을 끝내도 되는지 설명하라.
4. 참여자 수를 N에서 2N으로 바꿀 때 첫 번째 풀이와 세 번째 풀이의 기록 횟수는 각각 어떻게 바뀌는가. 또한 검토 짝의 목록 전체를 출력하도록 요구가 바뀌면 식을 계산하는 것만으로 충분한지 설명하라.

정답과 해설

1. 짝의 수는 6 × 5 ÷ 2 = 15다. 첫 번째 풀이는 조건을 36번 검사하고 그중 15번 답을 늘린다. 두 번째 풀이는 유효한 짝을 15번 방문하며 매번 답을 늘린다. 세 번째 풀이는 결과식을 한 번 평가한다. 세 풀이가 반환하는 답은 모두 15다.
2. 바깥 반복 한 번마다 안쪽 문장이 세 번 실행되므로 총 3N번이다. 시간 복잡도는 O(N)이다. N이 0이면 바깥 반복이 실행되지 않아 총횟수도 0이다. 중첩된 반복문이라도 안쪽 범위가 입력과 함께 커지는지 확인해야 한다.
3. 수량이 0인 선반과 1인 선반이 부족하므로 답은 2다. 비교는 리스트 길이와 같은 5번이다. 첫 번째 부족한 선반을 찾은 뒤에도 뒤에 부족한 선반이 더 있을 수 있다. 존재 여부가 아니라 전체 개수를 요구하므로 그 시점에 끝내면 안 된다.
4. 첫 번째 풀이의 횟수는 N²에서 (2N)² = 4N²으로 바뀐다. 세 번째 풀이의 결과식 평가 수는 계속 1이다. 목록 전체를 요구한다면 식은 개수만 알려 주므로 충분하지 않다. 서로 다른 짝 N(N−1)/2개를 실제로 출력해야 하며, 출력 항목 수만으로도 N²에 비례하는 작업이 필요하다.