[면접 준비-CS기초] 1. 자료구조와 알고리즘(2)

IT 기업 신입사원 면접에서 많이 질문하는 면접 질문 목록입니다. 이번 포스팅은 자료구조와 알고리즘 관련 질문 중 대표적인 정렬 알고리즘에 대한 설명과 동적 프로그래밍의 정의가 설명되어 있습니다. 또한 최단거리 알고리즘도 설명해 놓았습니다.

 

자료구조와 알고리즘 면접 질문과 답변 정리

[면접 준비-CS기초] 1. 자료구조와 알고리즘(1)

정렬 알고리즘

아래는 정렬 알고리즘의 종류와 설명 및 시간 복잡도입니다. 기본적인 정렬 알고리즘은 대표 면접 기출문제이므로 꼭 알아두어야 합니다.

삽입 정렬 (insertion sort)

• 삽입 정렬은 두번째 위치부터 시작하여, 그 앞의 이미 정렬된 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 알고리즘입니다. 평균 시간복잡도는 O(n2)이며, 가장 빠른 경우 O(n)까지 빨라질 수 있습니다.

선택 정렬 (selection sort)

• 선택 정렬은 각 순서에 원소를 넣을 위치는 이미 정해져 있고, 해당 위치에 어떤 원소를 넣을지 선택하는 알고리즘입니다. 오름차순으로 정렬한다면 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 선택하여 넣고, 두 번째 순서에는 두 번째 위치에 남은 값 중 최솟값을 선택하여 넣는 과정을 마지막까지 반복합니다. 구현이 간단하지만 O(n2)의 시간복잡도를 갖는 비효율적인 정렬 방식입니다.

버블 정렬 (bubble sort)

• 버블 정렬은 인접한 두 원소를 비교하여 자리를 교환해가며 정렬하는 알고리즘입니다.
• 오름차순으로 정렬한다면 첫번째 순서에는 처음부터 마지막 원소까지 비교하여 결과적으로 마지막 위치에 가장 큰 값이 위치하게 되고, 두 번째 순서에는 마지막 원소를 제외하고 같은 과정을 반복하며 정렬하는 방식입니다. 구현이 간단하지만 O(n2)의 시간복잡도를 갖는 비효율적인 정렬 방식입니다.

퀵 정렬 (quick sort)

• 퀵 정렬은 pivot을 설정하여 원소들을 pivot보다 큰 값과 작은 값으로 분할하여 정렬하는 분할 정복 알고리즘입니다. 시간 복잡도는 O(nlogn)이지만, 계속해서 불균등하게 나누어지는 경우에는 O(n2)까지 나빠질 수 있습니다.

병합 정렬 (merge sort)

• 병합 정렬은 주어진 배열을 크기가 1인 배열로 분할한 뒤 이들을 병합하면서 정렬을 진행하는 분할 정복 알고리즘입니다. 시간 복잡도는 항상 O(nlogn)입니다.

셸 정렬 (shell sort)

• 셸 정렬은 삽입 정렬이 어느 정도 정렬된 배열에 대해서 매우 빠르다는 점에서 착안하여 삽입 정렬을 보완한 알고리즘입니다.
• 일정한 간격으로 떨어져 있는 원소들끼리 부분집합을 구성하여, 각 부분집합 내에서 삽입 정렬을 수행한 뒤 모든 부분집합을 다시 합치는 과정을 반복하며 정렬합니다. 시간 복잡도는 평균적으로 O(n1.5)이며, 최악의 경우에는 O(n2)입니다.

힙 정렬 (heap sort)

• 힙 정렬은 주어진 데이터를 힙으로 만들어 최댓값 또는 최솟값부터 하나씩 꺼내며 정렬하는 알고리즘입니다. 전체를 정렬할 때보다는 가장 크거나 작은 값 몇 개를 필요로 할 때 가장 유용합니다. 시간 복잡도는 O(nlogn)입니다.

트리 정렬 (tree sort)

• 트리 정렬은 이진 탐색 트리(BST)를 이용하여 데이터를 정렬하는 방식입니다. 원소들을 순서대로 이진 탐색 트리에 넣은 뒤, 중위 순회로 값을 모두 꺼내면 데이터가 오름차순으로 정렬됩니다. 시간 복잡도는 O(nlogn)입니다.

 

동적 프로그래밍 (DP: Dynamic Programming)

• 동적 프로그래밍이란 주어진 문제를 풀기 위해서 문제를 여러 개의 하위 문제로 나누어 푼 뒤 그것을 결합하여 해결하는 방식입니다. 동적 프로그래밍에서는 어떤 부분 문제가 다른 문제들을 해결하는 데 사용될 수 있기 때문에, 답을 한 번만 계산하고 그 결과를 재사용하는 memoization 기법으로 속도를 향상할 수 있습니다.
• 동적 프로그래밍을 적용하기 위해서는 중복 부분문제와 최적 부분 구조를 만족해야 합니다.
• 중복 부분문제는 문제가 순환적이라서 이전에 구한 작은 문제의 해가 더 큰 부분 문제의 해를 구할 때 여러 번 재사용되는 구조를 의미합니다.
• 최적 부분구조는 작은 부분 문제에서 구한 최적의 답이 합쳐져 큰 부분 문제의 최적의 답을 구할 수 있는 구조입니다.

분할 정복 vs 동적 프로그래밍

• 분할 정복 기법은 단순히 큰 문제를 작은 문제로 나누어 푸는 방법이고, 동적 프로그래밍은 작은 문제의 해가 중복해서 재사용된다는 점을 이용해서 푸는 방법입니다.

 

최단 경로

최단 경로는 네트워크의 양 끝을 연결하는 경로 중 가중치의 합이 최소인 경로를 의미합니다.

다익스트라 알고리즘

• 다익스트라 알고리즘은 하나의 시작점에서 다른 정점까지의 최단 경로를 구하는 알고리즘입니다.
• 최단거리를 여러개의 최단거리로 이루어져 있기 때문에 DP를 적용하여, 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보들을 재사용하게 됩니다.
• 매 과정에서 아직 방문하지 않은 정점들 중 최단 거리가 가장 짧은 정점을 방문하게 되는데, 이때 우선순위 큐를 활용하면 더욱 효율적으로 처리할 수 있습니다.

플로이드 와샬 알고리즘

플로이드 와샬 알고리즘은 특정 시작점 없이 모든 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘입니다. 두 정점 사이의 어떤 경유점이 존재할 때, 경유점을 거쳐가는 경우의 거리를 계산하여 기존까지 계산한 최단 거리와 비교하며 더 짧은 거리를 선택하는 방식입니다.