20.10.09 면접 스터디

1. 정렬 알고리즘

정렬 알고리즘의 종류에는 무엇이 있나요?

안정정렬과 불안정 정렬의 차이점은 무엇인가요?

퀵 정렬과 합병정렬의 차이점은 무엇인가요?

데이터가 아주 많이 존재할 때 어떤 정렬 알고리즘을 선택하는 것이 좋은가요?

데이터가 100개 이하일 때에는 어떤 정렬 알고리즘을 선택하는 것이 좋은가요?

C++내의 STL의 sort함수는 어떤 방식으로 구현되어 있나요?

 

거품정렬

n개의 원소를 가진 배열을 정렬할 때, 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다.

 

시간복잡도는 n^2, 공간복잡도는 O(1)

평균, 최선, 최악의 시간복잡도가 동일하다. 장점으로는 구현이 간단하고 소스코드가 직관적이다. 제자리 정렬이므로 다른 메모리 공간을 차지하지 않으며 안정 정렬이다. 단점으로는 속도가 느리다는 점을 들 수 있다.

 

선택정렬

해당 순서에 해당하는 위치에 넣을 원소를 선택하는 알고리즘이다.

오름차순 정렬 시 처음에 가장 작은 값을 찾아 맨 앞으로 가져온다. 그리고 이후로도 같은 방식으로 정렬할 수 있다.

최악의 경우는 역방향으로 정렬되어 있는 경우이다.

 

시간복잡도는 n^2, 공간복잡도는 O(1)

평균, 최선, 최악의 시간복잡도가 동일하다. 장점으로는 구현이 간단하고 소스코드가 직관적이다. 제자리 정렬이므로 다른 메모리 공간을 차지하지 않으며 안정 정렬이다. 단점으로는 속도가 느리다는 점을 들 수 있다. 또한 불안정 정렬이다.

 

퀵 정렬

배열 가운데에서 pivot을 골라 작은 수는 왼쪽, 큰 수는 오른쪽으로 나누고 왼쪽과 오른쪽으로 나눠진 배열에서 동일하게 pivot을 골라가며 재귀적으로 진행한다.

Divide-conquer 방식으로 구현한다.

 

평균과 최선은 nlogn이지만 최악의 경우 n^2의 시간복잡도를 가진다. Pivot의 영향을 크게 받는 편이다. 한 번 결정된 pivot이 이후의 연산에서 제외되는 특성때문에 시간 복잡도가 빠르다. 

단점은 불안정 정렬이며, 정렬되어 있는 경우에 오히려 불균형 분할때문에 수행 시간이 오래 걸리게 된다.

 

합병정렬

요소의 영역을 쪼개고 다시 합병시켜 나가면서 정렬해나간다. 퀵소트와 마찬가지로 분할 정복 방식을 통해 구현한다. 퀵 소트와 달리 pivot을 설정하는 과정 없이 무조건 절반으로 나누기 때문에 시간 복잡도가 최선, 최악, 평균 모두 동일하다. 안정정렬이다.

단점으로는 임시 배열을 사용하여 정렬할 요소를 나누고 넣는 과정을 반복하여 추가적인 메모리가 필요하다.

 

힙정렬

최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법이다. 내림차순 정렬을 할 때엔 최대 힙을, 오름차순 정렬을 할 때는 최소 힙을 구성하면 된다.

시간복잡도는 최선 최선 최악 모두 nlogn이다.

 

+ 힙은 완전 이진 트리(이진 트리이면서 마지막 레벨을 제외한 모든 레벨의 노드가 채워져 있어야 한다. 마지막 레벨의 노드들은 가능한 왼쪽부터 채워져있어야 한다.)이면서 heap property를 만족해야 한다.

+ C++ 내의 STL 정렬 알고리즘은 sort(퀵 정렬), stable_sort(합병 정렬), partial_sort(힙 정렬)로 나누어져 있다.

 

2. 그래프

그래프의 개념은 무엇인가요?

그래프와 트리의 차이점은 무엇인가요?

MST를 구하는 알고리즘은 무엇이 있나요? 각각의 차이점은?

최단 경로를 구하는 방식에는 무엇이 있나요?

다익스트라 알고리즘과 벨만-포드 알고리즘의 차이점은?

 

