[BOJ] 11단계 시간 복잡도

1

24262

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String n = reader.readLine();
        /**
         * MenOfPassion(A[], n) {
         *     i = ⌊n / 2⌋;
         *     return A[i]; # 코드1
         * }
         * 코드1의 수행시간: n과 무관하게 1번만 수행됨 (O(1))
         */
        System.out.println("1\n0");
    }
}

 

2

24263

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String n = reader.readLine();
        /**
         * MenOfPassion(A[], n) {
         *     sum <- 0;
         *     for i <- 1 to n
         *         sum <- sum + A[i]; # 코드1
         *     return sum;
         * }
         * 코드1의 수행시간: for문 안에서 n번 수행됨 (O(n))
         */
        System.out.println(n);
        System.out.println(1);
    }
}

 

3

24264

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(reader.readLine());
        /**
         * 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)+(n-2)+...+1 번 수행됨 (O(n^2))
         */
        System.out.println(n*(n-1)/2);
        System.out.println(2);
    }
}

* n*n이 int의 범위를 넘어섬 -> long 사용

 

4

24265

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(reader.readLine());
        /**
         * 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;
         * }
         */
        long cnt = 0;
        for(long i = 1; i < n; i++) {
            cnt += i;
        }
        System.out.println(cnt);
        System.out.println(2);
    }
}

 

5

24266

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(reader.readLine());
        /**
         * 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;
         * }
         * 코드1의 수행시간: 삼중 for문 안에서 n*n*n번 실행 (O(n^3))
         */
        System.out.println(n * n * n);
        System.out.println(3);
    }
}

 

6

24267

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        long N = Long.parseLong(tokenizer.nextToken());

        //int cnt = 0;
        //for(int i = 1; i <= N-2; i++) {
        //    for(int j = i + 1; j <= N-1; j++) {
        //        for(int k = j + 1; k <= N; k++) {
        //            cnt++;
        //        }
        //    }
        //}
        //반복문 범위인 N * (N - 1) * (N - 2) 와 실제 반복되는 횟수(cnt) 사이에서 규칙 찾기
        System.out.println(N * (N - 1) * (N - 2) / 6); //cnt
        System.out.println(3);
    }
}

 

7

24313

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int a1 = Integer.parseInt(tokenizer.nextToken());
        int a0 = Integer.parseInt(tokenizer.nextToken());
        int c = Integer.parseInt(reader.readLine());
        int n0 = Integer.parseInt(reader.readLine());

        //f(n) = a1 * n + a0
        //g(n) = c * n
        for(int i = n0; i <= 100; i++) {
            if(a1 * i + a0 > c * i) {
                System.out.println(0);
                return;
            }
        }
        System.out.println(1);
    }
}