[Do it 알고리즘 코딩테스트] JAVA

시간복잡도

1. 시간복잡도 : 알고리즘 선택의 기준 / 주어진 문제를 해결하기 위한 연산 횟수

1) 유형 : 빅오메가_최선일 때(i=0 -->1번) / 빅세타_보통일 때(i=50 --> N/2번) / 빅오_최악일 때(i=99 --> N번)

=====> 시간복잡도 코딩 테스트는 최악의 케이스를 염두에 두는 것 -> 빅오일 때를 기준으로 수행시간을 계산해야 함!!

본인이 짠 코드의 시간복잡도에 대해서 알아두는 것이 좋다.

※연산횟수 = 알고리즘 시간 복잡고 X 데이터의 크기

(버블정렬= N^2 / 병합정렬 = NlogN)

시간복잡도 도출 기준

1) 상수는 시간 복잡도 계산에서 제외한다 -> N이나 3N이나 똑같다

2) 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다. -> 이중포문으로 시간복잡도가 N^2이 되면 10개의 일반포문이 추가되어도 N^2이다.

맞는 알고리즘 -> 시간초과 ==> 로직이 효율적으로 짜여있는지를 확인

1. 알맞은 알고리즘 선택 기준 2. 비효율적인 로직 찾아서 효율적으로 바꾸기(중첩문을 확인)

디버깅

1. 디버깅 --> 논리오류 잡는데 도움을 주는 스킬

오류 주의

** 변수 초기화 위치

** 자료형은 처음부터 long형으로 선언하자! --> 디버깅시 변수값이 음수가 나오면 범위를 초과한 것

자료구조

(1) 배열과 리스트

배열: 연속공간에 값이 채워져 있는 형태의 자료구조 / 인덱스를 통해 참조할 수 있음 --> A[3] / 값을 삽입하거나 삭제하려면 주변 값을 이동시키는 과정이 필요 / 배열 크기 한번 선언하면 변경할 수 없다.

리스트: 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 / 인덱스가 없어서 head포인트 순서대로 접근해야 함 -> 접근 속도가 느리다 / 데이터 삽입&삭제 연산속도 빠르다 / 선언시 크기를 지정하지 않아도 된다. 리스트는 크기가 정해져 있지 않다. / 배열보다 구조가 복잡

==> 실제 코딩테스트: 크기 픽스 or 데이터 접근 --> 배열 사용 / 크기가 변하는 데이터 or 데이터 삽입&삭제 많은 경우 -> 리스트(ArrayList,LinkedList) 사용

(2) 구간합

합 배열을 이용해서 시간복잡도를 줄이기 위해 사용하는 특수한 목적의 알고리즘

i 에서 j까지의 구간 합 = S[j] - S[i-1]

(3) 스택과 큐

스택 : 삽입과 삭제가 한 쪽에서만 일어남(top부분에서만 연산이 일어남) --> 후입선출 / 깊이우선탐색, 백트래킹 종류, 재귀함수 알고리즘 원리

- top : 삽입과 삭제가 일어나는 위치

- push : top 위치에 데이터 삽입

- pop : top 위치에 있는 데이터를 삭제하고 확인

- peek : top 위치에 있는 데이터를 확인

큐 : 삽입과 삭제가 양방향에서 일어남 -> 선입선출 / 너비우선탐색,

- rear : 큐에서 가장 끝 데이터 -> 삽입 부분

- front : 큐에서 가장 앞의 데이터 -> 삭제 부분

- add : rear 위치에 데이터 삽입

- poll : front 위치에 있는 데이터를 삭제하고 확인

- peek : front 위치에 있는 데이터를 확인

cf. 우선순위 큐 : 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

정렬

버블정렬	인접데이터끼리 비교하고 swap연산 수행하며 정렬
선택정렬	가장 크거나 작은 데이터를 찾아서 선택 반복하며 정렬
삽입정렬	대상을 선택 -> 정렬된 영역에서 적절한 위치를 찾아 삽입하며 정렬
퀵정렬	피봇값을 정해 해당 값을 기준으로 정렬
병합정렬	이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬
기수정렬	데이터의 자릿수를 비교하여 정렬