신입 면접에서 자주 묻는 질문 정리 - 알고리즘(Algorithm) 편

1. 정렬 알고리즘

버블 정렬 (Bubble Sort)

정의: 인접한 두 원소를 비교하여 큰 값을 뒤로 보내는 방식으로 정렬.

동작 과정:

1. 첫 번째 원소부터 인접한 원소와 비교
2. 더 큰 값을 뒤로 이동 (스왑)
3. 한 번의 순회로 가장 큰 값이 맨 뒤로 이동
4. n-1번 반복

시간복잡도:

• 최선: O(n) - 이미 정렬된 경우 (최적화 시)
• 평균: O(n²)
• 최악: O(n²)

공간복잡도: O(1)

특징:

• 구현 간단
• 안정 정렬
• 실무 사용 거의 없음 (비효율적)

선택 정렬 (Selection Sort)

정의: 매 반복마다 최솟값(또는 최댓값)을 찾아 맨 앞과 교환하는 방식.

동작 과정:

1. 배열에서 최솟값 찾기
2. 맨 앞 원소와 교환
3. 정렬된 부분을 제외하고 반복

시간복잡도:

• 최선: O(n²)
• 평균: O(n²)
• 최악: O(n²)

공간복잡도: O(1)

특징:

• 구현 간단
• 불안정 정렬
• 교환 횟수가 적음

삽입 정렬 (Insertion Sort)

정의: 정렬되지 않은 부분의 원소를 정렬된 부분의 적절한 위치에 삽입하는 방식.

동작 과정:

1. 두 번째 원소부터 시작
2. 이전 원소들과 비교하며 적절한 위치 찾기
3. 해당 위치에 삽입

시간복잡도:

• 최선: O(n) - 이미 정렬된 경우
• 평균: O(n²)
• 최악: O(n²)

공간복잡도: O(1)

특징:

• 안정 정렬
• 거의 정렬된 데이터에 효율적
• 작은 데이터셋에 적합

퀵 정렬 (Quick Sort)

