간략한 요약
이 강의에서는 정렬 알고리즘에 대해 다루며, 인터페이스와 데이터 구조의 중요성을 강조합니다. 집합(Set) 인터페이스를 구현하는 다양한 방법을 살펴보고, 정렬되지 않은 배열과 정렬된 배열을 사용하여 집합을 구현할 때의 효율성을 비교합니다. 또한, 선택 정렬(Selection Sort)과 병합 정렬(Merge Sort) 알고리즘을 소개하고, 각 알고리즘의 시간 복잡도를 분석합니다.
- 인터페이스와 데이터 구조의 차이점을 이해하고, 적절한 데이터 구조를 선택하는 것이 중요합니다.
- 정렬되지 않은 배열을 사용한 집합 구현은 간단하지만 비효율적입니다.
- 선택 정렬은 O(n^2)의 시간 복잡도를 가지며, 병합 정렬은 O(n log n)의 시간 복잡도를 가집니다.
소개
강의 소개와 함께, 알고리즘 수업에서 중요한 주제인 인터페이스와 데이터 구조에 대한 간략한 복습이 이루어집니다. 인터페이스는 프로그램 사양을 의미하며, 데이터 구조는 인터페이스를 실제로 구현하는 방법을 나타냅니다. 집합(Set)을 예시로 들어, 다양한 데이터 구조를 사용하여 집합을 구현할 때의 장단점을 설명합니다. 알고리즘을 선택할 때 인터페이스의 정확성과 데이터 구조의 효율성을 고려해야 함을 강조합니다.
집합 인터페이스
집합 인터페이스의 세부 사항을 설명합니다. 집합은 여러 항목을 담는 컨테이너로, 항목을 추가하고 검색할 수 있습니다. 집합의 기본적인 연산으로는 생성, 크기 확인, 검색, 삭제, 삽입 등이 있습니다. 학생 ID를 예시로 들어, 집합 내에서 특정 키를 사용하여 객체를 검색하는 방법을 설명합니다. 집합 인터페이스는 데이터 구조가 아닌, 이러한 연산들을 정의하는 역할만 합니다.
정렬되지 않은 배열
집합을 구현하는 가장 간단한 방법 중 하나인 정렬되지 않은 배열에 대해 설명합니다. 배열에 객체들을 임의의 순서로 저장하는 방식으로, 구현은 간단하지만 효율성은 떨어집니다. 특정 학생이 교실에 있는지 확인하는 쿼리를 예시로 들어, 정렬되지 않은 배열에서 검색하는 데 선형 시간이 걸림을 설명합니다. 삽입, 삭제, 최소값 찾기 등 다른 연산들도 모두 선형 시간이 소요됩니다.
정렬된 배열
정렬된 배열을 사용하여 집합을 구현하는 방법을 소개합니다. 학생 ID를 기준으로 배열을 정렬하여 검색 효율성을 높일 수 있습니다. 정렬된 배열에서는 최소값 찾기, 최대값 찾기 등의 연산이 상수 시간 안에 가능하며, 이진 검색을 통해 특정 요소를 로그 시간 안에 찾을 수 있습니다. 하지만 정렬된 배열을 구축하는 데 추가적인 시간이 소요됩니다.
정렬 소개
정렬 알고리즘의 기본 사항과 관련된 몇 가지 어휘를 소개합니다. 정렬 알고리즘은 n개의 숫자로 이루어진 배열을 입력으로 받아 정렬된 배열을 출력합니다. 파괴적인 정렬(destructive sort)은 정렬된 배열을 새로운 메모리에 저장하는 대신, 기존 배열을 덮어씁니다. 제자리 정렬(in-place sort)은 파괴적인 정렬이면서 추가적인 메모리를 사용하지 않습니다.
순열 정렬
가장 간단한 정렬 알고리즘 중 하나인 순열 정렬(permutation sort)을 설명합니다. 순열 정렬은 가능한 모든 순열을 나열하고, 정렬된 순열을 찾는 방식으로 작동합니다. n개의 숫자에 대한 순열의 수는 n 팩토리얼이므로, 순열 정렬의 시간 복잡도는 최소한 O(n! * n)입니다. 따라서 순열 정렬은 매우 비효율적인 알고리즘입니다.
선택 정렬
선택 정렬(selection sort) 알고리즘을 소개합니다. 선택 정렬은 배열에서 가장 큰 숫자를 찾아 맨 뒤로 보내는 과정을 반복합니다. 재귀적인 방식으로 구현하여, 각 단계에서 최대값을 찾고, 제자리에 배치한 후, 나머지 부분을 정렬합니다. 선택 정렬의 시간 복잡도는 O(n^2)입니다.
병합 정렬
병합 정렬(merge sort) 알고리즘을 설명합니다. 병합 정렬은 분할 정복(divide and conquer) 방식을 사용하여, 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 다음, 두 정렬된 부분을 병합합니다. 두 손가락 알고리즘을 사용하여 두 정렬된 리스트를 선형 시간 안에 병합할 수 있습니다. 병합 정렬의 시간 복잡도는 O(n log n)입니다.
