1. 개요퀵 정렬(Quick Sort)은 피벗을 하나 정하고, 배열을 피벗을 기준으로 배열을 분할하여 정렬하는 기법이다. 재귀 호출을 사용한다. 2. 시간복잡도어떤 피벗값을 선정하는지에 따라 시간복잡도 차이가 난다.평균 시간복잡도 : 𝛳(nlogn)최악 시간복잡도 : O(n^2) 3. 핵심이론1) 하나의 피벗(기준값)을 정한다. (피벗값 배열의 맨 처음 값으로 설정)2) 시작, 끝 포인터를 설정한다. (시작 s는 0, 끝 e는 배열의 마지막 인덱스로 설정한다.)3) s가 e보다 작을 때까지 순회한다. 3-1) 배열의 마지막 값 (arr[e])이 피벗값 (arr[pivot]) 보다 클때 까지 순회하며, e를 1씩 왼쪽(감소)으로 이동한다. (피벗값보다 작은 값이 나올때까지 순..
코딩테스트
1. 개요선택정렬이란, 배열의 맨 앞 요소를 선택한 후 그 다음 요소부터 가장 작은 값을 찾아 맨 앞 요소와 비교 후 swap 하는 형식의 정렬 알고리즘이다. (오름차순 기준) 2. 시간복잡도모든 배열의 요소를 첫 요소로 잡고 (N), 그 다음 요소부터 끝까지 최소값을 찾아야하므로 (N) 시간복잡도는 O(N^2)이다. 3. 핵심이론- 배열의 크기를 5로 가정51324 - 맨 앞 요소를 선택 후 그 다음 요소부터 최소값을 찾은 후 비교하여 서로 swap 한다.5(맨 앞 요소 선택)1(최소값)32415324 - 위 과정을 반복한다.15(맨 앞 요소 선택)32(최소값)412354 123(맨 앞 요소 선택)54(최소값)12354 1235(맨 앞 요소 선택)4(최소값)12345 - 정렬 완료 4. 예시 코..
1. 버블정렬이란?인접한 두 요소를 비교하여 정렬하는 간단한 알고리즘이다. 왜 버블정렬일까? 가장 큰 요소가 배열의 마지막 위치로 버블처럼 떠오른다고 하여 '버블정렬' 이라는 이름으로 유래됨. 2. 시간복잡도각 정렬 과정마다 다시 한번 배열을 순회하여 인접한 두 요소를 비교해야 하므로 O(N^2) 의 시간복잡도를 가진다. 3. 핵심이론1) 배열 사이즈가 N이라고 가정한다.2) 버블 정렬은 총 (N - 1)번의 과정을 거친다.3) 각 정렬 과정마다 맨 끝 요소는 정렬이 된 상태이므로 (N - i - 1)번 순회한다.4) 이전 요소가 다음 요소보다 크면 swap 진행5) 위 과정 반복 4. 예시아래 N이라는 배열이 있다고 가정하자.543211) 첫번째 순회45321435214325143215 (가장 큰 요소..
구간합을 구하는 핵심 문제이다. 구간합이란 정수가 들어있는 배열 A가 있다고 가정했을때, A배열의 i번재 수에서 j번째 수의 합을 구하는 공식이다. 구간합을 사용하지 않으면 배열 A를 모두 탐색하면서 해당 구간에서 합 연산을 해야하므로, O(n)의 시간복잡도를 가지지만, 구간합을 사용한다면, 이미 만들어진 합배열 S를 이용하여 구간합을 구하므로, 시간복잡도는 O(1)로 감소한다.(즉 성능이 좋아진다는 얘기!) 이러한 이유로 코딩테스트에서 구간합을 구해야하는 로직이 있다면 시간 복잡도를 줄일 수 있으므로, 많이 사용되는 알고리즘이다. 먼저, 합배열 S와 구간합을 구하는 공식을 알아보자.public class PrefixSumEx{ public static void main(String[] args){..