정의: 피벗(pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하며 정렬하는 분할 정복 알고리즘.

동작 과정:

1. 피벗 선택 (보통 첫 번째, 마지막, 중간 또는 랜덤 원소)
2. 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
3. 분할된 부분 배열에 대해 재귀적으로 퀵 정렬 수행

시간복잡도:

• 최선: O(n log n)
• 평균: O(n log n)
• 최악: O(n²) - 피벗이 최솟값 또는 최댓값인 경우

공간복잡도: O(log n) - 재귀 호출 스택

특징:

• 불안정 정렬
• 평균적으로 가장 빠름
• 피벗 선택이 성능에 큰 영향
• 캐시 효율성 좋음

병합 정렬 (Merge Sort)

정의: 배열을 반으로 나누어 각각 정렬한 후 합치는 분할 정복 알고리즘.

동작 과정:

1. 배열을 절반으로 나눔 (재귀적으로 크기 1까지)
2. 나눈 배열을 정렬
3. 정렬된 두 배열을 병합

시간복잡도:

• 최선: O(n log n)
• 평균: O(n log n)
• 최악: O(n log n)

공간복잡도: O(n) - 추가 배열 필요

특징:

• 안정 정렬
• 시간복잡도 일정 (예측 가능)
• 연결 리스트 정렬에 효율적
• 추가 메모리 필요

정렬 알고리즘 시간복잡도 비교표

 

정렬	최선	평균	최악	공간복잡도	안정성
버블	O(n)	O(n²)	O(n²)	O(1)	안정
선택	O(n²)	O(n²)	O(n²)	O(1)	불안정
삽입	O(n)	O(n²)	O(n²)	O(1)	안정
퀵	O(n log n)	O(n log n)	O(n²)	O(log n)	불안정
병합	O(n log n)	O(n log n)	O(n log n)	O(n)	안정

주요 언어의 sort 함수 구현

Java

• Arrays.sort() (primitive 타입): Dual-Pivot Quick Sort
• Arrays.sort() (객체): TimSort (병합 정렬 + 삽입 정렬의 하이브리드)
• Collections.sort(): TimSort

Python

• sorted(), list.sort(): TimSort (병합 정렬 + 삽입 정렬의 하이브리드)

JavaScript

• Array.sort(): 엔진마다 다름
  • V8 (Chrome): TimSort
  • 작은 배열: 삽입 정렬

C++

• std::sort(): IntroSort (QuickSort + HeapSort + InsertionSort의 하이브리드)
  • QuickSort로 시작
  • 재귀 깊이 초과 시 HeapSort로 전환
  • 작은 부분은 InsertionSort

TimSort: 실제 데이터는 부분적으로 정렬되어 있는 경우가 많다는 점을 활용. 작은 블록은 삽입 정렬로 정렬하고, 이를 병합 정렬로 합침. 안정 정렬이며 최선 O(n), 최악 O(n log n) 보장.

---

2. 탐색 알고리즘

선형 탐색 (Linear Search)

정의: 배열의 처음부터 끝까지 순차적으로 탐색하는 알고리즘.

동작 과정:

1. 첫 번째 원소부터 시작
2. 찾는 값과 비교
3. 일치하면 인덱스 반환, 아니면 다음 원소로 이동
4. 끝까지 찾지 못하면 -1 반환

시간복잡도:

• 최선: O(1) - 첫 번째 원소가 찾는 값
• 평균: O(n)
• 최악: O(n) - 마지막 원소이거나 없는 경우

공간복잡도: O(1)

특징:

• 구현 간단
• 정렬되지 않은 데이터에도 사용 가능
• 작은 데이터셋에 적합

이진 탐색 (Binary Search)

정의: 정렬된 배열에서 중간값과 비교하며 탐색 범위를 절반씩 줄여가는 알고리즘.

동작 과정:

1. 배열의 중간값과 찾는 값 비교
2. 찾는 값이 중간값보다 작으면 왼쪽 절반 탐색
3. 찾는 값이 중간값보다 크면 오른쪽 절반 탐색
4. 값을 찾거나 범위가 없어질 때까지 반복

시간복잡도:

• 최선: O(1) - 중간값이 찾는 값
• 평균: O(log n)
• 최악: O(log n)

공간복잡도: O(1) - 반복문 / O(log n) - 재귀

특징:

• 반드시 정렬된 배열 필요
• 매우 빠른 탐색
• 대용량 데이터에 효율적

주의: 정렬되지 않은 배열에는 사용 불가

DFS (Depth-First Search, 깊이 우선 탐색)

정의: 그래프/트리에서 한 경로를 끝까지 탐색한 후 다음 경로를 탐색하는 알고리즘.

동작 과정:

1. 시작 노드 방문 표시
2. 인접한 미방문 노드 중 하나 선택
3. 해당 노드로 이동하여 재귀적으로 DFS 수행
4. 더 이상 방문할 노드가 없으면 이전 노드로 백트래킹

구현 방법:

• 재귀: 함수 호출 스택 이용
• 스택: 명시적 스택 자료구조 이용

시간복잡도: O(V + E) - V는 정점 수, E는 간선 수

공간복잡도: O(V) - 방문 체크 배열 + 재귀 스택

특징:

• 모든 경로 탐색에 유리
• 백트래킹 문제에 적합
• 경로의 특징을 저장해야 할 때 유용
• 미로 찾기, 사이클 탐지 등에 사용

BFS (Breadth-First Search, 너비 우선 탐색)

정의: 그래프/트리에서 시작 노드로부터 가까운 노드부터 탐색하는 알고리즘.

동작 과정:

1. 시작 노드를 큐에 삽입하고 방문 표시
2. 큐에서 노드 꺼내기
3. 해당 노드의 인접한 미방문 노드를 모두 큐에 삽입하고 방문 표시
4. 큐가 빌 때까지 반복

구현 방법:

• 큐: FIFO 자료구조 이용

시간복잡도: O(V + E)

공간복잡도: O(V) - 큐 + 방문 체크 배열

특징:

• 최단 경로 찾기에 유리 (가중치 없는 그래프)
• 레벨별 탐색 가능
• 두 노드 간 최단 거리 계산
• 네트워크 플러딩, 최단 경로 등에 사용

DFS vs BFS 비교

 

구분	DFS	BFS
탐색 방식	깊이 우선	너비 우선
자료구조	스택 (재귀)	큐
메모리	적음 (경로 길이에 비례)	많음 (레벨 노드 수에 비례)
최단 경로	보장 안 됨	보장됨 (가중치 없을 때)
적합한 경우	모든 경로 탐색, 백트래킹	최단 경로, 레벨별 탐색

---

3. 시간복잡도/공간복잡도

시간복잡도 (Time Complexity)

정의: 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 증가하는지를 나타내는 지표.

목적:

• 알고리즘의 효율성 평가
• 입력 크기가 커질 때 성능 예측
• 알고리즘 간 비교

측정 기준:

• 연산 횟수 (비교, 대입, 산술 연산 등)
• 입력 크기 n에 대한 함수로 표현

Big-O 표기법

정의: 알고리즘의 최악의 경우 시간복잡도를 나타내는 점근적 표기법.

특징:

• 상수, 낮은 차수 항 무시
• 가장 빠르게 증가하는 항만 표기
• 입력이 충분히 클 때의 성능 평가

주요 Big-O 표기:

 

표기	이름	설명	예시
O(1)	상수 시간	입력 크기와 무관	배열 인덱스 접근, 해시 테이블 조회
O(log n)	로그 시간	절반씩 줄어듦	이진 탐색, 균형 트리 탐색
O(n)	선형 시간	입력에 비례	선형 탐색, 배열 순회
O(n log n)	선형 로그 시간	효율적 정렬	병합 정렬, 퀵 정렬(평균)
O(n²)	이차 시간	중첩 반복문	버블 정렬, 삽입 정렬
O(n³)	삼차 시간	3중 반복문	행렬 곱셈
O(2ⁿ)	지수 시간	매우 느림	피보나치 재귀
O(n!)	팩토리얼 시간	극도로 느림	순열 생성

성능 순서 (빠름 → 느림): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

 

 

예시:

// O(1)
int first = arr[0];

// O(n)
for (int i = 0; i < n; i++) {
    System.out.println(arr[i]);
}

// O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(arr[i] + arr[j]);
    }
}

