쿠딩 교육 - 1

시간복잡도 빅오표기법 교육용문제

풀이법 마다 시간복잡도가 다르지만 내 코드의 시간복잡도로 표현

1. 3355 - O(1)

프로젝트 오일러의 1번 Multiples of 3 and 5 과 동일하다

#include <stdio.h>

int T, N;

void load() {

    scanf("%d", &N);

}

// 각 수식은 N값에 관계없이 상수시간에 처리되므로 O(1) 이다

void solve() {

    int ans = 0;

    int p;

    N--; // n보다 작은

    // sum(n) = 1+2+3+...+n = n*(n+1)/2

    // 1000보다 작은 5의 배수의 경우

    // 5+10+15+...+995 = 5 *(1+2+3+...+199)

    // 199 = (N-1)/5

    p = N / 3; ans += 3 * (p*(p + 1) / 2);

    p = N / 5; ans += 5 * (p*(p + 1) / 2);

    p = N / 15; ans -= 15 * (p*(p + 1) / 2);

    printf("%d\n", ans);

}

int main() {

    scanf("%d", &T);

    while (T--) {

        load();

        solve();

    }

    return 0;

}

2. bitlen - O(log n)

각 숫자의 이진 길이를 구하는 문제

#include <stdio.h>

int T, n;

void load() {

    scanf("%d", &n);

}

// 각 숫자 n에 대해서 log_2 n 번 연산하면 된다.

// O(log n)

void solve() {

    int ans = 0;

    while (n) {

        ans++;

        n >>= 1;

    }

    printf("%d\n", ans);

}

int main() {

    scanf("%d", &T);

    while (T--) {

        load();

        solve();

    }

    return 0;

}

3. line - O(n)

n의 순열을 구하는 문제

#include <stdio.h>

int T, n;

void load() {

    scanf("%d", &n);

}

// n! 을 구하는 연산의 회수는 1*2*3*...*n

// n번이므로 O(n)

void solve() {

    long long ans = 1;

    for (int i = 1; i <= n; ++i) {

        ans *= i;

    }

    printf("%lld\n", ans);

}

int main() {

    scanf("%d", &T);

    while (T--) {

        load();

        solve();

    }

    return 0;

}

4. mat_max - O(n^2)

2차원 정사각행렬의 최대값을 구하는 문제

#include <stdio.h>

int T, n;

int a[100][100];

void load() {

    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < n; ++j) {

            scanf("%d", &a[i][j]);

        }

    }

}

// n*n개의 원소의 값을 확인하므로

// 시간 복잡도 O(n^2)

void solve() {

    int mx = -1;

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < n; ++j) {

            if (mx < a[i][j])

                mx = a[i][j];

        }

    }

    printf("%d\n", mx);

}

int main() {

    scanf("%d", &T);

    while (T--) {

        load();

        solve();

    }

    return 0;

}

5. mat_mul O(n^3)

두 2차원 정사각행렬의 곱을 구하는 문제

#include <stdio.h>

int T, n;

int mat1[100][100];

int mat2[100][100];

void load() {

    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < n; ++j) {

            scanf("%d", &mat1[i][j]);

        }

    }

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < n; ++j) {

            scanf("%d", &mat2[i][j]);

        }

    }

}

// O(n^3)

// [i,k]*[k,j] 연산 수 |i|*|j|*|k| i==j==k==n

// 따라서 O(n^3)

void solve() {

    int ans = 0;

    int mat3[100][100] = { 0 };

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < n; ++j) {

            mat3[i][j] = 0;

            for (int k = 0; k < n; ++k) {

                mat3[i][j] += mat1[i][k] * mat2[k][j];

            }

        }

    }

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < n; ++j) {

            ans += mat3[i][j];

        }

    }

    printf("%d\n", ans);

}

int main() {

    scanf("%d", &T);

    while (T--) {

        load();

        solve();

    }

    return 0;

}

[솔루션/테스트케이스]

kuding_001.zip