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

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

---

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

문제 설명:

다음 알고리즘의 수행 횟수를 분석하여 출력하는 문제입니다:

for (i = 1; i < n; i++) {
    for (j = i + 1; j <= n; j++) {
        // 반복문 안의 작업
    }
}

위의 중첩 반복문에서 수행 횟수와 해당 알고리즘의 시간 복잡도를 구하는 것이 목표입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

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

    long long int n; // 입력값 n
    cin >> n;

    // 수행 횟수 계산: (n * (n - 1)) / 2
    cout << (n * (n - 1)) / 2 << '\n';

    // 알고리즘의 시간 복잡도 계수
    cout << 2 << '\n';

    return 0;
}

예제 입력:

5

예제 출력:

10
2

---

코드 설명

• 핵심 알고리즘: 중첩 반복문에서 수행 횟수를 구하기 위해 이중 반복문에서 수행되는 작업의 총 횟수를 계산합니다.
• 수행 횟수 분석:
  • 외부 반복문은 1부터 n - 1까지 실행됩니다.
  • 내부 반복문은 i + 1부터 n까지 실행되므로, 각 i에 대해 (n - i)번 실행됩니다.
  • 총 수행 횟수는 ∑(n - i) = (n * (n - 1)) / 2로 계산됩니다.
• 시간 복잡도: 이중 반복문으로 인해 시간 복잡도는 O(n²)입니다.

---

결과

입력된 n에 대해 이중 반복문의 총 수행 횟수와 알고리즘의 시간 복잡도 계수(2)를 출력합니다. 이 문제는 반복문 분석과 시간 복잡도 이해를 연습하기에 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!