알고리즘 면접 대비 질문 리스트업

 

1) 정렬

 

 

정렬에는 다양한 방법이 있는데, 알고 있는 방법에는 무엇이 있나요?

키 값을 비교해 자료를 삽입해 정렬하는 선택 정렬, 버블 정렬, 퀵 정렬, 병합 정렬 등의 방법이 있고, 계수 정렬과 같이 값을 비교하지 않고 정렬하는 방법도 있습니다.

 

 

왜 정렬 알고리즘이 많을까?

정렬 알고리즘 하나가 무조건 우수한게 아니라 주어진 상황에 따라 trade-off가 있기 때문입니다.

 

구체적인 Trade-off 예시

• 퀵소트는 평균의 경우 O(N logN)을 갖지만 정렬된 경우 O(N^2)의 시간 복잡도를 갖게 됩니다.
• 삽입 정렬은 평균 O(N^2)을 갖지만 정렬된 경우 O(N)의 시간 복잡도를 갖게 됩니다.

 

이미 정렬된 데이터에 대해 가장 좋은 성능을 보이는 정렬 알고리즘은?

삽입 정렬로, 자기 앞에 있는 원소에 대해서만 비교를 수행하게 되므로 O(N)이 걸립니다.

 

버블 정렬 같은 알고리즘은 왜 사용할까요?

버블 정렬은 알고리즘 구현이 쉽고, 다른 메모리 공간을 필요로 하지 않으면서 stable sort 라는 장점을 가지고 있습니다. 데이터의 크기가 크지 않다면 성능 저하가 크지 않아 사용할 수 있습니다.

 

안정 정렬인 정렬에는 무엇이 있나요?

삽입 정렬, 버블 정렬, 병합 정렬, 계수 정렬이 안정 정렬에 속합니다.

---

왜 삽입 정렬이 평균 $O(N^2)$ 시간복잡도를 갖는 알고리즘 중 가장 빠를까요?

삽입 정렬은 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다. 따라서 삽입할 위치까지만 탐색하면 되기 때문에 선택 정렬과 버블 정렬에 비해 빠릅니다. 

또한, 삽입 정렬은 데이터가 모두 정렬된 경우 한 번씩만 비교하면 되므로 $O(N)$ 시간복잡도를 갖습니다.

 

Quick Sort의 특징과 시간복잡도에 대해 설명해주세요.

퀵 소트는 기준 데이터 pivot을 설정하고 그 기준보다 큰 데이터와 작은 데이터 위치를 바꿔 정렬하는 알고리즘입니다. 추가적인 메모리를 필요로 하지 않습니다. 시간복잡도의 경우 피봇이 정확히 데이터를 절반씩 나눈다면 평균적으로 $O(NlogN)$에 정렬이 가능하지만, 피봇이 데이터를 1개씩만 나눈다면 최악의 경우 시간복잡도는 $O(N^2)$이 됩니다.

 

Quick sort 성능 개선 기법으로는 어떤게 있나요?

2가지 방법을 알고 있습니다.

하나는 피벗을 맨 처음 값으로 정하면 최악의 경우 $O(N^2)$의 시간 복잡도를 가지므로 랜덤하게 피벗을 설정할 수 있습니다.

또는 맨 앞과 중간, 맨 뒤 값을 우선적으로 정렬하고 중앙값을 피벗으로 삼는 방법입니다. 

하지만, 이 방법으로 개선한다해도 Quick Sort의 최악의 시간복잡도가 O(nlogn) 이 되지는 않습니다.

 

퀵 정렬을 여러 언어의 정렬 내부 구현으로 사용하는 이유는?

피벗을 적절하게 선택하도록 구현해 성능 개선을 할 수 있고, 퀵 정렬 수행할 때 한 번 위치가 정해진 원소는 정렬을 위해 확인할 대상에서 제외된다는 특성이 있기 때문에 평균적으로 병합 정렬보다 더 빠른 정렬 알고리즘이기 때문입니다.

 