// O(log n)
while (n > 1) {
    n = n / 2;
}

공간복잡도 (Space Complexity)

정의: 알고리즘 실행에 필요한 메모리 공간이 입력 크기에 따라 어떻게 증가하는지를 나타내는 지표.

포함 요소:

• 고정 공간: 코드, 상수, 단순 변수 (입력 크기와 무관)
• 가변 공간: 동적 할당 메모리, 재귀 호출 스택 (입력 크기에 비례)

예시:

// 공간복잡도 O(1)
int sum(int[] arr) {
    int total = 0;  // 고정 공간
    for (int i = 0; i < arr.length; i++) {
        total += arr[i];
    }
    return total;
}

// 공간복잡도 O(n)
int[] copy(int[] arr) {
    int[] newArr = new int[arr.length];  // n 크기 배열
    for (int i = 0; i < arr.length; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

// 공간복잡도 O(n) - 재귀 스택
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // n번 재귀 호출 = 스택 n개
}

시간복잡도와 공간복잡도 중 무엇이 중요한가?

일반적으로 시간복잡도가 더 중요

이유:

1. 메모리는 상대적으로 저렴: 현대 컴퓨터는 메모리가 충분
2. 사용자 경험: 느린 속도는 직접적으로 체감되지만, 메모리는 부족하기 전까지 느껴지지 않음
3. 확장성: 시간은 돈을 들여도 단축에 한계가 있지만, 메모리는 추가 가능

상황에 따라 공간복잡도가 중요한 경우:

• 임베디드 시스템: 메모리가 제한적인 환경
• 모바일 환경: 배터리, 메모리 제약
• 대용량 데이터: 메모리가 부족하면 디스크 I/O 발생 (오히려 느려짐)
• 분산 시스템: 네트워크 전송 비용

Trade-off:

• 메모이제이션: 공간을 사용해 시간 절약
• 제자리 정렬: 시간을 희생해 공간 절약

결론: 대부분 시간복잡도 우선이지만, 상황에 맞게 균형 있게 고려해야 함.