메모
10. 정렬과 탐색
- 널리 사용되는 정렬 및 탐색 알고리즘을 완벽히 이해하는 건 굉장히 가치 있는 일임.
- 많은 정렬 및 탐색 문제는 잘 알려진 알고리즘들을 변용하여 출제됨.
- 여러 가지 정렬 알고리즘의 차이점을 잘 이해하고, 해당 상황에서 어떤 알고리즘이 어울릴지 살펴두는 것이 좋음.
널리 사용되는 정렬 알고리즘
- 아래 정리한 다섯 알고리즘 가운데, 병합 정렬(merge sort), 퀵 정렬(quick sort), 버킷 정렬(bucket sort)관련 문제가 가장 자주 출제됨.
버블 정렬(bubble sort) | 평균 및 최악 실행 시간 : O(n^2), 메모리 : O(1)
- 배열의 첫 원소부터 순차적으로 진행하며, 현재 원소가 그다음 원소의 값보다 크면 두 원소를 바꾸는 작업을 반복함.
- 이런 식으로 배열을 계속 살펴보면서 완전히 정렬된 상태가 될 때까지 반복한다.
선택 정렬(selection sort) | 평균 및 최악 실행 시간 : O(n^2), 메모리 : O(1)
- 심플한 알고리즘이지만 비효율적임.
- 배열을 선형 탐색하며 가장 작은 원소를 배열 맨 앞으로 보낸다. 그 다음에 두 번쨰로 작은 원소를 찾아서 앞으로 보내준다. 이를 정렬될 때까지 반복함.
병합 정렬(merge sort) | 평균 및 최악 실행 시간 : O(nlogn), 메모리 : 상황에 따라 다름
- 병합 정렬은 배열을 절반씩 나누어 각각을 정렬한 다음 이 둘을 합하여 다시 정렬하는 방법임.
- 병합을 처리하는 것이 가장 복잡함.
퀵 정렬 | 실행 시간 : 평균 O(nlogn), 메모리 : O(logn)
- 무작위로 선정된 한 원소를 사용하여 배열을 분할함.
- 선정된 원소보다 작은 원소들은 앞에, 큰 원소들은 뒤로 보냄.
- 배열 분할 작업은 연속된 스왑(swap) 연산을 통해 효율적으로 수행 됨.
기수 정렬(radix sort) | 실행 시간 : O(kn)
- 데이터가 정수처럼 유한한 비트로 구성되어 있는 경우에 사용됨.
- 각 자릿수를 순회해 나가면서 각 자리의 값에 따라 그룹을 나눔.
- 첫 자릿수가 0인 수들은 같은 그룹에 속함.
- 다음 각그룹마다 두 번째 자릿수를 기준으로 다시 정렬을 수행함.
탐색 알고리즘
면접 문제
10.1 정렬된 병합
- 정렬된 배열 A와 B가 주어진다. A의 끝에는 B를 전부 넣을 수 있을 만큼 충분한 여유 공간이 있다. B와 A를 정렬된 상태로 병합하는 메서드를 작성하라.
10.2 Anagram 묶기
- 철자 순서만 바꾼 문자열(anagram)이 서로 인접하도록 문자열 배열을 정렬하는 메서드를 작성하라.
10.3 회전된 배열에서 검색
- n개의 정수로 구성된 정렬 상태의 배열을 임의의 횟수만큼 회전시켜 얻은 배열이 입력으로 주어진다고 하자. 이 배열에서 특정한 원소를 찾는 코드를 작성하라. 회전시키기 전, 원래 배열은 오름차순으로 정렬되어 있었다고 가정한다.
10.4 크기를 모르는 정렬된 원소 탐색
- 배열과 비슷하지만 size 메서드가 없는 Listy라는 자료구조가 있다. 여기에는 i 인덱스에 위치한 원소를 O(1) 시간에 알 수 있는 elementAt(i) 메서드가 존재한다. 만약 i가 배열의 범위를 넘어섰다면 -1을 반환한다.(이 때문에 이 자료구조는 양의 정수만 지원한다.) 양의 정수가 정렬된 Listy가 주어졌을 때, 원소 x의 인덱스를 찾는 알고리즘을 작성하라. 만약 x가 여러 번 등장한다면 아무거나 하나만 반환하면 된다.
댓글