Merge Sort의 특징과 시간복잡도에 대해 설명해주세요.

머지 소트는 재귀적으로 배열을 더 이상 쪼갤 수 없을 때 까지 나눈 뒤, 배열을 합쳐 정렬된 하나의 배열로 만드는 정렬 알고리즘입니다. 추가 메모리가 필요하지만 정렬했을 때 중복된 값의 순서가 변하지 않습니다. 시간복잡도의 경우 항상 O(NlogN) 입니다.

---

본인이 사용하는 언어의 정렬 알고리즘이 무엇인지 알고 있나요?

네, Python의 경우 병합 정렬과 삽입 정렬의 장점을 섞은 Timsort 를 사용하고 있습니다.

 

 

Python에서는 퀵 정렬이 아니라 병합 정렬을 기반한 정렬 알고리즘을 사용하는 이유가 무엇일까요?

퀵 정렬은 이미 정렬된 데이터의 경우 시간 복잡도가 $O(N^2)$ 을 갖는 반면 병합 정렬은 모든 경우 $O(NlogN)$을 보장합니다.

또한 파이썬은 기본적으로 리스트 자료구조를 사용합니다. 이때 병합 정렬은 순차적인 비교'로 정렬을 진행하므로 LinkedList 정렬에 효율적입니다. 반면 퀵정렬은 임의 접근이기 때문에 LinkedList 접근 오버헤드 발생으로 비효율적입니다.

 

100GB의 데이터를 1GB의 램으로 정렬하려면 어떻게 해야할까?

메모리 만큼 데이터를 읽어오고, 퀵 소트를 이용해 데이터를 정렬한 뒤, 정렬된 데이터를 저장하는 것을 반복해 정렬할 수 있습니다.

• 2개의 블록을 선택해 데이터를 읽은 후 두 블록의 값을 비교하며 정렬을 진행해 정렬된 2G의 블록을 만듭니다. 그 다음에는 2G 블록 2개를 정렬해 4G 블록을, 그 다음에는 8G 블록을, 그렇게 합쳐가면서 100GB의 정렬된 블록을 만들 수 있습니다.
• 입력 크기 N 메모리 크기 m 이라고 한다면 정렬 자체의 시간 복잡도만 보자면 O(log N/M) 인데, 메모리를 참조하는 시간이 더 많이 걸릴 것이라고 생각됩니다.

 

 

2) 그래프 탐색

 

 

 

그래프 자료구조란?

노드와 노드의 관계를 나타내는 엣지로 이루어진 자료구조로 정방 행렬과 링크드 리스트로 구현할 수 있습니다.

 

그래프 구현에서 인접 행렬과 인접 리스트의 장단점

인접 행렬은 구현이 간단하고 조회에 O(1)의 시간 복잡도를 갖지만, sparse 한 경우 공간 낭비가 많습니다.

인접 리스트는 공간의 낭비가 없지만 연결 정보를 탐색할 때 O(N)의 시간 복잡도를 갖습니다.

 

그래프 탐색이란 무엇인가요?

그래프 탐색이란 하나의 정점으로부터 차례로 모든 정점들을 한 번씩 방문하는 것입니다.

 

그래프 탐색 방법은?

너비 우선 탐색 BFS, 깊이 우선 탐색 DFS 방법을 알고 있습니다. BFS는 자신과 연결된 주변 노드부터 탐색하는 방법이고, DFS는 자신과 연결된 노드를 하나 선택하고 그 노드와 연결된 모든 노드를 깊게 탐색하는 방법입니다.

 

BFS와 DFS의 장단점은?

