Baekjoon Time-complexity

24262번 문제

 

이 문제는 시간복잡도를 확인하는 문제이다. n을 입력하면 절반으로 계속 줄이고 그 수를 배열의 인덱스로 넣어서 반환해주고 있다.

 

따라서, 이걸 다항식으로 표현하였을 때 미지수로 표현한다면 x라고 표현할 수 있다. 이 x의 시간 복잡도를 표현한다면 O(n) 이다.

 

단지 최고차항의 차수를 출력하고 그게 아니면 0을 출력하는 의미이므로, 출력문 두 개만 존재해도 문제는 풀린다.

public class Main {
	public static void main(String[] args) {
    	System.out.println("1");
        System.out.println("0");
        }
}

 

 

24263 문제

 

 

이 문제는 n을 받아서 1 ~ n까지 입력 받고 있다. 예제 입력 1을 예로 들어보면 1 ~ 7 까지 입력을 받는다. 다시 말하면 7번 반복하였다.

즉, 입력받은 n의 수만큼 반복 횟수가 늘어난다. 따라서 시간 복잡도가 O(n)이 된다.

import java.util.Scanner;

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

 

24264 문제

 

이 문제도 위의 문제에서 반복문 한 번을 더 돌리고 있다. 그러면 시간 복잡도는 O(n^2) 이므로, 다항식으로 나타냈을 때는 n^2으로 나타내고 있고, 밑에는 지수인 2를 출력한다.

import java.util.Scanner;

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

 

24265 문제

이 문제의 예제 입력을 살펴보면, n을 7로 설정한다면 i는 1부터 6까지 진행된다. 그 후에 j는 2~7 (6번), 그리고 계속해서 i가 늘어날수록 j의 횟수가 1까지 작아진다. 따라서, 수열의 합인 1 + 2 + 3 + ... + n 인 (n * (n + 1) ) / 2 에서 n대신 n-1 을 대입해서 진행한다면 코드 1의 수행 횟수를 나타낼 수 있고, 최고차항의 차수는 2가 나타난다.

import java.util.Scanner;

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

 

24266번 문제는 O(n^3) 의 문제이므로 생략한다.

 

24267 문제

 

문제를 자세히 살펴보면 우선 반복문이 3번 존재하는 것을 알 수 있다.

예제 입력 1에서 n을 7로 가정하고 i를 1부터 진행해보았을 때, j는 2, 3, 4, 5, 6이 나올 수 있고 각 숫자마다 k가 3, 4, 5, 6, 7 이 존재했다. 따라서, 5 + 4 + 3 + 2 + 1 = 15가지가 나온다.

이렇게 계속해서 진행해보았을 때, 하나의 규칙이 나온다는 것을 발견하였다.

1~n 까지 숫자 중 3가지를 뽑아서 중복을 허용하지 않는 크기 순으로 작성하는 것을 일반화하면 좋을것이라 판단하였다.

따라서, 우리가 고등학교 확률과 통계 시간에 배운 nCr 개념을 활용하여, r은 3가지를 뽑는 것(반복문 3개)이 고정되어 있으므로

nC3의 공식을 일반화하여 진행해보면 ((n - 2) * (n - 1) * n) / 6 이라는 일반화된 식이 나온다. 이를 이용하여 진행해보았다.

 

import java.util.Scanner;

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

 

24313 문제

 

 

O(g(n)) = f(n) 이라는 정의가 존재한다. 문제를 자세히 살펴보면 이 정의를 만족하는지 만족하지 않는지만 판단해주면 되는 것이고, 모든 알고리즘이 문제에서 다 나와있으니 그걸 판단하는 If-else 문만 만들어서 출력해주면 끝나는 굉장히 간단한 문제이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        
        int a1 = input.nextInt();
        int a0 = input.nextInt();
        
        int c = input.nextInt();
        int n0 = input.nextInt();
       
        boolean isTrue = true;
        
        for (int i = n0; i <= 100; i++) {
            if (f(i, a1, a0) > g(i, c)) { 
                isTrue = false;
                break;
            }
        }
        
        if (isTrue) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
    
    public static int f(int n, int a1, int a0) {
        return a1 * n + a0;
    }
    
    public static int g(int n, int c) {
        return c * n;
    }
}