인터뷰 질문 및 답변 정리
알고리즘
Sorting Algorithm에서 stable 하다는 것은 무엇을 의미하나요?
정렬 알고리즘이 stable하다는 것은 정렬 기준에 없는 다른 값의 순서가 달라질 수 있는 것을 말합니다.
안정 정렬에는 bubble sort, insertion sort, merge sort가 있습니다.
stable unstable에 대하여
정렬이 필요한 이유
정렬이 되어 있다면 자료 탐색에 있어서 편리함을 가질 수 있기 때문입니다. 정렬이 되어 있다는 가정 아래에 찾고자 하는 값을 logN의 시간 복잡도 만으로 찾을 수가 있습니다.
Sorting Algorithm이 가짓수가 많은데 그 이유가 무엇일 것 같나요?
2가지. 과거부터 계속해서 더 나은 정렬알고리즘을 찾기위해 연구하다보니 기존의 정렬 알고리즘을 대체할 방안이 계속 나왔다는 것 하나가 있습니다.
또 두번째로는 정렬 알고리즘 하나가 무조건 항상 우수한 것이 아니라, 주어진 상황에 따라서 trade-off가 있기 때문입니다.
- 꼬리 질문 : 구체적인 trade-off의 예시를 들어주세요.
Quick sort에 대해서 설명해 줄 수 있나요?
quick sort란 입력 값 중에서 pivot이라는 기준을 하나 설정하여 그 값보다 작으면 왼쪽, 더크면 오른쪽으로 정렬하는 것을 재귀적으로 반복하는 방법입니다. quick sort의 시간 복잡도는 최선의 경우에는
O(n), 평균의 경우에는 O(nlogn), 최악의 경우에는 O(n^2)을 가집니다. 배열이 거의 정렬되어 있을 경우에
우수한 성능을 보이는 정렬 알고리즘입니다.
시간 복잡도와 공간 복잡도를 설명해보세요
시간 복잡도란 프로그램이 실행되는데 걸리는 시간을 말합니다. 일반적으로 빅오 기법을 사용하여 최악의 수행시간 복잡도를 시간복잡도라고 말합니다.
공간 복잡도는 프로그램이 실행되는데 필요한 메모리의 크기를 말합니다.
시간 복잡도는 실제 수행 시간과 어떤 관계가 있을까요?
실제 수행 시간은 실행되는 컴퓨터의 환경에 따라 달라지며 입력되는 데이터에 따라서도 상이합니다.
그래서 보통 입력값이 커질수록 반복문이 수행시간을 지배하기 때문에, 알고리즘의 수행시간을 반복문이 수행되는 횟수로 측정합니다.
시간복잡도가 작은 알고리즘은 무조건 빠른가요?
시간복잡도가 작다고 해서 무조건 그 알고리즘이 빠르지는 않습니다. 왜냐하면 시간복잡도의 경우에는
보통 최악의 수행시간을 나타내기 때문입니다. 구체적인 예로 퀵소트의 시간 복잡도는 O(n^2)이지만,
거의 정렬된 데이터의 경우에는 O(n)에 가까운 시간복잡도를 보여 다른 정렬알고리즘 보다 나은 빠른 성능을 보입니다.
최악의 복잡도는 나쁘지만 실제로는 자주 사용되는 알고리즘을 말해보세요
퀵소트의 시간 복잡도는 O(n^2)이지만, 거의 정렬된 데이터의 경우에는 O(n)에 가까운 시간복잡도를 보여 다른 정렬알고리즘 보다 나은 빠른 성능을 보입니다. 그래서 python, java와 같은 언어의 내장정렬 함수에서 사용됩니다.
해쉬테이블의 경우 충돌이 발생했을 경우에 O(n)의 시간복잡도를 보이지만, 평균적으로 충돌없이 잘 구현된 경우 O(1)만에 탐색이 가능하여 자주 사용됩니다.
팩토리얼(factorial)을 구현해 보세요(손코딩)
반복문과 재귀 두가지 방법으로 간단하게 구현가능.
피보나치 수열 구현 방식 세 가지를 말해보시고, 시간복잡도와 공간복잡도를 설명해 주세요
피보나치 수열의 구현 방식 3가지에는 재귀를 통한 구현, 반복문을 통한 구현, 메모라이제이션/동적 계획법을 통한 구현 세가지가 있습니다. 재귀문 통해 구현할 경우 시간복잡도는 O(2^n), 반복문을 통해 구할 경우 O(n), 동적계획법을 통할 경우 O(n) 의 시간 복잡도를 가집니다. 동적계획법을 통할 경우에는 한번 값을 구하고 나면 다음에 다시 구할 때는 O(1)만에 구할수 있다는 점에서 반복문을 통한 방법과 차이가 있습니다.
피보나치 알고리즘을 해결하는 5가지 방법
BFS/DFS 차이는 무엇인가요?
BFS와 DFS는 그래프를 탐색하는 알고리즘 입니다.
우선, BFS는 너비 우선 탐색으로 한 정점에서 시작하여 그 정점과 인접한 정점 먼저 방문하는 방법입니다. 그래서 BFS의 특성을 이용하여 가중치가 1인 최단 경로 탐색에 주로 활용되며 queue 자료구조를 이용하여 구현됩니다. 시간 복잡도는 인접리스트로 구현했을 때 O(V+E)입니다.
DFS는 깊이 우선 탐색으로 한 정점에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법입니다. 모든 경우의 수를 탐색해야하는 문제에서 주로 사용됩니다. 재귀적으로 구현하거나 stack을 이용하여 구현할 수 있습니다. 시간 복잡도는 인접리스트로 구현했을때 O(V+E)입니다.
BFS vs DFS
다익스트라 알고리즘에 대해서 설명해 주세요.
다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 정점간의 최단 경로를 찾는 알고리즘입니다.
우선순위 큐를 사용한 다익스트라 알고리즘의 경우에는 O((V+E)logV)의 시간복잡도를 가집니다.
처음 시작점에서 시작하여 계속해서 거리를 짧은 노드를 고르면서 최종점까지의 최단경로를 구합니다.
정렬의 종류에는 어떤 것들이 있나요?
정렬의 종류에는 퀵소트, 버블소트, 머지소트, 계수정렬, 기수정렬, 선택정렬, 삽입정렬 등 여러가지 정렬이 있습니다. 정렬을 나누는 여러가지 기준에는 안정정렬인가? 제자리 정렬인가? 등이 있습니다. 만약 정렬하고자 하는 데이터가 너무 큰경우에는 외부정렬을 이용하여 정렬합니다.
- 꼬리질문: 이런 경우에는 어떤 정렬을 이용하는 것이 좋을까요?
- 삽입 정렬이 일어나는 과정을 설명해 보세요.
- 퀵 정렬이 일어나는 과정을 설명해 보세요.
- 54321 배열이 있을 때, 어떤 정렬을 사용하면 좋을까요?
- 랜덤으로 배치된 배열이 있을때, 어떤 정렬을 사용하면 좋을까요?
- 자릿수가 모두 같은 수가 담긴 배열이 있을 때, 어떤 정렬을 사용하면 좋을까요?
크루스칼 알고리즘과 프림 알고리즘을 비교해서 설명해 주세요.
둘 모두 일단 최소신장트리를 구하는 알고리즘들 입니다.
크루스칼 알고리즘은 간선선택 기반의 알고리즘이고 프림 알고리즘은 정점선택 기반의 알고리즘 입니다.
크루스칼 알고리즘의 경우에는 간선들을 가중치 기반으로 오름차순 정렬하고, 가중치가 가장 작은 간선을 사이클을 이루지 않는다면
선택하는 것을 반복하며 사용합니다.
프림 알고리즘의 경우에는 임의의 한 정점을 선택한 다음, 그 정점의 간선들 중 가장 가중치가 작은 간선을 선택합니다.
그리고 해당 간선의 다른 정점에 대해서 과정을 사이클을 이루지 않을때 까지 선택하는 것을 반복합니다.
크루스칼 알고리즘은 O(Elog2E)의 시간 복잡도, 프림알고리즘은 O(N^2)의 시간복잡도를 가집니다.
간선이 적은 희소그래프의 경우 크루스칼, 간선이 많은 그래프의 경우 프림을 사용하는 것이 일반적입니다.
인접행렬과 인접리스트에 대해 설명하시오
인접행렬과 인접리스트 모두, 그래프의 정점과 간선 정보를 저장하는 자료구조입니다.
인접행렬은 행렬을 이용해서 한정점과 다른정점이 연결되어 있는지 여부를 나타냅니다.
인접리스트의 경우, 한정점이 다른 어떤 정점과 연결되어 있는지를 리스트 형태로 저장합니다.
-꼬리질문
- 인접리스트와 인접행렬 각각의 장단점을 무엇인가요?
- 사용하는 예시를 하나 들어보세요
인접행렬과 인접리스트
자주 사용하는 주언어는 무엇인가요? 그 언어에서 기본정렬은 어떻게 구현되어 있나요?
제가 자주사용하는 주언어는 JAVA언어 입니다. JAVA언어의 내장 sort 메소드를 보았을때, 퀵정렬과 Tim정렬이 혼합된 형태로 구현된 것을 확인했습니다.
여기서 퀵정렬이란 pivot을 기준으로 더작은 쪽과 더 큰쪽을 나누는 것을 반복하는 정렬방법입니다.
팀정렬이란 삽입정렬과 합병정렬을 합친 방법으로 각각의 장점을 취한 정렬 방법입니다. 구체적으로 작은 단위일 경우 삽입정렬이 뛰어난 성능을 보여주는 것을 이용하여 작은 단위로 나눈뒤 각각에 대해 삽입정렬을 하고, 그것을 다시 합병정렬을 하는 방식입니다.
Tim 소트 분석기
자바 내부정렬
Dynamic Programming가 무엇이고 왜 어떻게 사용하는가?
동적계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말합니다.
동적 계획 알고리즘은 최단 경로 문제(다익스트라), 행렬의 제곱 문제 등의 최적화에 사용되는데요.
이전에 계산한 작은 문제에 대한 값을 공간을 할당하여 기억에 둔다는 점에서 분할정복과 차이가 있습니다.
이것은 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아내기 때문입니다.
문제가 가능한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우, 동적 계획법은 최적의 해법이라고 말할 수 있다.
안정 정렬 vs 불안정 정렬을 차이점을 설명해보세요.
안정 정렬은 정렬의 기준이 되지 않는 다른 값의 순서가 기준값이 같은 경우에 본래의 데이터의 순서로 유지가 됩니다.
불안정 정렬은 그렇지 않습니다.
분할정복에 대해 설명하고 그 예시를 드시오
분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘입니다.
구체적으로 합병정렬이나 여러 정렬 알고리즘에서 사용됩니다.
이전에 계산한 문제에 대한 답을 따로 저장하지 않는 다은 점에서 동적계획법과 차이가 있습니다.
동적계획법과 분할정복 비교
출처
