Algorithm 기술 면접 분석
기술 면접 대비 핵심 질문
카테고리: Algorithm
Q. 정렬 알고리즘 종류와 시간복잡도를 설명해주세요.
핵심 답변
대표적인 정렬 알고리즘으로는 버블, 선택, 삽입, 퀵, 병합, 힙 정렬 등이 있습니다. 버블, 선택, 삽입 정렬은 평균 및 최악의 경우 O(N^2)의 시간복잡도를 가지며 구현이 간단합니다. 반면 퀵, 병합, 힙 정렬은 평균 O(N log N)의 시간복잡도를 가져 대용량 데이터 처리에 적합합니다.
꼬리 질문
- Q. 퀵 정렬(Quick Sort)의 최악의 경우 시간복잡도는 어떻게 되며, 그 이유는 무엇인가요?
- A: 최악의 시간복잡도는 O(N^2)입니다. 이는 이미 정렬된 배열 등에서 피벗(Pivot)이 계속 최댓값이나 최솟값으로 잡혀 요소가 균등하게 분할되지 않고 한쪽으로 치우칠 때 발생합니다.
Q. 재귀와 반복의 차이점은 무엇인가요?
핵심 답변
재귀(Recursion)는 함수가 내부 로직에서 자기 자신을 다시 호출하는 방식이며, 반복(Iteration)은 for, while 루프를 사용하여 코드 블록을 실행하는 방식입니다. 재귀는 코드가 간결해지고 논리 도출이 쉬운 장점이 있지만 호출 스택이 커지며 Stack Overflow가 날 수 있습니다. 반복은 속도가 비교적 빠르고 메모리 부하가 낮습니다.
꼬리 질문
- Q. 재귀 호출에 의해 발생하는 스택 오버플로우 문제를 해결하는 꼬리 재귀(Tail Recursion) 최적화에 대해 설명해주세요.
- A: 재귀 호출을 한 리턴값이 연산으로 연결되지 않고 온전히 자기 자신의 결과만을 반환하게 구현하여, 컴파일러가 추가 콜 스택을 생성하지 않고 기존 스택을 재사용하도록 반복문 형태로 내부 최적화를 해주는 기법입니다.
Q. 퀵 정렬과 병합 정렬의 차이는 무엇인가요?
핵심 답변
퀵 정렬은 피벗을 기준으로 리스트를 분할하여 정렬하는 불안정 정렬(Unstable Sort)이며 메모리 낭비가 적은 제자리 정렬(In-place Sort)로 추가 배열이 불필요합니다. 반면 병합 정렬은 항상 리스트를 반으로 나눈 뒤 합치며 정렬하는 안정 정렬(Stable Sort)이고, 병합 과정에서 추가적인 메모리 공간(O(N))을 요구합니다.
꼬리 실문
- Q. 실무나 언어 내장 정렬에서는 보통 어떤 정렬을 사용하나요?
- A: Java 등에서는 프리미티브 타입에 대해서는 퀵 정렬을 베이스로 최적화한 Dual-Pivot Quick Sort를, 객체 타입에 대해서는 안정성이 보장되어야 하므로 병합 정렬과 삽입 정렬을 결합한 Tim Sort를 주로 사용합니다.
Q. 이진 탐색의 동작 원리와 시간복잡도를 설명해주세요.
핵심 답변
이진 탐색은 이미 정렬된 데이터 배열에서 중간값(mid)을 선택한 뒤, 탐색하려는 값과 크기를 비교해 탐색 범위를 절반씩 좁혀나가는 알고리즘입니다. 매 단계마다 탐색 범위가 반으로 줄어들기 때문에 시간복잡도는 O(log N)을 가집니다.
꼬리 질문
- Q. 이진 탐색 코드 구현 시 중간값(mid)을
(low + high) / 2로 계산할 때의 문제점은 무엇인가요?- A: low와 high 값이 커지면 서로를 더하는 과정에서 int 형의 최댓값을 초과하는 오버플로우(Overflow)가 발생할 수 있습니다. 이를 방지하기 위해
low + (high - low) / 2형태로 오버플로우를 예방하여 작성해야 합니다.
- A: low와 high 값이 커지면 서로를 더하는 과정에서 int 형의 최댓값을 초과하는 오버플로우(Overflow)가 발생할 수 있습니다. 이를 방지하기 위해
Q. DFS와 BFS의 차이와 사용 사례는 무엇인가요?
핵심 답변
DFS(깊이 우선 탐색)는 트리나 그래프에서 한 경로로 최대한 깊게 파고든 뒤, 더 이상 갈 곳이 없으면 백트래킹을 통해 돌아와 다른 경로를 탐색하는 방식으로 스택이나 재귀를 사용합니다. BFS(너비 우선 탐색)는 인접한 노드부터 층 단위로 먼저 탐색하는 방식으로 큐(Queue)를 사용합니다.
꼬리 질문
- Q. 어떨 때 DFS를 쓰고, 어떨 때 BFS를 쓰나요?
- A: DFS는 모든 노드를 방문해야 하거나 사이클 탐지, 백트래킹 퍼즐 류의 문제에 적합하며, BFS는 그래프의 간선 가중치가 같을 때 '최단 경로'를 찾거나 레벨 순 탐색이 필요할 때 적합합니다.
Q. 그래프에서 사이클을 탐지하는 방법은?
핵심 답변
방향 그래프에서는 주로 DFS를 사용하여 특정 노드가 현재 탐색 경로의 노드를 다시 방문하는지(백 에지 탐색 여부) 관찰하여 사이클을 탐지합니다. 무방향 그래프에서는 서로소 집합(Disjoint Set) 알고리즘인 Union-Find를 사용하여, 추가하려는 두 정점의 부모 노드가 이미 같다면 사이클이 발생하는 것으로 판단할 수 있습니다.
꼬리 질문
- Q. 위상 정렬(Topological Sort)을 통해 사이클을 판별할 수 있나요?
- A: 네. 진입 차수를 이용한 위상 정렬 큐 진입 알고리즘에서 정점 개수보다 적은 정점이 큐에서 꺼내졌는데 진행이 멈춘 경우(남은 정점들의 진입차수가 0이 되지 않을 때) 사이클이 있다고 판단합니다.
Q. 최소 신장 트리(MST)란 무엇인가요?
핵심 답변
최소 신장 트리(Minimum Spanning Tree, MST)란 가중치 무방향 그래프에서 그래프 내의 모든 정점을 포함하면서, 사이클이 없고, 간선들의 가중치 합이 최소가 되는 부분 그래프를 의미합니다. 노드가 N개일 때 항상 N-1개의 간선을 가지며 네트워크 회선 구축 등 최적의 비용을 구할 때 사용됩니다.
꼬리 질문
- Q. MST를 찾기 위한 대표적인 알고리즘 2가지의 차이는?
- A: 크루스칼(Kruskal)은 간선을 가중치 오름차순 정렬 후 사이클이 발생하지 않도록(Union-Find) 선택하는 방식(O(E log E))이고, 프림(Prim) 알고리즘은 임의의 정점에서 시작해 연결된 가장 적은 가중치의 간선 노드를 우선순위 큐로 확장해 나가는 방식(O(E log V))입니다.
Q. 다익스트라 알고리즘은 어떻게 동작하나요?
핵심 답변
다익스트라 알고리즘은 특정 시작 정점 하나에서부터 그래프 내 다른 모든 정점들까지의 최단 경로를 구하는 탐색 알고리즘입니다. 최단 거리가 가장 가까운 정점을 우선순위 큐(Min-Heap)로 뽑아 인접 정점의 이동 비용을 갱신하며 진행합니다. 평균적으로 O(E log V)의 시간복잡도를 가집니다.
꼬리 질문
- Q. 다익스트라가 음수 가중치를 가진 간선에서 동작하지 않는 이유는 무엇이며, 대안은 무엇인가요?
- A: 다익스트라는 원리 자체가 '이미 방문 처리(확정)된 노드의 최단거리는 변하지 않는다'는 그리디 가정을 기반으로 하기 때문입니다. 벨만-포드 알고리즘을 사용하면 모든 간선을 (V-1)번 반복적으로 갱신하므로 음수 가중치 및 음수 사이클 처리가 가능합니다.
Q. 동적 프로그래밍(DP)이란 무엇인가요?
핵심 답변
동적 프로그래밍은 커다란 하나의 문제를 작은 하위 문제들로 나누어 해결한 뒤, 그 결과를 저장하여 큰 문제 해결에 재활용함으로써 연산 횟수와 실행 시간을 획기적으로 줄이는 알고리즘 설계 기법입니다. 메모이제이션(Memoization)과 타뷸레이션(Tabulation)이라는 기법을 활용합니다.
꼬리 질문
- Q. DP를 적용하기 위해 충족되어야 하는 2가지 조건은?
- A: 첫째는 하위 문제들이 중복해서 반복 등장하는 '부분 문제 반복(Overlapping Subproblems)' 조건이고, 둘째는 부분 문제의 최적의 해가 합쳐져 전체 최적해를 구성할 수 있는 '최적 부분 구조(Optimal Substructure)' 조건입니다.
Q. 그리디 알고리즘이 적용 가능한 조건은?
핵심 답변
그리디 알고리즘은 매 선택 순간에 부분적으로만 최적인 결정(가장 이익이 큰 결정)을 내리며 전체 최적해를 도출하는 기법입니다. 이것이 먹히기 위해선 '탐욕적 선택이 항상 전체 최적해를 지켜줄 것'이라는 탐욕적 선택 속성(Greedy Choice Property)과 큰 문제의 최적해가 부분 해들로 구성되는 최적 부분 구조가 충족되어야 합니다.
꼬리 질문
- Q. 거스름돈 반환 알고리즘에서 그리디가 실패하는 경우는 어떤 경우인가요?
- A: 거스름돈 화폐의 단위들이 서로 배수 관계가 아닐 경우 실패합니다. 예를 들어 단위가 10, 4, 3 일때 12원을 만들 경우 그리디는 10, 1, 1을 선택해 3단계를 수행하지만, 실제 해는 4, 4, 4 즉 3단원이며 최선의 해를 놓치게 됩니다. 이런 경우 DP로 풀어야 합니다.
Q. 안정 정렬(Stable Sort)과 불안정 정렬(Unstable Sort)의 차이점은 무엇인가요?
핵심 답변
안정 정렬은 중복된 키 값을 가진 요소들의 상대적인 순서가 정렬 이후에도 유지되는 정렬 알고리즘을 말합니다. 반면 불안정 정렬은 중복된 키 값들의 순서가 보장되지 않는 알고리즘입니다. 대표적인 안정 정렬로는 병합 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)이 있으며, 불안정 정렬로는 퀵 정렬(Quick Sort)과 힙 정렬(Heap Sort)이 있습니다.
꼬리 질문
- Q. 퀵 정렬(Quick Sort)의 최악의 시간복잡도와 이를 방지하기 위한 개선법은?
- A: 최악의 시간복잡도는 O(N^2)이며, 피벗을 선택할 때 난수를 사용하거나(Randomized Quick Sort) 중앙값(Median of three)을 피벗으로 선택하는 방법으로 최악의 경우를 피할 수 있습니다. 피벗이 한쪽으로 계속 쏠리지 않도록 방지하는 원리입니다.