백준 24264번 [알고리즘 수업 - 알고리즘의 수행 시간 3](C++) -yes6686- 티스토리

백준 문제 풀이: 24264 [알고리즘 수업 - 알고리즘의 수행 시간 3]

---

문제 링크: https://www.acmicpc.net/problem/24264

문제 설명:

주어진 코드가 수행되는 총 연산 횟수를 계산하는 문제입니다. 입력으로 주어진 n에 따라 코드의 수행 시간이 어떻게 증가하는지 분석합니다.

해당 문제에서는 이중 반복문 구조를 갖춘 알고리즘을 고려하여 총 수행 횟수와 최고차항의 차수를 구해야 합니다.

출력은 다음 두 값을 포함합니다:

• 총 수행 횟수 (최고차항의 계수를 포함한 수행 횟수)
• 최고차항의 차수 (이중 반복문이므로 2차)

---

문제 해결 코드

// C++로 구현된 코드
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    long long int n;
    cin >> n;

    // 총 수행 횟수와 최고차항 차수 출력
    cout << n * n << '\n' << 2;
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 이중 반복문을 가정했을 때, 내부 반복문의 총 수행 횟수는 n ⋅ n입니다.
  • 이로 인해 수행 시간은 O(n²)이며, 출력으로 총 수행 횟수와 최고차항의 차수를 반환합니다.
• 구현 세부사항:
  • 입력값 n을 long long으로 받아 대규모 입력에도 대응할 수 있습니다.
  • n²는 이중 반복문을 통해 수행되는 연산의 총 횟수를 나타냅니다.
  • 차수 2는 알고리즘의 시간 복잡도가 O(n²)임을 나타냅니다.
• 시간 복잡도 분석:
  • 입력값을 처리하는 부분은 상수 시간에 처리되므로 O(1)입니다.
  • 출력값은 이중 반복문의 총 연산 횟수와 차수를 반환하므로 O(1)입니다.

---

결과

입력값 n에 따라 수행 횟수 n²와 알고리즘의 시간 복잡도 차수(2)를 정확히 출력합니다.

해당 문제에 대한 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!