[JAVA] 시간 복잡도 단계

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

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
//import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


    System.out.println(1);
    System.out.println(0);
  

    br.close();
    

  }
}

똑같이 상수 시간이 걸리니 1하고 0만 출력하면 됨

 

---

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
//import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int a = Integer.parseInt(br.readLine());
    
    System.out.println(a);
    System.out.println(1);
  

    br.close();

  }
}

---

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
//import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    long a = Integer.parseInt(br.readLine());
    
    System.out.println(a*a);
    System.out.println(2);
  

    br.close();
    

  }
}

50만 * 50만은 int형의 범위를 넘어버리므로 long형으로 저장한다. Int형으로 저장해도 정상적으로 작동함(실수로 한건데 맞았다고 나옴..)

나는 입력이 범위 안이라서 괜찮을 줄 알았는데 출력까지 범위를 생각해야 한다.

 

---

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
//import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    long a = Integer.parseInt(br.readLine());
    
    System.out.println(((a-1)*a)/2);
    System.out.println(2);
  

    br.close();
    

  }
}

두번째 루프만 신경쓰면 되는데, 두번째 루프는 n-1, n-2, n-3, ..., 1만큼 수행하는 등차수열이다.

따라서 등차수열 공식 (a-1)*a /2를 적용하면 된다.

 

---

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
//import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    long a = Integer.parseInt(br.readLine());
    
    System.out.println(a*a*a);
    System.out.println(3);
  

    br.close();
    

  }
}

Math.pow()를 이용해 거듭제곱을 계산했는데, 이 메서드는 double형을 사용하므로 계산하면 오차가 날 수 있다고 한다.

double, float형을 부동소수점 자료형이라 하는데 이런 애들은 큰 값을 표현할 때 약간의 오차가 있어 계산에서 사용하면 오류가 있을 수 있음!

 

---

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
//import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    long a = Integer.parseInt(br.readLine());
    
    System.out.println((a*(a-1)*(a-2))/6);
    System.out.println(3);
  

    br.close();
    

  }
}

입력 받은 a를 7이라 할 때,

첫번째 루프는 1,2,3,4,5까지 실행

i가 1일 때, 두번째 루프는 2,3,4,5,6까지 실행

j가 2일 때, 세번째 루프는 3,4,5,6,7까지 실행

j가 3일 때, 세번째 루프는 4,5,6,7까지 실행

.

.

.

1을 (n-2)번, 2를 (n-1)번, ... , (n-2)를 1번 곱해준다.

 

그러나 이것은 결국 1부터 a까지의 숫자 중 3개의 수를 뽑아 순서대로 나열한 것과 같다.

즉, aC3이다..!

이 공식은 a*(a-1)*(a-2)/6과 같다. 

 

---

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
//import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    
    int a1 = Integer.parseInt(st.nextToken());
    int a0 = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(br.readLine());
    int n = Integer.parseInt(br.readLine());
    
    if(a1*n + a0 <= c*n && c>=a1) System.out.println(1);
    else System.out.println(0);
  

    br.close();
    

  }
}

a1*n + a0 <= c*n에 n0을 대입해서 성립하는지 확인한다.

단, a0이 음수인 경우 성립하지 않을 수도 있다. 이런경우 a1>=c 라는 조건이 있으면 무조건 성립한다.

모든 n>=n0이므로 성립하는 것이다.

 

---

# 회고

 

대략적인 차수까지는 쉬운데, 자세한 수행횟수는 식이 복잡해지면 어렵다.

특히 6번처럼 공식을 유도해내는 건 정말 어렵다...그리고 저 공식도 까먹었음 ㅜ