• DFS는 스택에 백트래킹을 해야하는 노드들만 저장해주면 되기 때문에 BFS에 비해 저장 공간의 필요성이 적고, 찾아야 하는 노드가 깊이 있을 때 빨리 탐색이 가능합니다. 하지만 답이 아닌 깊은 경로에 빠질 수 있고, 찾은 해가 최단 경로라는 보장이 없습니다.
• BFS는 답이 되는 경로가 여러 개인 경우에도 항상 최적해를 찾음을 보장하고, 찾아야 하는 노드가 얕을 때 유리합니다. 하지만 큐에 다음에 탐색할 노드를 계속 저장하기 때문에 더 큰 저장 공간이 필요합니다.

 

그래프의 최단 경로 구하는 방법은?

다익스트라와 플로이드 워셜을 알고 있습니다.

다익스트라는 음의 가중치가 없을 때 특정 노드에서 다른 노드로 가는 각각의 최단 경로 계산하는 알고리즘입니다. 간선 개수가 E, 노드 개수가 V일 때 $O(E\ logV)$ 의 시간 복잡도를 갖습니다.

플로이드 워셜은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용하는 알고리즘입니다. DP 유형 중 하나로 그래프에서 a에서 b로 가는 최단 경로를 구할 때, 모든 다른 정점 k에 대해 최단 경로를 찾습니다. 코드가 단순하고 양/음수 값의 모든 가중치에 대해 탐색 가능하지만 3중 포문으로 느립니다.

 

BFS와 DFS와 다익스트라 구현 방법은?

• BFS는 큐를 이용해 구현합니다. 큐에 시작 노드를 넣고, 그래프에서 인접한 노드를 모두 큐에 넣습니다. 그리고 하나씩 꺼내서 반복 합니다.
• DFS는 스택이나 재귀함수를 이용해 구현합니다. 스택에 시작 노드를 넣고, 인접한 노드를 모두 스택에 넣습니다. 그리고 하나를 꺼내서 반복 합니다.
• 다익스트라는 힙을 이용해 구현할 수 있습니다. 최단 거리 테이블을 만들고, 힙에 시작 노드를 넣습니다. 힙에서 최단 거리의 노드를 꺼내고 해당 노드를 거쳐 다른 노드로 이동하는 거리가 더 짧은 경우 최단 거리를 갱신하고, 이동 가능한 노드를 힙에 다시 넣습니다. 이를 힙이 빌 때까지 반복하면서 최단 거리 테이블을 갱신합니다.

---

최소 스패닝 트리란?

스패닝 트리는 그래프에서 일부 간선을 선택해 모든 정점이 포함되는 트리를 말합니다. 최소 스패닝 트리는 스패닝 트리중 가중치 합이 최소인 트리를 의미합니다.

 

최소 스패닝 트리 구현방법

크루스칼이나 프림 알고리즘을 사용해 구현할 수 있습니다. Sparse 하다면 크루스칼, Dense 하다면 프림 알고리즘이 적합합니다.

 

크루스칼 알고리즘

그리디 알고리즘의 하나로 모든 간선에 대해 정렬을 수행한 뒤, 가장 거리가 짧은 간선부터 집합에 포함시킵니다. 이때, 사이클을 발생시킬 수 있는 간선의 경우 집합에 포함시키지 않는다. 시간 복잡도는 간선 개수가 E 일때, $O(E logE)$ 를 갖습니다.

 

프림 알고리즘

이전 단계의 스패닝 트리를 단계적으로 확장하는 방법입니다. 시작 정점에서부터, 최소 간선으로 연결된 정점을 선택하고, 다시 그 정점에서 최소 간선으로 연결된 정점을 선택하며 트리를 확장하는 것을 모든 정점이 포함될 때까지 반복합니다. 간선 개수가 E, 노드 개수가 V일 때 $O(E+VlogV)$ 시간 복잡도를 갖습니다.

 

 

3) 기타

시간 복잡도와 공간 복잡도란?

시간 복잡도는 알고리즘에 사용되는 연산 횟수의 총량이고, 공간 복잡도는 메모리 공간의 총량입니다. 즉, 시간 복잡도는 속도에 대한 분석이고 공간 복젭도는 메모리 사용량에 대한 분석 결과입니다.

 

