[Java] 백준 - 알고리즘 수업(수행시간)

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

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.

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

다음의 시간복잡도는 O(1) <<입력값에 상관없이 항상 일정한 결과를 냄
나누기가 한 번 실행되므로 복잡도는 1
(입력과 관계없는 문제!)

//알고리즘 수업

import java.util.Scanner;

public class A_24262 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        System.out.println(1);//수행횟수
        System.out.println(0);//최고차항-식이1이므로 0
    }
}

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

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간

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

import java.util.Scanner;

public class A_24263 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();

        System.out.println(n);//수행횟수
        System.out.println(1);//수행횟수를 다항식으로 나타내었을 때, 최고차항의 차수
    }
    
}

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(1 ≤ n ≤ 500,000)이 주어진다.
<< 입력은 int로 가능하지만 출력은 불가능

숫자의 입력가능, 출력 범위도 잘 확인하기...

#int
500000
891896832

#long
500000
250000000000

import java.util.Scanner;

public class A_24264 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        sc.close();

        System.out.println(n*n);//수행횟수
        System.out.println(2);//수행횟수를 다항식으로 나타내었을 때, 최고차항의 차수
    }
}

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;
}

수학적으로 헷갈려서 식 바꿔서 확인함ㅎ

import java.util.Scanner;

public class A_24265 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        sc.close();

        // int sum=0;
        // for(int i=1;i<n;i++){
        //     for(int j=i+1;j<=n;j++){
        //         sum+=1;
        //         System.out.println(sum+" i:"+i+" j:"+j);
        //     }
        // }
        // System.out.println(sum);

        System.out.println(n*(n-1)/2);//수행횟수
        System.out.println(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;
}

import java.util.Scanner;

public class A_24266 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        sc.close();

        System.out.println(n*n*n);//수행횟수
        System.out.println(3);//수행횟수를 다항식으로 나타내었을 때, 최고차항의 차수
        
    }
}

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;
}

이거를 어떻게 다항식으로 풀지..?
절대 브론즈2의 문제가 아님.. 배신감.. 백준선생님 저 슬퍼요

import java.util.Scanner;
public class A_24267 {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       long n = sc.nextInt();
       sc.close();

       if(n==1||n==2) System.out.println(0);
       else System.out.println((n-2)*2*(n-1)*3*n/36);//수행횟수
       System.out.println(3);//수행횟수를 다항식으로 나타내었을 때, 최고차항의 차수
   }
}

이리저리 수식써보다가 성공 !!!! 이 맛에 코딩합니다ㅜㅜ

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

알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.
O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}
f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.
만족하면1, 아님0

위 식에 맞춰 a1n0+a0 <= cn0 식만 넣었을 때 틀림ㅜㅜ
이유를 살펴보니 수식을 살펴보면 a1이 c보다 커질 경우 수식은 맞지 않음..(함수 기울기의 조건)때문에 a1<=c 라는 조건이 추가로 필요하다!

import java.util.Scanner;

public class A_24313 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a1= sc.nextInt();
        int a0= sc.nextInt();
        int c= sc.nextInt();
        int n0= sc.nextInt();
        sc.close();

        if( (a1*n0+a0 <= c*n0) && a1<=c) System.out.println(1);
        else System.out.println(0);
    }
}