자알인 (1) 코딩테스트 팁

 

 

- 연습장과 필기도구를 준비하는 것이 좋다 

- 코드 스피넷을 만들어두면 좋다 : 본인이 어려웠던 알고리즘 위주, 복습과 원리를 학습하는 차원에서도 좋고, 사용할 수 있다면, 빠르게 가져올 수 있음 

- 타임아웃오류 : 자바는 거의 자유로우나, 자바의 컬렉션을 사용하면 타임아웃이 발생하는 경우도 있으니 조심하자

- 예외처리 조심하자 (null값 참조 등 -> 실수하는경우 종종 발생)

- 본인만의 시간제한을 두고 푸는 연습을 하는 편이 좋다

- REPL로 코드를 검증하는 연습도 해두면 좋다고함! 

 

2. 자바 자료형

 

-> 속도면에서 당연히 원시자료형이 연산이 빠름 

 ex) 배열에 데이터 1억개 집어넣고, 찾는 연산 -> 원시(int -> 삽입:128밀리초,탐색:26밀리초, Integer:847밀리초, 46밀리초)

-> int로 배열을 생성하면 newarray, Integer배열 생성시 anewarray => 각각 신규배열,신규참조배열 생성 -> 메모리 4배가량 차이남 

 

List ->  ArrayList:동적배열구현 시쿼스 형태 

           LinkedList: 연결리스트 구현 자료형, 이중 연결리스트로 되어있다.

           Set과 Queue도 같은 Collection을 상속받아서, 동일한 메서드들 있음 

 

Map -> HashMap: 해시테이블 구조 자료형, 입력순서 보장 x

        -> LinkedHashMap: 입력 순서 보장하는 해쉬맵

        -> TreeMap: 값을 순서에 따라 정렬 -> 내부적으로 자가 균형 이진 탐색 트리 (레드-블랙트리)임

* TreeMap과 HashMap은 내부 구현만 다르고, 인터페이스 동일 

 

BigInteger : 무한대 숫자 크기를 저장할 수 있는 자료형 -> 계산속도가 느리다는 단점 존재!

 

2.1 컬렉션 프레임워크의 속도

 

List<Integer> listElements = new ArrayLtst<>();
for (int t = 0; i. < 100000000 - 1; t++)
listElements.add(1);
listElements.add(2);
// ArrayLtstcInteger그 1억 개 중 찾기
listElements.contains(2);


//삽입속도 : 2791,밀리초  탐색속도:98밀리초

-> 참조자료형이자 동적 배열 > 동적배열은 배열의 크기가 넘어가는 숫자를 저장하기 위해 초기값의 1.5배씩 배열의 크기를 늘림(더블링)

-> 만약 처음부터 ArrayList의 크기를 크게 한다면 더블링 과정이 사라져 좀 더 빠르게 삽입가능

 

3. 빅오 

 

- 빅오는 점진적 실행시간을 표기하기 위한 방법 (입력값 n에 따른 실행시간)

- 구체적인 연산 횟수보다 입력값에 따른 알고리즘 실행시간 추이만 따진다.

 

O(1) : 입력 값이 커져도, 실행 시간이 일정함

public int big1(int n){
	return 42;
}

ex) 배열에서 값을 조회할 때, 연결리스트의 끝에 값을 삽입할 때

 

 

O(logn) : 입력값을 계속 반으로 나눈다고 생각해보자 -> 연산횟수는 log2N과 같다  

while(n>1)
	n =/ 2;
return n;

ex) 이진 탐색

 

 

 

O(N): 정확하게 입력값 만큼 실행 -> 실행 시간이 선형으로 늘어남 -> 선형 시간 알고리즘

ex) 정렬되지 않은  리스트에서 최댓값,최솟값을 찾는 경우 

 

O(nlogN) : 입력값을 순회하며, logn연산이 곱해짐 (입력값 만큼 순회하면서, 각 순서에 해당하는 값 반으로 계속 나누기)

for (Int i = 0; i < n; i++) {
while (n > 1)
n /= 2;
n = r；
}

ex)병합정렬을 비롯한, 효율적인 정렬 알고리즘들이 위와 같은 빅오를 가짐 

O(n)과 거의 비슷한 성능

 

O(n^2) : 중첩으로 반복하면서 하는 연산 

ex) 버블정렬 

-> 대부분 코테에서 알고리즘 최적화라 한다면, N^2을 nlogn으로 바꾸는 작업들이다.

 

O(2^n) : 입력값의 크기만큼  2배씩 연산함 -> 시간 복잡도가 아주 구림 

ex)피보나치 재귀적 구현 

 

O(n!) :  입력값 순회하면서, 다시 값을 줄이며 재귀호출 -> 가장 구린 알고리즘 n이 100만되어도 못씀 

public int fn(int n) {
for (int i = 0; i < n; i++)
fn(n - 1);
return n;
}

 

3.1 빅오를 계산하는 실용적인 방법

 

-> 정확하게 계산하는 방법은 count같은걸 넣어서 ++하고 종료시 출력해보기

-> 분할상한분석: 최악의 경우의 빅오를 여러 번에 걸쳐 나눠주는 형태로 알고리즘 시간복잡도 계산 

-> 병렬화 

 

 

4. 자바 컬렉션 프레임워크와 빅오