코딩테스트 - 패스트캠퍼스 챌린지 26일차

수강한 강의

Part 3. 알고리즘 유형별 풀이

Chapter 02 알고리즘
- 다양한 정렬 응용법 (Sort Application)
- 다양한 정렬 응용법 (Sort Application) - 응용법

학습 후기
정렬
오름차순: 1, 2, 3, 4... 뒤로 갈수록 숫자가 커지는 경우
내림차순: 9, 8, 7, 6... 뒤로 갈수록 숫자가 작아지는 경우

알고리즘에서 정렬을 사용하는 포인트

1. 정렬 조건이 필요하다

class Item implements Comparable<Item> {
    public int num;
    public int idx;

    @Override
    public int compareTo(Item o) {
        return num - o.num;
    }
}

compareTo 함수에서 return 값이 음수이면 num가 먼저, return 값이 양수이면 파라미터로 받는 o.num가 먼저 정렬된다.
같으면 자리를 바꾸지 않는다. 위의 코드는 오름차순 정렬 예시이다.

2. 시간 복잡도는 약 O(N log N)이다.
N개의 원소를 정렬하는 것은 O(N log N)만큼의 시간 복잡도를 갖는다. N이 만약 10만이면 100000 * log 100000(여기서 로그는 밑이 2)이고 log 100000은 약 16이기 때문에 160만 번의 연산이 필요하고 컴퓨터는 1초에 대략 1억 번의 연산을 하기 때문에 시간 복잡도 O(N log N)은 충분히 연산이 가능하다.

3. In-place / Stable 여부를 알아야 한다.
In-place: 정렬하는 과정에서 N에 비해 충분히 무시할 만한 개수의 메모리만큼만 추가적으로 사용하는가? 많이 안 쓰면 In-place
Stable: 같은 값을 정렬할 때 위치가 보존되는가? 보존되면 Stable

Java Arrays.sort()	Primitive 원소 정렬	Object 원소 정렬
정렬 방식	Dual-Pivot Quick Sort	Tim Sort
최선 시간 복잡도	O(N)	O(N)
최악 시간 복잡도	O(N^2)	O(N log N)
평균 시간 복잡도	O(N log N)	O(N log N)
	In-place Sort	Stable Sort

정렬의 특성
1. 같은 정보들은 인접해 있을 것이다.
2. 가장 가까운 원소는 자신의 양 옆 중에 있다.

문제를 풀기 전 정렬의 특성을 알고 정렬 활용만으로도 쉽게 풀리는 문제가 많으니 잘 기억해두자.

이번 강의에서 푼 문제
https://www.acmicpc.net/problem/10825

10825번: 국영수

https://www.acmicpc.net/problem/1015

1015번: 수열 정렬

https://www.acmicpc.net/problem/11652

11652번: 카드

https://www.acmicpc.net/problem/15970

15970번: 화살표 그리기

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.