[백준] 24262번~24265번: 알고리즘 수업 - 알고리즘의 수행 시간 - JAVA

[작성일: 2023. 10. 09]

 

https://www.acmicpc.net/problem/24262

 

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(1);
        System.out.println(0);
    }
}

 

MenOfPassion 알고리즘은 입력의 크기 n에 관계없이 return A[i]; (코드 1)는 딱 한 번만 수행된다.

코드1의 수행 횟수는 1번이며 코드1의 수행 횟수를 다항식으로 나타냈을 때 최고차항의 차수는 O(상수항, O(1))이다.

이 코드는 입력값 n을 받아도 실제로 사용하지 않으므로 결과 출력에서 첫 번째 줄은 1을 출력하고, 두 번째 줄은 0을 출력하기만 하면 된다.

 

 

 

 

 

https://www.acmicpc.net/problem/24263

 

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(n);
        System.out.println(1);
    }
}

 

코드1은 sum <- sum + A[i]를 의미한다. 이 구문은 for i <- i to n 반복문 안에 있으므로 n번 수행된다.

sum <- sum + A[i] 구문의 복잡도는 O(1)이지만 이 구문은 n번 반복되므로 전체 복잡도는 O(n)이 되며 최고차항의 차수는 1이다.

 

 

 

 

 

https://www.acmicpc.net/problem/24264

 

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Long n = sc.nextLong();
        System.out.println(n*n);
        System.out.println(2);
    }
}

 

코드1은 sum <- sum + A[i] * A[j]를 의미한다. 이 구문이 위치한 중첩된 두 개의 for 반복문으로 인해 전체적으로 n * n번, 즉 n^2번 수행된다.

구문의 복잡도 자체는 O(1)이지만 중첩된 for문 때문에 전체 복잡도는 O(n) * O(n) = O(n^2)이며, 최고차항의 차수는 2가 된다.

 

그런데 이 문제를 int형으로 받으면 틀렸다고 나온다. 46341 * 46341을 할 경우 int형의 범위를 넘어서기 때문에 Long으로 받았다.

 

 

 

 

 

https://www.acmicpc.net/problem/24265

 

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Long n = sc.nextLong();
        System.out.println(n * (n - 1) / 2);
        System.out.println(2);
    }
}

 

코드1은 i가 1일 때 j는 2부터 n까지 반복하므로 n-1번을 돈다.

전체 수행 횟수는 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2번이 된다.

 

 

이 공식은 1부터 n-1까지의 정수의 합을 나타낼 수 있는데,

n = 5일 경우 1+2+3+4= 10이며, 공식을 사용하면 다음과 같다.

 

 

 

 

 

 

https://www.acmicpc.net/problem/24266

 

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Long n = sc.nextLong();
        System.out.println(n * n * n);
        System.out.println(3);
    }
}

 

 

 

 

 

https://www.acmicpc.net/problem/24267

 

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Long n = sc.nextLong();
        System.out.println(n * (n - 2) * (n - 1) / 6);
        System.out.println(3);
    }
}

 

첫 번째 for문 i는 1부터 n-2까지 반복되므로 n-2번이 반복된다.

두 번째 for문 j는 i+1부터 n-1까지 반복되므로 최대 n-1-i번 반복된다.

세 번째 for문 k는 j+1부터 n까지 반복되므로 최대 n-j번 반복된다.

 

chatGPT

 

이걸 다 계산하면 코드1의 수행 횟수는 n(n-1)(n-2) / 6이 된다.

코드1의 수행 횟수를 다항식으로 나타내면 최고차항의 차수는 n^3이므로 3이 된다.