[ 코딩 테스트 개념 정리 ] 코딩 테스트 기본 개념

1. 코딩 테스트 기본 개념

시간 복잡도

표기법 이름 시간복잡도 설명 예시

O(1)	상수	상수 시간	입력 크기와 상관없이 일정한 실행 시간을 가진다.	배열에서 원소 하나 찾기
O(logn)	로그	로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가한다	이진 탐색 알고리즘
O(n)	선형	선형 시간	입력 크기와 비례하는 실행 시간을 가진다.	선형 탐색 알고리즘
O(nlogn)	로그 선형	선형 로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수와 선형 함수의 곱의 형태로 증가한다.	병합 정렬, 힙 정렬 알고리즘
O(n^2)	이차	이차 시간	입력 크기의 제곱에 비례하는 실행 시간을 가진다.	선택 정렬, 버블 정렬, 퀵 정렬 알고리즘
O(2^n)	지수	지수 시간	입력 크기의 지수에 비례하는 실행 시간을 가진다.	부분집합
O(n!)	계승	팩토리얼 시간	입력 크기의 팩토리얼에 비례하는 실행 시간을 가진다.	외판원 문제

정렬 알고리즘 시간 복잡도

Bubble Sort (버블 정렬)	O(n^2)
Selection Sort (선택 정렬)	O(n^2)
Insertion Sort (삽입 정렬)	O(n^2)
Quick Sort (퀵 정렬)	평균 : O(nlogn) / 최악 : O(n^2)
Merge Sort (병합 정렬)	O(nlogn)
Radix Sort (기수 정렬)	O(kn) / k : 최대 데이터의 자릿수
Arrays.sort()	평균 : O(nlogn) / 최악 : O(n^2)
Collections.sort()	O(nlogn)

모든 문제를 풀기 전에 시간 복잡도를 생각하는 것은 기본 중에 기본이다.

시간 복잡도에 따라 문제를 푸는 방향이 달라지기 때문이다.

백준에는 해당 문제를 몇 초 이내 풀어야 하는지에 대한 정확한 언급이 있고

프로그래머스에는 정확한 언급은 없지만 채점 시 시간 초과를 반환해준다.

사실 가장 이상적인 문제 풀이는 해당 문제를 1초 이내로 푸는 방법이 이상적이다.

자바의 경우 1초 연산을 1억번 연산은 1초의 시간으로 간주 10의 8승 으로 간주한다.

 

각 알고리즘의 시간 복잡도를 알고 데이터의 크기를 적용하여 1억번의 연산을 넘어가는지 확인하는 과정이 필요하다.

데이터 타입 ( 각 데이터 타입 별 자주 쓰이는 Method 정리 까지 )

정수 자료형

자바의 정수를 표현하기 위한 자료형은 대표적으로 int , long 이 있다.

( byte , short 도 있지만 잘 사용 x )

정수형 타입 할당되는 메모리 크기 데이터의 표현 범위

byte	1바이트	-128 ~ 127
short	2바이트	-215 ~ ( 215 - 1 ) , -32,768 ~ 32,767
int	4바이트	-231 ~ ( 231 - 1 ) , -2,147,483,648 ~ 2,147,483,647
long	8바이트	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

정수 오버플로우 / 언더플로우정수형 데이터의 타입을 사용할 때에는
반드시 자신이 사용하고자 하는 데이터의 최소/최대 크기를 고려해야 한다.
만약 해당 타입이 표현할 수 있는 범위를 벗어난 데이터를 저장하게 되면, 
오버플로우(overflow)가 발생해 전혀 다른 값이 저장될 수 있기 때문이다.
오버플로우 : 해당 타입이 표현할 수 있는 '최대 표현 범위'보다 큰 수를 저장할 때 발생하는 현상
언더플로우 : 해당 타입이 표현할 수 있는 '최소 표현 범위'보다 작은 수를 저장할 때 발생하는 현상

실수 자료형

자바의 실수를 표현하기 위한 자료형은 대표적으로 float, double 이 있다.과거에는 실수를 표현할 때 float형을 많이 사용했지만, 하드웨어의 발달로 인한 메모리 공간의 증가로 현재에는 double형을 가장 많이 사용한다.따라서 실수형 타입 중 기본이 되는 타입은 double형 이다.

실수형 타입 할당되는 메모리 크기 데이터의 표현 범위 리터럴 타입 접미사

float	4바이트	(3.4 X 10^-38) ~ (3.4 X 10^38)	F 또는 f
double	8바이트	(1.7 X 10^-308) ~ (1.7 X 10^308)	D 또는 d (생략 가능함)

float pi = 3.14F;
double morePi = 3.14159265358979323846;

위의 정수 long 타입 처럼, float 변수에 값을 대입할 때에는 
3.14F 와 같이 F접미사(또는 소문자 f)를 꼭 붙여 주어야 한다.

메소드 활용

 

package CodingTestBasic;

public class CodingTestBasic {

