Day06. 알고리즘

코딩 테스트

시간 복잡도

빅 오 표기법

• big-O (빅 오 표기법) : O() => 최악의 경우, worst case
• 점근적 상한선
  • 입력 크기가 무한대로 갈 때점근적 상한
  • (아무리 나빠도시간이 이보다 덜 걸림. 즉, 최악의 시나리오)
    • 주로, 빅 오 표기법을 사용함

계산 방법

1. 가장 큰차수 만 고려 : 예) n2 + n + 1 => O(n2)
2. 계수는 1 로 함 : 예) 3n => O(1n) => O(n)
3. 작은 차이는 무시 : 예) O(n-1) => O(n)
4. 규모가 큰 것 만 고려 : 예) O(2n + n2) => O(2n)

크기 순서

$$ O(1) < O(log n) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(∞) $$

⏩ 오래 걸림

 

공간 복잡도

코딩 테스트에서 문제가 되는 경우는 많지 않음.

재귀 구현할 때 정도?

 

입력

방법: 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일을 입력받는데 걸리는 시간을 측정. 10번 측정해서 평균값으로 순위를 매김

입력 방법	평균(초)
BufferedReader, Integer.parseInt	0.6585
Scanner	4.8448

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

public class Main {

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

        /* 숫자 입력 */
        int i = Integer.parseInt(bufferedReader.readLine());
        long l = Long.parseLong(bufferedReader.readLine());
        double d = Double.parseDouble(bufferedReader.readLine());

        /* 한 줄에 여러 문자 */
        // 공백 없음
        char[] chars = bufferedReader.readLine().toCharArray();
        // 공백으로 구분
        // 방법1) String method : split()
        String[] strings = bufferedReader.readLine().split(" ");
        String s0 = strings[0];
        String s1 = strings[1];

        // 방법2) StringTokenizer st
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());    // 두번째 인자로 구분자 가능
        String s2 = stringTokenizer.nextToken(" ");  // 딜리미터 여기에 넣을 수도 있음
        String s3 = stringTokenizer.nextToken();

        bufferedReader.close();

        /**
         * Scanner sc
         */
        Scanner scanner = new Scanner(System.in);

        String s = scanner.next();  // 공백 전까지 읽음
        String line = scanner.nextLine();
        
        int i1 = scanner.nextInt();
        long l1 = scanner.nextLong();
        double d1 = scanner.nextDouble();

        // 다음 입력 있는지
        boolean hasNext = scanner.hasNext();    // 다음 토큰 있는지
        boolean hasNextLine = scanner.hasNextLine();    // 다음 줄 있는지
        
        scanner.close(); // 다 쓰고 닫기 
    }
}

 

출력

방법: 총 N개의 줄에 1부터 10,000,000까지의 자연수를 한 줄에 하나씩 출력하는 시간을 측정. 10번 측정해서 평균값으로 순위를 매김 

출력 방법	평균(초)
BufferedWriter, bf.write(i + "\n");	0.9581
StringBuilder를 이용해 문자열 하나로 만든 다음, System.out.println(sb);	1.1881
BufferedWriter, bf.write(Integer.toString(i)); bf.newLine();	1.2556
PrintWriter	1.954
System.out.println(i);	30.013

import java.io.IOException;

public class Main {

    public static void main(String[] args) {

        String str = "스트링";
        System.out.println(str);    // IntelliJ 자동완성 : sout
        int i = 0;
        long l = 1_000_000_000_000L;
        double d = 3.14;
        System.out.printf("%d, %d, %.3f, %s", i, l, d, str);      // IntelliJ 자동완성 : souf

    }
}

 

포맷 지정자

지시자	출력
%b	boolean 형식
%d	정수 형식
%o	8진수 정수 형식
%x 또는 %X	16진수 정수 형식
%f	소수점 형식
%c	문자 형식
%s	문자열 형식
%e 또는 %E	지수 표현식

/* 포맷 지정자 문법 */
%<+면 오른쪽 정렬, -면 왼쪽 정렬><넓이><.소수점>지정자