[ CS 기술면접 ] 알고리즘 예상질문 모음 !

알고리즘 질문 모음

# Adjacency Matrix, Adjacency List, UnionFind, LIS

✅ 인접 행렬과 인접 리스트의 장단점을 서로 비교하며 설명해 주세요. 어떤 경우에 무엇을 사용하는 것이 더 유리한지를 중점으로 설명해주시면 됩니다.

인접행렬의 경우 구현하기 쉬우며 빽빽한 그래프를 구현할때 좋습니다. 어떤 정점과 어떤 정점 사이 간선이 존재하는지 확인하기도 쉽습니다. 하짐나 어떤 점과 연결된 모든 노드를 방문하려면 O(V) 시간만큼이 걸립니다. 또한 공간복잡도가 O(V^2) 로 정점의 개수 V가 커질수록 메모리가 더 많이 필요합니다.

인접리스트의 경우 듬성듬성한 그래프로 구현할때 좋습니다. 어떤 정점에 연결된 다른 모든 정점들을 쉽게 방문할 수 있습니다. 하지만 어떤 정점과 어떤 정점이 연결되어 있는지 확인하려면 O(E) 시간을 사용해야한다는 단점이 있습니다.

 

✅ UnionFind 문서의 1976 문제는 플로이드와샬 알고리즘으로도 풀 수 있는 문제입니다. 유니온 파인드로 풀었을 때 이점이 있을까요?

유니온 파인드가 시간복잡도에서 유리합니다. 플로이드 와샬의 시간복잡도가 O(V^3) 인 반면 유니온파인드는 O(N) 입니다.

 

✅ 다음은 수열입니다.

10 70 30 20 50 100 30

다이나믹 프로그래밍으로 LIS의 길이를 구하려고 합니다. for 루프가 전부 끝나고 답을 반환하기 직전 DP 테이블의 숫자는 어떻게 되어 있을까요? DP 테이블은 [1, 1, 1, 1, 1, 1, 1]에서 시작됩니다.

[1,2,2,2,3,4,3]

 

# MST & Kruskal, Prim MST & Dijkstra, Bellman-Ford, Floyd-Warshall

✅ 최소 신장 트리에 대해 설명해주세요

Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리. MST는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말한다. 즉, 그래프에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.

 

✅ 최소 신장 트리의 알고리즘에 대해 설명해주세요

크루스칼 MST 알고리즘은 탐욕적인 방법을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것이다. MST가 '최소 비용의 간선으로 구성되며 사이클을 포함하지 않음' 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다. 즉, 간선 선택을 기반으로 하는 알고리즘이다.

프림 MST 알고리즘은 시작 정점에서부터 출발하여 MST 집합을 단계적으로 확장 해나가는 방법이다. 정점 선택을 기반으로 하는 알고리즘이다. 즉, 이전 단계에서 만들어진 신장 트리를 확장하는 방법이다.

 

✅ 다익스트라, 벨만포드, 플로이드 워셜의 개념에 대해서 간단히 설명해주세요

다익스트라는 가중치가 음이 아닌 그래프에서 한 정점에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘이다. 우선순위 큐 사용하고, 시간 복잡도는 O(ElogV)이다.

벨만포드는 가중치가 음수이고 음수 사이클이 없는 그래프에서 한 정점에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘이다. 시간 복잡도는 O(VE)이다.

플로이드워셜은 모든 정점에서 모든 정점으로 가는 최단경로를 구하는 알고리즘이다. 2차원 배열 사용하고, 시간 복잡도는 O(V^3)이다.

 

# Bitmask & Sorting alrorithm & Fibonacci

 
✅ 재귀와 반복의 차이와 DP 의 장점에 대해 설명해주세요
재귀는 함수 내에서 자기 자신을 반복하는 호출이고 반복은 조건이 참인 경우 계속하여 반복되는 명령어 블록입니다
dp는 작은 문제의 해를 여러 메모리에 저장해두기 때문에 동일한 계산의 반복을 줄일 수 있어 속도가 빠르다는 장점이 있습니다

✅ Quick sort 에서 최악의 복잡도 O(n^2) 이 발생하는 경우를 설명하고 이를 개선할 수 있는 방법에 대해서도 추가적으로 설명해주세요
예로 pivot을 가장 큰 값이나 작은 값으로 잡는 경우 분할 과정에서 비대칭적인 파티션이 반복되며 시간복잡도가 O(n^2) , 최악의 복잡도가 됩니다 이경우 수행시간이 일반적인 경우보다 훨씬 길어지게 되는데 이를 개선하기 위해서는 난수를 발생시켜 피벗을 랜덤하게 뽑는 경우를 생각해볼 수 있습니다

✅ 피보나치 수열을 구현할 수 있는 알고리즘 3가지를 언급하고 각 시간복잡도를 비교해주세요
피보나치 수열의 구현 방식에는 재귀, 반복, dp 가 있습니다
재귀문을 통해 구현할 경우 시간복잡도는 O(2^n) 이고 반복문과 dp 의 경우 O(n) 입니다
dp 를 사용하는 경우 한번 값을 구하고 나면 저장해두기 때문에 O(1) 만에 구할 수 있습니다