    public static void main(String[] args) {

        //String to Int
        String str = "123";
        int num = Integer.parseInt(str);

        //int to String
        int num1 = 123;
        String str1 = Integer.toString(num1);

        //10진수 ->2진수
        String str2 = Integer.toBinaryString(num);
        System.out.println("2진수: "+str2);

        //10진수->8진수
        String str3 = Integer.toOctalString(num);
        System.out.println("8진수: "+str3);

        //10진수->16진수
        String str4 = Integer.toHexString(num);
        System.out.println("8진수: "+str4);

        //2진수->10진수
        int temp = Integer.parseInt(str2, 2);
        System.out.println("2진수->10진수: "+temp);

        //8진수->10진수
        System.out.println("8진수->10진수: "+Integer.parseInt(str3, 8));

        //둘 중 큰 수 반환 (min도 가능)
        System.out.println("더 큰 수 : "+ Integer.max(3, 5));

        //2진수의 1 개수
        System.out.println("2진수의 1 개수 : "+ Integer.bitCount(num1));

        // 3번째 인덱스에 있는 문자 반환
        String subject = "자바 프로그래밍";
        char charValue = subject.charAt(3);
        System.out.println(charValue);


        //해당 문자열의 index 위치 반환
        String subject1 = "자바 프로그래밍";
        int index = subject1.indexOf("프로그래밍");
        System.out.println("프로그래밍 문자열의 시작 index 는 : "+ index);

        // 해당 문자열의 문자 개수 반환
        String subject2 = "자바 프로그래밍";
        int len = subject2.length();
        System.out.println("문자열의 개수 : " +  len);

        // 해당 문자열의 문자열 치환
        String subject3 = "자바 프로그래밍";
        String newStr = subject3.replace("자바" , "JAVA");
        System.out.println(" before : " + subject3);
        System.out.println(" after : " + newStr);


        // 문자열 잘라내기
        String subject4 = "951211-1234567";
        String firstNum = subject4.substring(0 , 6);
        String secondNum = subject4.substring(7);
        System.out.println(" 처음 잘라낸 문자열 : " + firstNum);
        System.out.println(" 두번째 문자열 : " + secondNum);


        // 알파벳 소,대문자 변경
        String original = "Java Programming";
        String lowerCase = original.toLowerCase();
        String upperCase = original.toUpperCase();
        System.out.println(" 문자열 대문자 -> 소문자 : " + lowerCase );
        System.out.println(" 문자열 소문자 -> 대문자 : " + upperCase );

        // 앞뒤 공백 잘라내기
        String before1 = " 자바 프로그래밍 ";
        String after1 = before1.trim();
        System.out.println( " 앞뒤 공백 자르기 전 : " + before1);
        System.out.println( " 앞뒤 공백 자르기 후 : " + after1);

        // 문자열 변환
        boolean b = true;
        int i = 1;
        long l = 124242L;
        char c = 'c';
        double d = 0.4343;
        float f = 0.5252f;

        System.out.println(" boolean b : " + String.valueOf(b));
        System.out.println(" int i : " + String.valueOf(i));
        System.out.println(" long l : " + String.valueOf(l));
        System.out.println(" char c : " + String.valueOf(c));
        System.out.println(" double d : " + String.valueOf(d));
        System.out.println(" float f : " + String.valueOf(f));



    }

// 결과 값
/*

2진수: 1111011
8진수: 173
8진수: 7b
2진수->10진수: 123
8진수->10진수: 123
더 큰 수 : 5
2진수의 1 개수 : 6
프
프로그래밍 문자열의 시작 index 는 : 3
문자열의 개수 : 8
 before : 자바 프로그래밍
 after : JAVA 프로그래밍
 처음 잘라낸 문자열 : 951211
 두번째 문자열 : 1234567
 문자열 대문자 -> 소문자 : java programming
 문자열 소문자 -> 대문자 : JAVA PROGRAMMING
 앞뒤 공백 자르기 전 :  자바 프로그래밍 
 앞뒤 공백 자르기 후 : 자바 프로그래밍
 boolean b : true
 int i : 1
 long l : 124242
 char c : c
 double d : 0.4343
 float f : 0.5252

*/

}

 

 

참고 사이트

https://hongong.hanbit.co.kr/java-%EC%9E%90%EB%B0%94-%EB%AC%B8%EC%9E%90%EC%97%B4%EC%9D%84-%EB%8B%A4%EB%A3%A8%EB%8A%94-string-%ED%81%B4%EB%9E%98%EC%8A%A4-%EB%A9%94%EC%86%8C%EB%93%9C-%EC%B4%9D%EC%A0%95%EB%A6%AC/

[Java] 자바 문자열을 다루는 String 클래스 메소드 총정리

https://kutar37.tistory.com/entry/%EC%9E%90%EB%B0%94-Integer-%ED%81%B4%EB%9E%98%EC%8A%A4%EC%9D%98-%EB%A9%94%EC%86%8C%EB%93%9C

자바 Integer 클래스의 메소드

https://adjh54.tistory.com/186

[Java/알고리즘] 시간 복잡도, 공간 복잡도, 빅오 표기법 이해하기

https://chb2005.tistory.com/75

[JAVA] 다양한 정렬 알고리즘 개념 및 시간 복잡도 비교

https://inpa.tistory.com/entry/JAVA-%E2%98%95-%EA%B8%B0%EB%B3%B8-%EC%9E%90%EB%A3%8C%ED%98%95-%EC%A2%85%EB%A5%98-%EC%B4%9D%EC%A0%95%EB%A6%AC-int-double-char-String

☕ JAVA 기본 자료형 & 데이터 타입 - 한눈에 정리