정렬
=> 사용자가 정의한 순서대로 데이터를 나열하는 방법을 이야기한다.
=> 오름차순 혹은 내림 차순으로 출력할 수 있다.
인덱스 0 1 2 3 4
값 1 5 7 9 3
인덱스 0 1 2 3 4
값 1 3 5 7 9
특정한 값을 찾고자 할 때 연산하는 과정을 줄이기 위해 정렬을 한다.
이진 트리에서 루트를 기준으로 값을 큰거 오른쪽 / 작은거 왼쪽 !!!
정렬 문제는 이진 트리 문제와 관련이 있을 수 있다.
1. 삽입 정렬 => 데이터 영역에서 정렬된 영역과 되지 않은 영역을 나누어서 분리한다.
삽입 정렬 => 최선의 경우 시간 복잡도 O(N)
=> 최악의 경우 시간복잡도 O(N의 2승)
1 4 8 11 16 9 23 2 7 13
정렬된 부분 정렬되지 않은 부분
9가 키값이 된다. 키 => 정렬되지 않은 영역의 맨 앞에 있는 값을 의미한다.
-
정렬된 영역과 정렬되지 않은 영역으로 분류한다.
-
키와 정렬된 영역의 맨 끝 값부터 거슬러 올라가면 정렬한다.
ex) 9와 맨 끝 값인 16으로 부터 -
2번을 반복하여 데이터가 정렬될때 까지 반복한다.
다음과 같은 데이터가 존재한다.
11 4 16 1 8 9 23 2 7 13
이럴땐 11을 정렬된 영역 그 뒤를 정렬되지 않은 영역으로 본다.
4인 키값을 비교 하여 11 과 4 과 바뀌면
4 11 16 1 8 9 23 2 7 13
이렇게 되면 4하고 11까지 정렬된 영역으로 본다. 16은 정렬되지 않은 영역으로 본다.
그러나 시간복잡도에 걸린다.
2. 병합 정렬 => 정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치는 정렬방식이다.(이러한 방식을 "분할 정복"이라고 한다.)
1 5 3 7 2 6 4 8
|
반으로 나눠서
병합 정렬의 핵심은 => 병합할때 부분 정렬하는 부분을 어떻게 구현하는 것이가.
"정렬된 두 배열을 정렬된 상태로 병합하는 로직이 병합 정렬의 핵심이다."
- 포인터 => C언어의 포인터를 의미하는 것은 아니다.
1 3 5 7
2 4 6 8
각 데이터의 맨 처음 데이터인 1과 2를 가리킨다.
O(1) -> 인덱스 1대1 대응
O(n) ->
O(n의 2제곱)
1/2씩 정렬 대상 데이터 개수가 줄어든다.
위상 정렬 : 진입 차수
프로그래머스 문제 : 110 옮기기
https://school.programmers.co.kr/learn/courses/30/lessons/77886?language=java
Queue 큐를 구현하는 방법에는 크게 2가지가 존재한다.
1. 큐의 인터 페이스를 활용하는 방법
2. ArrayDeque를 사용한다. (배열 형식)
자바의 Collection FrameWork에 구현되어 있다.
자주 사용하는 클래스는 ArrayDeque와 LinkedList가 있다.
* 코딩 테스트에서는 ArrayDeque를 아주 많이 사용한다.
큐를 구현하기 위해 ArrayDeque 객체 생성
Queue 인터페이스를 이용하여 데이터를 삽입 및 삭제하기 위해서는 add연산과 poll 연산을 이용한다.
Queue<String> deque = new ArrayDeque<>();
deque.add(1);
deque.add(2);
deque.poll();
Arrays vs Array vs ArrayList
Arrays => java.util 패키지의 일부분이다. 배열을 이용하기 위해 다양한 메서드를 제공(정렬, 검색, 삽입, 삭제등과 같은 여러가지 메서드를 가지고 있다.)
Array => 선형 자료 구조 중 하나이다. 동일한 타입의 연관된 데이터를 메모리에 연속적으로 저장하여 하나의 변수에 묶어서 사용한다.
ArrayList => 자바의 List 인터페이스를 상속 받은 하나의 클래스이다.
Arrays.toString() => toString은 Object class에 포함
인스턴스에 대한 정보를 문자열로 반환한다.(문자열로 제공할 목적으로 정의되어 있다.)
요세푸스 문제 변환
pucblic int solution(int N, int K){
ArrayDeque<Integer> deque = new ArrayDeque<>();
for(int i=1; i <= N; i++){
deque.addList(i);
}
while (deque.size() > 1){
for(int i = 0; i < K - 1; i++){
deque.addLast(deque.pollFirst());
}
deque.pollFirst();
}
return deque.pollFirst();
}
📌 예제 실행 (N=5, K=2)
초기 상태: [1, 2, 3, 4, 5]
1 → 뒤로 보냄, 2 제거 → [3, 4, 5, 1]
3 → 뒤로 보냄, 4 제거 → [5, 1, 3]
5 → 뒤로 보냄, 1 제거 → [3, 5]
3 → 뒤로 보냄, 5 제거 → [3]
👉 마지막에 남은 사람: 3
백준 - 주유소