정점과 간선의 집합을 그래프라고 한다. 트리 또한 그래프이며, 그 중 사이클이 허용되지 않는 그래프를 말한다.

정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 무방향성 그래프, 있는 그래프를 방향성 그래프라고 한다.

각 정점에 연결된 간선의 개수를 degree라 한다. 방향성 그래프에서는 방향이 존재하기 때문에 degree가 두 개로 나뉘게 된다.

 

그래프를 구현하는 방법에는 인접 행렬과, 인접 리스트 방식이 있다.

인접 행렬은 정방 행렬이며 dense graph(그래프에 간선이 많이 존재하는 그래프)를 표현할 때 적절하다. 인접 리스트는 sparse graph(그래프 내에 적은 숫자의 간선만을 가지는 그래프)를 표현하는 데 적절하다.

 

그래프 탐색 방식에는 깊이 우선 탐색과 너비 우선 탐색이 있다.

 

최소 스패닝 트리를 구할 때에는 크루스칼 알고리즘과, 프림 알고리즘을 사용한다. 프림 알고리즘은 정점을 선택하고 해당 정점에 연결된 가장 적은 비용의 정점을 선택한다면 크루스칼은 모든 비용을 순차적으로 나열하여 가장 적은 비용의 간선을 선택하는 방식이다.

 

최단 거리를 구할 때에는 보통 4가지 방법이 존재한다.

단일 출발 최단 경로, 단일 도착 최단 경로, 단일 쌍 최단 경로, 전체 쌍 최단 경로.

전체는 보통 플로이드-와셜 알고리즘을 사용한다.

단일 출발 최단 경로를 구할 때에는 다익스트라와 벨만-포드 알고리즘을 주로 사용한다.

다익스트라와 벨만-포드 알고리즘의 큰 차이점은 벨만-포드 알고리즘은 가중치가 음수인 경우에도 사용이 가능하다는 점이다.

 

3. 해시 충돌

해시에 대해 설명해주세요.

해시 충돌이 생기는 이유가 무엇인가요?

해시 충돌이란 무엇인가요?

해시 충돌의 해결 방법에는 무엇이 있나요?

저장하려는 정보와 해시 테이블의 개수가 비슷할 때, 개방 주소법으로 해결하게 되면 발생할 수 있는 문제는 무엇인가요?

 

해시는 일반적으로 key와 value를 갖는 해시테이블과 해시 함수로 구성된다. 해시함수는 해시테이블의 키 값으로 레코드가 저장되는 주소를 만들어내는 함수이다. 순차검색에 비해 검색 속도가 매우 빨라진다.

그러나 다른 내용의 데이터가 같은 키를 갖는다면 문제가 발생하게 되고 이것을 해시 충돌이라고 한다.

 

해시 충돌은 해시테이블의 성능을 떨어뜨리게 된다. 따라서 이를 막기 위해 해시 함수를 잘 정의하는 것이 중요하다. 하지만 입력값은 무한하지만 출력값은 유한하므로 충돌은 반드시 발생한다.

 

충돌 해결 방식에는 두 가지가 있다.

 

1. 체이닝 : 해시 충돌이 발생하면 연결리스트로 데이터를 연결하는 방식이다. 장점은 복잡한 계산식을 사용할 필요가 없다는 것이지만 메모리 공간이 추가적으로 할당되어 성능저하가 발생할 수 있다.

2. 개방 주소법 : 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식이다. 대표적으로 선형 탐색, 제곱 탐색, 이중 해시 방식이 있다. 체이닝처럼 포인터가 필요없고, 추가 저장공간이 필요하지 않다. 삽입 삭제 시 오버헤드가 적지만 저장할 데이터가 적을 때 더 유리하다. 저장하려는 정보와 해시 테이블의 개수가 비슷하게 되면 해시 충돌이 더 자주 일어날 수 있게 되고, 개방 주소법으로 해결할 때 삭제된 공간에 다시 데이터를 저장하는 문제가 발생할 수 있다. 그렇게 되면 순차적으로 데이터가 저장되지 않게 되고 문제가 생기게 되는데 이를 막기 위해 삭제된 공간이라는 것을 표시해주어야 한다.