[BOJ 24264] 알고리즘 수업 - 알고리즘의 수행 시간 3 - [수학, 구현]

[BOJ 24264] 알고리즘 수업 - 알고리즘의 수행 시간 3 - [수학, 구현]

문제 링크

https://www.acmicpc.net/problem/24264

문제 요약

이중 for문으로 구성된 MenOfPassion 알고리즘이 주어졌을 때, 입력 크기 에 대한 코드1의 수행 횟수와 시간 복잡도 다항식의 최고차항 차수를 출력하는 문제.

접근 방법

• 알고리즘 분석:
• 외부 for문이 $1$부터 $n$까지 $n$회 반복됩니다.
• 내부 for문도 $1$부터 $n$까지 $n$회 반복됩니다.
• 따라서 코드1(sum <- sum + A[i] * A[j])의 총 수행 횟수는 $n × n = n^2$ 회입니다.

• 자료구조 (핵심):
• 입력 $n$의 최대 크기는 입니다.
• 수행 횟수 $n^2$은 $500,000×500,000=250,000,000,000(2,500억)$이 됩니다.
• 이는 C++의 int 자료형 표현 범위(약 21억)를 넘어가므로, 반드시 long long 자료형을 사용해야 합니다.

• 차수:
• 실행 횟수가 $n^2$이므로, 최고차항의 차수는 2입니다.

풀이 코드

#include <iostream>

using namespace std;

int main() {
    // 입출력 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n; // n^2 계산을 위해 long long 사용 권장 (입력 자체는 int 범위지만 계산 결과 고려)
    cin >> n;

    // 1. 수행 횟수 출력
    // n * n 결과가 int 범위를 넘으므로 long long 연산이 되도록 주의
    cout << n * n << "\n";

    // 2. 최고차항의 차수 출력
    // 시간복잡도가 O(n^2)이므로 차수는 2
    cout << 2 << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도:$O(1)$
• 문제 풀이 로직은 곱셈 연산 한 번과 출력만 수행하므로 상수 시간입니다. (알고리즘 자체의 시간 복잡도는 $O(n^2)$)

• 공간 복잡도:$O(1)$
• 변수 하나만 사용합니다.

실행 결과

• 메모리: 2020 KB
• 시간: 0 ms

핵심 포인트

1. 자료형 선택: $n = 500,000$일 때 $n^2$은 int 범위를 초과하므로 long long을 사용해야 한다는 점이 가장 중요합니다. 이 부분을 놓치면 '틀렸습니다'를 받게 됩니다.
2. 시간 복잡도: 이중 중첩 루프는 $O(n^2)$ 복잡도를 가지며, 이는 2차 다항식임을 이해해야 합니다.

예제 확인

• 예제 1:
• 입력: 7
• 출력:

  49
  2
  

```

• 설명: $7 × 7 = 49$회 수행되며, $n^2$에 비례하므로 차수는 2입니다. 예제 출력과 일치합니다.