CS 면접 준비 - 알고리즘(지속 업데이트 예정)
1. 정렬 알고리즘에 관해서 설명을 해주세요.
정렬 알고리즘은 특정한 기준에 따라 정렬하여 후의 탐색과정을 편하게 하기 위해 사용합니다. 정렬 알고리즘에는 버블 정렬, 선택 정렬, 삽입 정렬 같은 간단하지만, 시간 복잡도가 n^2인 정렬 방식이 있고, 분할 정복을 활용한 퀵 정렬, 병합 정렬, 힙정렬과 같은 nlogn인 정렬 방식이 있습니다.
※ 그러면, 병합 정렬이나 퀵 정렬이 가장 빠른가요? 단점은 없나요?
시간 복잡도가 삽입 정렬의 경우에는 이미 정렬이 된 경우 가장 빠르고 반대로 병합이나 퀵정렬에서는 느립니다. 하지만 일반적인 경우에는 빠릅니다. 그리고 공간 복잡도가 상대적으로 큽니다. 메모리가 중요한 경우에는 병합정렬이나 퀵 정렬보다는 원소의 개수만큼만 사용하는 삽입 정렬을 고려해야한다 생각합니다.
※ 참고용
선택 정렬: 현재 위치에 들어갈 최소값 혹은 최대값을 찾아 위치를 바꾸면서 정렬을 하는 방법, 공간 복잡도는 낮지만 시간 복잡도는 모든 요소를 검사하기 때문에 O(n^2)이다.
삽입 정렬: 현재 위치에서 그 이하의 배열들을 비교하며 본인이 들어갈 위치를 찾아 삽입하는 알고리즘이다. 이미 정렬이 된 경우, 시간 복잡도가 O(n)이며, 최악의 경우는 O(n^2)이다. 공간복잡도는 O(n)이다.
버블 정렬: 매번 연속된 두 개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방식, 어떻게 되었건 선택 정렬과 동일하게 O(n^2), 공간 복잡도 O(n)이다.
합병 정렬: 분할 정복을 통해 문제를 쪼개서 합치는 것을 반복하는 알고리즘이다. 공간 복잡도는 2N, 시간 복잡도는 O(NlogN)이다.
퀵 정렬: 피봇 포인트를 통한 값을 기준으로 작은 값과 높은 값으로 분리해 정렬을 진행한다. 이 때, 이미 정렬된 경우엔 시간 복잡도가 O(N^2)이지만 일반적으로는 O(NlogN)이며, 합병 정렬에 비해 일반적으로 더 빠르다.
카운트 정렬: 정렬하고자 하는 데이터 값의 범위가 크지 않은 경우에 유용하다. 알고리즘에서 각 원소가 등장하는 횟수를 계산한 후 각 원소의 등장 횟수를 누적합으로 계산해 사용함, 숫자에만 사용 가능
Radix 정렬: 특정한 자리수를 기준으로 정렬해서, 카운트 정렬과 유사하게 사용한다.
※ 카운트 정렬이나 Radix 정렬에서 어떻게 같은 값들의 순서를 보장할까요?
같은 값들이 있는 경우, 해당 값의 순서를 보장해주어야 합니다. 그 방법은 뒤에서부터 읽어가며 카운트된 값을 계산하면 됩니다. 그러면 초기 주어진 동일 원소의 순서와 정렬 후 동일 원소의 순서가 보장이 됩니다.
2. BFS와 DFS에 관해서 설명해주세요.
BFS는 너비 우선탐색이라 불리며 시작점에서부터 위치상으로 가까운 곳부터 순차적으로 탐색하는 알고리즘입니다. 이를 구현하기 위해 큐와 함께 사용이 되며, 위치상으로 가까운 곳부터 탐색한다는 특징이 있어 최단 거리를 구할 때 사용할 수 있고, 메모리를 사용해서 거리를 적어놓는다면 최단 경로 또한 구할 수 있습니다.
DFS는 깊이 우선탐색이라 불리며 현재 탐색하는 정점으로부터 가까운 점들부터 탐색을 하는 알고리즘입니다. 스택 혹은 재귀함수를 통해 구현을 합니다.
보통 탐색하는 상황에서 많이 사용되는데 DFS보다 BFS를 선호합니다.