[BOJ/C] 단계별로 풀어보기 - 시간복잡도

2026.01.05일자 입니다. 시간복잡도 풀어보았습니다.
이번 단계에서는 C++는 사용하지 않았습니다. 계산 문제라서 그냥 다 숏코딩 했습니다.

24262번 알고리즘 수업 - 알고리즘의 수행 시간 1

문제 링크

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

해당 코드는 n에 어떤 값이 입력되어도 한 번만 수행됩니다. 따라서 수행 횟수는 1, 최고차항의 차수는 0입니다.

1
0

텍스트 형식으로 이렇게 작성하여도 정답입니다.

24263번 알고리즘 수업 - 알고리즘의 수행 시간 2

문제 링크

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        sum <- sum + A[i]; # 코드1
    return sum;
}

단순 반복문으로 n번 반복합니다. 따라서 실행 횟수는 n이며 최고차항은 1입니다.

main(n){scanf("%d", &n);printf("%d\n1",n);}

정답 코드입니다.

24264번 알고리즘 수업 - 알고리즘의 수행 시간 3

문제 링크

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

중첩 반복문입니다. n*n번 반복하므로 실행 횟수는 n*n, 최고차항은 2입니다.

main(long long n){scanf("%lld",&n);printf("%lld\n2",n*n);}

정답 코드입니다.

24265번 알고리즘 수업 - 알고리즘의 수행 시간 4

문제 링크

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

중첩 반복문인데 바깥쪽은 1 ~ n-1, 안쪽은 i+1 ~ n으로 이루어져 있습니다.
n-1, n-2, ..., 1번 반복하며 이는 첫째항이 1, 끝항이 n-1인 등차수열과 같으며 따라서 실행 횟수는 (n-1)/2*n이 되고 2차식이므로 최고차항은 2입니다.

main(long long n){scanf("%lld",&n);printf("%lld\n2", n*(n-1)/2);}

정답 코드입니다.

24266번 알고리즘 수업 - 알고리즘의 수행 시간 5

문제 링크

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            for k <- 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

실행 횟수는 n*n*n, 3차식이므로 최고차항은 3입니다.

main(n){scanf("%d",&n);printf("%lld\n3",(long)n*n*n);}

정답 코드입니다.

24267번 알고리즘 수업 - 알고리즘의 수행 시간 6

문제 링크

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

바깥 반복문은 i = 1 ~ n-2, 중간 반복문은 j = i+1 ~ n-1, 안쪽 반복문은 k = j+1 ~ n번 반복합니다.
이를 공식으로 나타내면 다음과 같은데

풀기 귀찮습니다.
이 조건을 다시 생각해본다면 i, j, k는 1부터 n까지의 숫자 중에서 세 가지 숫자를 고르는 경우라고 볼 수 있습니다.
또한 i ＜ j ＜ k 로 순서가 고정되므로 순서를 상관하지 않고 뽑으면 됩니다. 즉 _nC₃입니다.

main(n){scanf("%d",&n);printf("%ld\n3",(long)(n-2)*(n-1)*n/6);}

정답 코드입니다.

24313번 알고리즘 수업 - 점근적 표기 1

문제 링크

O(g(n)) = {f(n) | 모든 n≥n₀에 대하여 f(n)≤c × g(n)인 양의 상수 c와 n₀가 존재한다}

f(n) = a₁n + a₀이고 O(n)의 정의를 만족하는지 알아보자고 했으므로 O(g(n))=O(n)이므로 g(n)=n입니다.
일차식이고 정비례 관계이므로 a₁≤c이며, n₀에서 a₁*n+a₀≤c*n이 참이라면 정의를 만족합니다.

main(a,b,c,d){scanf("%d%d%d%d",&a,&b,&c,&d);printf("%d",a*d+b<=c*d&a<=c);}

정답 코드입니다.