Big-O 란 무엇인가요?

빅오 표기법은 알고리즘의 효율성을 표기해주기 위해 사용하며, 함수의 결과값을 시간복잡도에서 가장 큰 지수승만 남겨서 나타내는 방법입니다.

---

이진 탐색이란?

이진탐색이란, 매 탐색마다 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘입니다. 단 이진탐색을 수행하기 위해서는 리스트(배열)가 정렬되어 있어야 합니다. 한번 탐색을 수행할 때 마다, 탐색의 범위가 반으로 줄어들기 때문에, 시간복잡도는 O(logN) 입니다.

 

재귀와 반복의 차이

재귀함수는 함수는 자기 자신을 계속 호출하는 함수라 스택 메모리를 사용합니다. 그래서 무한 재귀가 발생하면 스택 오버플로우가 발생하게 됩니다. 반복문은 명령을 반복적으로 실행하고, 스택 메모리를 사용하지 않아 무한 실행될 수 있습니다.

 

언제 재귀를 사용하면 좋은가?

피보나치 수열처럼 재귀적인 표현이 자연스러운 경우, 반복문을 사용할 때보다 변수 사용을 줄이고 가독성을 높일 수 있습니다.

 

피보나치 수열 구현 방식과 각 방식의 시간복잡도는?

• 반복문 : O(N)
• 재귀 :$ O(N^2)$
• DP(메모라이제이션) : O(N)

 

최대 공약수와 최소 공배수 알고리즘을 설명해주세요

최대 공약수는 유클리드 호제법을 사용해 구현할 수 있고, 최소 공배수는 최대 공약수를 이용해 구현할 수 있습니다. 2개 자연수 a와 b가 있을 때, a와 b를 나눈 나머지를 r이라고 한다면, a와 b의 최대 공약수와 b와 r의 최대 공약수는 같습니다. 이 성질에 따라 b가 0이 되기 전까지 a와 b를 b와 r로 반복하면서 최대 공약수를 구할 수 있습니다.

최소 공배수는 a와 b의 곱을 a와 b의 최대 공약수로 나눈 값입니다.

 

DP 와 분할정복의 공통점과 차이점은?

DP와 분할정복 모두 문제를 잘게 나누어서, 가장 작은 단위로 분할하여 문제를 해결하는 알고리즘입니다. 하지만 DP는 부분 문제를 중복되어 재활용 되므로 Memoization이 필요하지만 분할정복에서는 부분 문제는 서로 중복되지 않습니다.

 

백트래킹 알고리즘이란?

상태 공간을 트리로 나타낼 수 있을 때, 모든 경우의 수를 전부 고려하는 알고리즘입니다. 하지만 최종 결정에 영향 주지 않는 부분은 쳐내면서 경우의 수를 줄여나갑니다. 대표적으로 BFS, DFS 등이 있습니다.

 

그리드 알고리즘이란?

매 순간에서 가장 좋은 것을 선택하는 방법입니다. 따라서 현재의 선택이 이후의 선택에 영향을 주지 않고, 순간마다 하는 선택이 지역적으로도 최적이면서 최종적(전역적)으로도 최적이라는 보장이 있을 때만 사용할 수 있습니다. 크루스칼이 대표적인 그리디 알고리즘입니다.

 

허프만 코딩이란?

허프만 코딩이란 데이터 압축을 수행하는 알고리즘입니다. 문자의 빈도 수를 가지고 압축하는 과정입니다. 전체 문자를 우선순위 큐에 넣고 빈도수가 낮은 값을 합쳐 이진 탐색 트리를 만들고, 이걸 다시 우선순위 큐에 넣어 N번 반복합니다. 파일압축 in Unix,  JPEG, MP3 파일 압축을 위한 서브루틴 등에서 사용됩니다.