알고리즘 풀이 기준
시간 복잡도 표기법
알고리즘에서의 시간 복잡도는 문제를 해결하기 위한 연산 횟수
1억 번의 연산 = 1초의 시간으로 간주하여 예측
시간 복잡도 정의
- 빅-오메가 Ω(n) : best case
- 빅-세타 θ(n) : average case
- 빅-오 Ο(n) : worst case
코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋음
1개의 테스트 케이스로 합격, 불합격을 결정하지 않음
다양한 테스트 케이스를 수행해 통과해야하므로 시간 복잡도를 판단할 떄는 최악일 때를 염두
빅-오 표기법의 시간 복잡도는 데이터의 크기가 증가함에 따라 성능이 달라짐
- 크기가 증가할수록 성능이 낮음
시간 복잡도 활용
버블 정렬 O(n²)
인접한 두 원소를 검사하여 정렬
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환
index 0 과 1 를 비교, 1 - 2 , 2 - 3, 3 - 4 ...이런식으로 서로 자료의 크기를 비교하며 자료를 정리
1회 사이클이 돌면 제일 큰 자료가 맨 뒤로 이동, 그 후 다음 사이클에서는 맨 마지막 자료는 정렬에서 제외
장점 : 구현이 매우 간단
단점
그 외 모든 것
순서에 맞지 않는 요소를 인접한 요소와 교환
한 요소가 움직일 때 모든 요소를 교환 함 (가장 큰 요소가 맨 앞일 경우)
거의 쓰이지 않음
병합 정렬 O(n log n)
비교 기반 정렬 알고리즘, 안정 정렬에 속하며, 분할 정복 알고리즘
정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할
부분리스트가 하나만 남을 때까지 반복해서 병합하여 정렬된 부분리스트를 생성, 마지막으로 남은 리스트가 정렬된리스트
장점
안정적인 정렬 방법, 데이터 분포에 영향을 덜 받음. 정렬되는 시간은 동일
[링크드리스트]로 구성하면 인덱스만 변경되고, 모든 정렬보다 효율적이게 됨
단점
배열로 구성하면 임시 배열이 필요, in-place sorting 이 아님
레코드들이 크다면 이동 횟수가 많아서 시간낭비가 심함
버블정렬
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class main01 {
public static void main(String[] args) throws IOException {
// 스캐너를 써도 되지만 버퍼리더를 사용하는것을 추천
// Scanner sc = new Scanner(System.in);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuffer sb = new StringBuffer();
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
// 선택정렬
for (int i = 0; i < n -1; i++) {
for (int j = i + 1; j < n ; j++) {
// > 오름차순 < 내림차순
if (arr[i] > arr[j]) {
// 자리변경
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
for (int val : arr) {
System.out.println(val);
}
}
}
Arrays.sort()
// Arrays.sort
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 처음껀 당연히 여기서 받음
int n = Integer.parseInt(br.readLine());
// 받은 수로 배열의 사이즈 정함
int[] arr = new int[n];
// for 문이 받은 n의 수로 돌아감
for (int i = 0; i < n; i++) {
// BufferedReader를 받아야 for문이 돌아감
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
for (int val : arr) {
sb.append(val).append('\n');
}
System.out.println(sb);
}
카운팅 정렬
// 카운팅 정렬 + BufferedReader + StringBuilder
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
/*
range : -1000 ~ 1000
0 은 index[1000] 을 의미
*/
boolean[] arr = new boolean[2001];
for (int i = 0; i < n; i++) {
arr[Integer.parseInt(br.readLine()) + 1000] = true;
}
// 정렬 과정이 따로 필요 없음
for (int i = 0; i < 2001; i++) {
if (arr[i]) {
sb.append(i - 1000).append('\n');
}
}
System.out.println(sb);
}