🏠 홈으로

자료구조와 알고리즘 완전 정리 - 개념부터 면접까지

면접 예상 질문 및 답변 펼치기
Q1: 시간복잡도와 공간복잡도에 대해 설명해주세요.

A: 시간복잡도는 알고리즘이 실행되는데 걸리는 시간을 입력 크기에 따라 표현한 것입니다. 공간복잡도는 알고리즘이 실행되는데 필요한 메모리 공간을 입력 크기에 따라 표현한 것입니다. 보통 Big-O 표기법을 사용해 최악의 경우를 나타내며, O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) 순으로 효율성이 결정됩니다. 알고리즘 선택 시 입력 크기와 요구사항에 따라 적절한 복잡도를 고려해야 합니다.

Q2: 배열과 연결리스트의 차이점을 설명해주세요.

A: 배열은 메모리상에 연속적으로 데이터를 저장하는 자료구조로, 인덱스를 통한 접근이 O(1)로 매우 빠르지만 크기가 고정적이고 중간 삽입/삭제 시 O(n)의 시간이 걸립니다. 연결리스트는 각 노드가 데이터와 다음 노드의 주소를 가지는 구조로, 크기가 동적이고 삽입/삭제가 O(1)로 빠르지만 특정 위치 접근 시 O(n)의 시간이 필요하고 포인터를 위한 추가 메모리가 필요합니다.

Q3: 스택과 큐의 차이점과 활용 예시를 설명해주세요.

A: 스택은 LIFO(Last In First Out) 구조로 마지막에 들어온 데이터가 먼저 나가는 자료구조입니다. 함수 호출 관리, 괄호 검사, 웹브라우저 뒤로가기 기능 등에 활용됩니다. 큐는 FIFO(First In First Out) 구조로 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 프로세스 스케줄링, BFS 탐색, 프린터 대기열 등에 활용됩니다. 둘 다 삽입과 삭제가 O(1)로 효율적입니다.

Q4: 이진 탐색의 동작 원리와 조건을 설명해주세요.

A: 이진 탐색은 정렬된 배열에서 중간값과 찾고자 하는 값을 비교하여 탐색 범위를 절반씩 줄여가며 원하는 값을 찾는 알고리즘입니다. 찾는 값이 중간값보다 작으면 왼쪽 절반을, 크면 오른쪽 절반을 탐색합니다. 시간복잡도는 O(log n)으로 매우 효율적이지만, 반드시 정렬된 데이터에서만 사용할 수 있다는 제약이 있습니다.

Q5: 해시테이블의 동작 원리와 충돌 해결 방법을 설명해주세요.

A: 해시테이블은 해시 함수를 사용해 키를 배열의 인덱스로 변환하여 데이터를 저장하는 자료구조입니다. 평균적으로 O(1)의 시간복잡도로 탐색, 삽입, 삭제가 가능합니다. 충돌 해결 방법으로는 체이닝(같은 인덱스에 연결리스트로 저장)과 개방 주소법(선형 탐사, 이차 탐사, 이중 해싱)이 있습니다. 좋은 해시 함수와 적절한 로드 팩터 관리가 성능의 핵심입니다.

Q6: DFS와 BFS의 차이점과 각각의 활용 사례를 설명해주세요.

A: DFS(깊이 우선 탐색)는 스택을 사용해 한 방향으로 깊게 탐색한 후 백트래킹하는 방식입니다. 경로 탐색, 사이클 검사, 위상 정렬에 적합합니다. BFS(너비 우선 탐색)는 큐를 사용해 현재 레벨의 모든 노드를 먼저 방문하는 방식입니다. 최단 경로 탐색, 레벨별 탐색에 적합합니다. DFS는 메모리 사용량이 적고, BFS는 최단 경로를 보장한다는 특징이 있습니다.

Q7: 정렬 알고리즘들의 특징을 비교해서 설명해주세요.

A: 버블 정렬은 O(n²)로 느리지만 구현이 간단하고, 선택 정렬은 O(n²)이지만 교환 횟수가 적습니다. 삽입 정렬은 O(n²)이지만 부분적으로 정렬된 데이터에 효율적입니다. 퀵 정렬은 평균 O(n log n)으로 빠르지만 최악의 경우 O(n²)입니다. 머지 정렬은 안정적으로 O(n log n)을 보장하지만 추가 메모리가 필요합니다. 힙 정렬은 O(n log n)이고 제자리 정렬이지만 불안정 정렬입니다.

Q8: 트리와 그래프의 차이점을 설명해주세요.

A: 트리는 사이클이 없는 연결된 그래프로, 루트 노드가 있고 각 노드가 부모-자식 관계를 가집니다. n개의 노드에 n-1개의 간선을 가지며, 임의의 두 노드 사이에는 유일한 경로가 존재합니다. 그래프는 노드와 간선으로 구성된 일반적인 자료구조로, 사이클이 있을 수 있고 방향성 유무에 따라 유향/무향 그래프로 나뉩니다. 트리는 그래프의 특수한 형태라고 볼 수 있습니다.

Q9: 힙(Heap)의 특징과 활용 사례를 설명해주세요.

A: 힙은 완전 이진 트리 형태의 자료구조로, 최대 힙은 부모가 자식보다 크거나 같고, 최소 힙은 부모가 자식보다 작거나 같다는 조건을 만족합니다. 삽입과 삭제가 O(log n)으로 효율적이며, 최대값/최소값을 O(1)에 찾을 수 있습니다. 우선순위 큐 구현, 힙 정렬, 다익스트라 알고리즘 등에 활용됩니다. 배열로 구현하면 인덱스 i의 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2에 위치합니다.

Q10: 동적 계획법(Dynamic Programming)에 대해 설명해주세요.

A: 동적 계획법은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 부분 문제의 결과를 저장하여 중복 계산을 피하는 알고리즘 기법입니다. 최적 부분 구조와 중복되는 부분 문제라는 두 조건을 만족해야 적용할 수 있습니다. Top-down(메모이제이션)과 Bottom-up(테이블 채우기) 방식이 있으며, 피보나치 수열, 배낭 문제, 최장 공통 부분수열 등에 활용됩니다.

추가 면접 예상 질문 및 답변 펼치기
Q11: 배열과 동적 배열의 차이점을 설명해주세요.

A: 정적 배열은 컴파일 시점에 크기가 고정되어 변경할 수 없지만, 동적 배열은 런타임에 크기를 변경할 수 있습니다. 동적 배열은 내부적으로 고정 크기 배열을 사용하되, 용량이 부족하면 더 큰 배열을 할당하고 기존 데이터를 복사합니다. 이때 amortized O(1)의 삽입 시간복잡도를 가지지만, 재할당이 발생하는 경우에는 O(n)의 시간이 걸립니다. ArrayList, Vector 등이 동적 배열의 예시입니다.

Q12: 이진 탐색 트리와 균형 트리의 차이점을 설명해주세요.

A: 이진 탐색 트리는 왼쪽 자식이 부모보다 작고 오른쪽 자식이 부모보다 큰 조건을 만족하는 트리입니다. 평균적으로 O(log n)의 성능을 보이지만, 편향 트리가 되면 O(n)까지 성능이 저하될 수 있습니다. 균형 트리(AVL, Red-Black Tree 등)는 트리의 높이를 자동으로 조절하여 항상 O(log n)의 성능을 보장합니다. 삽입/삭제 시 회전 연산을 통해 균형을 맞추므로 약간의 오버헤드가 있지만 안정적인 성능을 제공합니다.

Q13: 우선순위 큐를 구현하는 방법들을 비교해주세요.

A: 배열로 구현하면 삽입은 O(1)이지만 최우선순위 요소 찾기가 O(n)입니다. 정렬된 배열로 구현하면 찾기는 O(1)이지만 삽입이 O(n)입니다. 연결리스트는 배열과 비슷한 특성을 가집니다. 힙으로 구현하면 삽입과 삭제가 모두 O(log n)으로 균형 잡힌 성능을 제공합니다. 따라서 일반적으로 힙을 사용한 구현이 가장 효율적이며, 대부분의 언어에서 기본 우선순위 큐 구현으로 힙을 사용합니다.

Q14: 해시맵과 트리맵의 차이점을 설명해주세요.

A: 해시맵은 해시 테이블 기반으로 평균 O(1)의 성능을 제공하지만 데이터가 정렬되지 않습니다. 트리맵은 이진 탐색 트리 기반으로 O(log n)의 성능을 가지지만 데이터가 자동으로 정렬됩니다. 해시맵은 단순한 키-값 저장/검색에 적합하고, 트리맵은 정렬된 순서가 중요하거나 범위 검색이 필요한 경우에 적합합니다. 메모리 사용량은 해시맵이 더 효율적이지만, 트리맵은 추가 포인터로 인한 오버헤드가 있습니다.

Q15: 재귀와 반복문의 차이점과 각각의 장단점을 설명해주세요.

A: 재귀는 함수가 자기 자신을 호출하는 방식으로, 코드가 직관적이고 분할정복 문제에 적합하지만 스택 오버플로우 위험이 있고 함수 호출 오버헤드가 발생합니다. 반복문은 루프를 사용하는 방식으로, 메모리 효율적이고 성능이 좋지만 복잡한 문제에서는 코드가 복잡해질 수 있습니다. 꼬리 재귀 최적화가 지원되는 경우 재귀의 단점을 줄일 수 있고, 일부 재귀 알고리즘은 반복문으로 변환 가능합니다.

Q16: 그리디 알고리즘의 특징과 한계점을 설명해주세요.

A: 그리디 알고리즘은 각 단계에서 지역적으로 최적인 선택을 하여 전역 최적해를 구하려는 방법입니다. 간단하고 빠르며 직관적이지만, 항상 최적해를 보장하지는 않습니다. 그리디 선택 속성(지역 최적 선택이 전역 최적해에 포함)과 최적 부분 구조(부분 문제의 최적해가 전체 최적해에 포함)를 만족해야 올바른 결과를 얻을 수 있습니다. 활동 선택 문제, 허프만 코딩, 최소 신장 트리 등에 적용됩니다.

Q17: 분할정복 알고리즘의 원리와 예시를 설명해주세요.

A: 분할정복은 문제를 작은 부분 문제로 나누어 해결하고, 부분 해를 결합하여 전체 해를 구하는 방법입니다. 분할(Divide), 정복(Conquer), 결합(Combine)의 3단계로 구성됩니다. 재귀적 구조를 가지며, 대표적인 예시로는 머지 정렬, 퀵 정렬, 이진 탐색, 거듭제곱 연산 등이 있습니다. 주로 O(n log n)의 시간복잡도를 가지며, 문제의 크기를 절반으로 줄여가며 해결하는 특징이 있습니다.

Q18: 최단 경로 알고리즘들을 비교해서 설명해주세요.

A: 다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 구합니다(O(V²) 또는 O(E log V)). 벨만-포드 알고리즘은 음의 가중치를 허용하지만 음의 사이클은 검출할 수 있으며 시간복잡도는 O(VE)입니다. 플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하며 O(V³)의 시간복잡도를 가집니다. 각각 그래프의 특성과 요구사항에 따라 선택해야 합니다.

Q19: 백트래킹 알고리즘에 대해 설명해주세요.

A: 백트래킹은 해를 찾는 도중 막다른 길에 도달하면 이전 상태로 돌아가서 다른 경로를 탐색하는 방법입니다. 모든 가능한 경우를 체계적으로 탐색하되, 조건에 맞지 않으면 즉시 후보를 제거하여 탐색 공간을 줄입니다. DFS를 기반으로 하며, N-Queen 문제, 스도쿠 해결, 미로 찾기 등에 활용됩니다. 가지치기(pruning)를 통해 효율성을 높일 수 있지만, 최악의 경우 모든 경우를 탐색해야 할 수도 있습니다.

Q20: Big-O, Big-Θ, Big-Ω의 차이점을 설명해주세요.

A: Big-O는 알고리즘의 상한(최악의 경우)을 나타내며, "최대 이만큼의 시간이 걸린다"는 의미입니다. Big-Ω는 하한(최선의 경우)을 나타내며, "최소 이만큼의 시간이 걸린다"는 의미입니다. Big-Θ는 상한과 하한이 같을 때 사용하며, "정확히 이만큼의 시간이 걸린다"는 의미입니다. 일반적으로 Big-O 표기법을 가장 많이 사용하며, 알고리즘의 확장성을 평가할 때 중요한 지표가 됩니다.

Q21: 시간복잡도와 실제 실행시간의 관계를 설명해주세요.

A: 시간복잡도는 입력 크기에 따른 연산 횟수의 증가율을 나타내는 이론적 지표입니다. 실제 실행시간은 하드웨어, 컴파일러 최적화, 캐시 성능, 상수 인수 등에 영향을 받습니다. 따라서 O(n²) 알고리즘이 작은 입력에서는 O(n log n) 알고리즘보다 빠를 수 있습니다. 또한 같은 시간복잡도라도 상수 인수나 캐시 친화성에 따라 성능 차이가 발생할 수 있어, 실제 성능 평가에서는 벤치마킹이 중요합니다.

Q22: 메모이제이션과 테이블화의 차이점을 설명해주세요.

A: 메모이제이션은 Top-down 방식으로 재귀 함수에서 계산 결과를 캐시에 저장하여 중복 계산을 피하는 기법입니다. 필요할 때만 계산하므로 메모리를 절약할 수 있지만 재귀 호출 오버헤드가 있습니다. 테이블화는 Bottom-up 방식으로 작은 부분 문제부터 순서대로 해결하여 테이블에 저장하는 기법입니다. 재귀 오버헤드가 없고 반복문을 사용하지만, 모든 부분 문제를 계산해야 하므로 불필요한 계산이 발생할 수 있습니다.

---

자료구조와 알고리즘 개념 정리 (전체) 펼치기

1. 복잡도 분석

1.1 시간복잡도 (Time Complexity)

알고리즘이 실행되는데 걸리는 시간을 입력 크기에 따라 함수로 표현한 것입니다.

Big-O 표기법

  • O(1): 상수 시간 - 입력 크기와 관계없이 일정한 시간
  • O(log n): 로그 시간 - 이진 탐색, 균형 트리 연산
  • O(n): 선형 시간 - 배열 순회, 선형 탐색
  • O(n log n): 로그 선형 시간 - 효율적인 정렬 알고리즘
  • O(n²): 이차 시간 - 중첩 반복문, 기본 정렬 알고리즘
  • O(2ⁿ): 지수 시간 - 피보나치 재귀, 부분집합 생성

1.2 공간복잡도 (Space Complexity)

알고리즘이 실행되는데 필요한 메모리 공간을 입력 크기에 따라 표현한 것입니다.

2. 기본 자료구조

2.1 배열 (Array)

동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조입니다.

특징

  • 인덱스를 통한 직접 접근: O(1)
  • 메모리 효율성: 연속된 메모리 할당
  • 크기 고정: 선언 시 크기 결정
  • 캐시 친화적: 지역성으로 인한 성능 향상

연산 복잡도

  • 접근: O(1)
  • 탐색: O(n)
  • 삽입: O(n) - 중간 삽입 시
  • 삭제: O(n) - 중간 삭제 시

2.2 연결리스트 (Linked List)

각 노드가 데이터와 다음 노드의 주소를 포함하는 동적 자료구조입니다.

종류

  • 단일 연결리스트: 한 방향으로만 연결
  • 이중 연결리스트: 양방향으로 연결
  • 원형 연결리스트: 마지막 노드가 첫 노드를 가리킴

연산 복잡도

  • 접근: O(n)
  • 탐색: O(n)
  • 삽입: O(1) - 위치를 알고 있을 때
  • 삭제: O(1) - 위치를 알고 있을 때

2.3 스택 (Stack)

LIFO(Last In First Out) 원칙을 따르는 자료구조입니다.

주요 연산

  • push: 스택 맨 위에 요소 추가
  • pop: 스택 맨 위 요소 제거 및 반환
  • top/peek: 스택 맨 위 요소 확인
  • isEmpty: 스택이 비어있는지 확인

활용 사례

  • 함수 호출 관리
  • 수식의 괄호 검사
  • 웹브라우저 뒤로가기
  • DFS 구현

2.4 큐 (Queue)

FIFO(First In First Out) 원칙을 따르는 자료구조입니다.

주요 연산

  • enqueue: 큐의 끝에 요소 추가
  • dequeue: 큐의 앞에서 요소 제거 및 반환
  • front: 큐의 첫 번째 요소 확인
  • isEmpty: 큐가 비어있는지 확인

종류

  • 선형 큐: 일반적인 큐
  • 원형 큐: 배열을 원형으로 사용
  • 우선순위 큐: 우선순위에 따라 처리
  • 덱(Deque): 양끝에서 삽입/삭제 가능

3. 트리 (Tree)

3.1 트리 기본 개념

계층적 구조를 가진 비선형 자료구조로, 사이클이 없는 연결 그래프입니다.

트리 용어

  • 루트: 트리의 최상위 노드
  • 부모/자식: 직접 연결된 노드들의 관계
  • 리프: 자식이 없는 노드
  • 레벨: 루트부터의 거리
  • 높이: 리프까지의 최대 거리
  • 차수: 자식 노드의 개수

3.2 이진트리 (Binary Tree)

각 노드가 최대 2개의 자식을 가지는 트리입니다.

종류

  • 완전 이진트리: 마지막 레벨을 제외하고 모든 레벨이 채워진 트리
  • 포화 이진트리: 모든 내부 노드가 2개의 자식을 가지는 트리
  • 균형 이진트리: 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하

3.3 이진 탐색 트리 (BST)

왼쪽 자식 < 부모 < 오른쪽 자식 조건을 만족하는 이진트리입니다.

연산 복잡도

  • 탐색: 평균 O(log n), 최악 O(n)
  • 삽입: 평균 O(log n), 최악 O(n)
  • 삭제: 평균 O(log n), 최악 O(n)

3.4 힙 (Heap)

완전 이진트리로 구현되는 우선순위 큐입니다.

종류

  • 최대 힙: 부모 >= 자식
  • 최소 힙: 부모 <= 자식

연산

  • 삽입: O(log n)
  • 삭제: O(log n)
  • 최댓값/최솟값 조회: O(1)

4. 해시테이블 (Hash Table)

4.1 해시 함수

키를 배열의 인덱스로 변환하는 함수입니다.

좋은 해시 함수의 조건

  • 계산이 빠름
  • 해시값이 고르게 분포
  • 결정적 (같은 입력에 같은 출력)

4.2 충돌 해결

서로 다른 키가 같은 해시값을 가지는 경우를 해결하는 방법입니다.

체이닝 (Chaining)

  • 같은 해시값을 가진 요소들을 연결리스트로 저장
  • 구현이 간단하지만 추가 메모리 필요

개방 주소법 (Open Addressing)

  • 선형 탐사: 순차적으로 다음 빈 자리 탐색
  • 이차 탐사: 제곱수만큼 떨어진 자리 탐색
  • 이중 해싱: 다른 해시 함수로 탐사 간격 결정

5. 그래프 (Graph)

5.1 그래프 기본 개념

정점(Vertex)과 간선(Edge)으로 구성된 자료구조입니다.

그래프 종류

  • 방향 그래프: 간선에 방향이 있음
  • 무방향 그래프: 간선에 방향이 없음
  • 가중 그래프: 간선에 가중치가 있음
  • 완전 그래프: 모든 정점이 서로 연결됨

그래프 표현 방법

  • 인접 행렬: 2차원 배열로 표현 (공간: O(V²))
  • 인접 리스트: 각 정점마다 연결된 정점들을 리스트로 저장 (공간: O(V+E))

5.2 그래프 탐색

DFS (깊이 우선 탐색)

스택을 사용하여 한 방향으로 깊게 탐색하는 방법입니다.

  • 시간복잡도: O(V + E)
  • 공간복잡도: O(V)
  • 활용: 경로 탐색, 사이클 검사, 위상 정렬

BFS (너비 우선 탐색)

큐를 사용하여 레벨별로 탐색하는 방법입니다.

  • 시간복잡도: O(V + E)
  • 공간복잡도: O(V)
  • 활용: 최단 경로, 레벨별 순회

6. 정렬 알고리즘

6.1 기본 정렬 알고리즘

버블 정렬 (Bubble Sort)

인접한 두 원소를 비교하여 정렬하는 방법입니다.

  • 시간복잡도: O(n²)
  • 공간복잡도: O(1)
  • 안정 정렬
  • 구현이 간단하지만 비효율적

선택 정렬 (Selection Sort)

최솟값을 찾아 앞쪽에 배치하는 방법입니다.

  • 시간복잡도: O(n²)
  • 공간복잡도: O(1)
  • 불안정 정렬
  • 교환 횟수가 적음

삽입 정렬 (Insertion Sort)

정렬된 부분에 새로운 원소를 올바른 위치에 삽입하는 방법입니다.

  • 시간복잡도: 최선 O(n), 평균/최악 O(n²)
  • 공간복잡도: O(1)
  • 안정 정렬
  • 부분적으로 정렬된 데이터에 효율적

6.2 고급 정렬 알고리즘

퀵 정렬 (Quick Sort)

피벗을 선택하여 작은 값과 큰 값으로 분할하여 정렬하는 방법입니다.

  • 시간복잡도: 평균 O(n log n), 최악 O(n²)
  • 공간복잡도: O(log n)
  • 불안정 정렬
  • 실제로 가장 빠른 정렬 중 하나

머지 정렬 (Merge Sort)

분할정복으로 배열을 반으로 나누어 정렬 후 합치는 방법입니다.

  • 시간복잡도: O(n log n)
  • 공간복잡도: O(n)
  • 안정 정렬
  • 성능이 일정함

힙 정렬 (Heap Sort)

힙 자료구조를 이용하여 정렬하는 방법입니다.

  • 시간복잡도: O(n log n)
  • 공간복잡도: O(1)
  • 불안정 정렬
  • 최악의 경우에도 성능 보장

7. 탐색 알고리즘

7.1 선형 탐색 (Linear Search)

배열을 처음부터 끝까지 순차적으로 탐색하는 방법입니다.

  • 시간복잡도: O(n)
  • 정렬되지 않은 데이터에서도 사용 가능
  • 구현이 간단

7.2 이진 탐색 (Binary Search)

정렬된 배열에서 중간값과 비교하여 탐색 범위를 줄여가는 방법입니다.

  • 시간복잡도: O(log n)
  • 반드시 정렬된 데이터여야 함
  • 매우 효율적

8. 고급 알고리즘 기법

8.1 동적 계획법 (Dynamic Programming)

복잡한 문제를 작은 부분 문제로 나누어 해결하는 방법입니다.

적용 조건

  • 최적 부분 구조: 부분 문제의 최적해가 전체 문제의 최적해에 포함
  • 중복되는 부분 문제: 같은 부분 문제가 여러 번 계산됨

구현 방식

  • Top-down (메모이제이션): 재귀 + 캐싱
  • Bottom-up (테이블화): 반복문으로 작은 문제부터 해결

8.2 그리디 알고리즘

각 단계에서 지역적으로 최적인 선택을 하는 방법입니다.

적용 조건

  • 그리디 선택 속성: 지역 최적 선택이 전역 최적해로 이어짐
  • 최적 부분 구조: 부분 문제의 최적해가 전체 최적해에 포함

대표 문제

  • 활동 선택 문제
  • 분할 가능 배낭 문제
  • 허프만 코딩

8.3 분할정복 (Divide and Conquer)

문제를 작은 부분으로 나누어 해결 후 결과를 합치는 방법입니다.

단계

  1. 분할: 문제를 작은 부분 문제로 나눔
  2. 정복: 부분 문제를 재귀적으로 해결
  3. 결합: 부분 해를 합쳐 전체 해 구성

대표 예시

  • 머지 정렬
  • 퀵 정렬
  • 이진 탐색
  • 거듭제곱 계산

8.4 백트래킹 (Backtracking)

모든 가능한 경우를 탐색하되, 조건에 맞지 않으면 이전 상태로 돌아가는 방법입니다.

특징

  • DFS 기반
  • 가지치기를 통한 효율성 향상
  • 해가 존재하지 않을 때 확실히 판별 가능

대표 문제

  • N-Queen 문제
  • 스도쿠
  • 미로 찾기
  • 조합/순열 생성

9. 최단 경로 알고리즘

9.1 다익스트라 알고리즘

음이 아닌 가중치를 가진 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘입니다.

동작 원리

  1. 시작 정점의 거리를 0으로, 나머지를 무한대로 초기화
  2. 방문하지 않은 정점 중 거리가 최소인 정점 선택
  3. 선택된 정점을 거쳐 다른 정점으로 가는 거리 업데이트
  4. 모든 정점을 방문할 때까지 반복
  • 시간복잡도: O(V²) 또는 O(E log V) (우선순위 큐 사용 시)

9.2 벨만-포드 알고리즘

음의 가중치를 허용하는 최단 경로 알고리즘입니다.

특징

  • 음의 사이클 검출 가능
  • 시간복잡도: O(VE)
  • 모든 간선에 대해 V-1번 완화 연산 수행

9.3 플로이드-워셜 알고리즘

모든 정점 쌍 간의 최단 경로를 구하는 알고리즘입니다.

동작 원리

  • 경유지 k를 통해 i에서 j로 가는 경로와 직접 가는 경로 비교
  • 시간복잡도: O(V³)
  • 동적 계획법 사용

10. 문자열 알고리즘

10.1 패턴 매칭

브루트 포스

모든 위치에서 패턴을 비교하는 방법입니다.

  • 시간복잡도: O(nm) (n: 텍스트 길이, m: 패턴 길이)

KMP 알고리즘

실패 함수를 이용하여 불필요한 비교를 줄이는 방법입니다.

  • 시간복잡도: O(n + m)
  • 전처리로 실패 함수 계산 필요

11. 기타 중요한 개념

11.1 재귀 (Recursion)

함수가 자기 자신을 호출하는 프로그래밍 기법입니다.

구성 요소

  • 기저 조건: 재귀 호출을 멈추는 조건
  • 재귀 호출: 자기 자신을 호출하는 부분

장단점

  • 장점: 직관적, 분할정복 문제에 적합
  • 단점: 스택 오버플로우 위험, 함수 호출 오버헤드

11.2 반복자 (Iterator)

컨테이너의 원소에 순차적으로 접근할 수 있게 하는 객체입니다.

종류

  • 입력 반복자
  • 출력 반복자
  • 순방향 반복자
  • 양방향 반복자
  • 임의 접근 반복자

11.3 재귀와 반복의 변환

일반적으로 재귀 알고리즘은 스택을 사용하여 반복문으로 변환할 수 있습니다.

12. 알고리즘 설계 전략

12.1 문제 해결 과정

  1. 문제 이해 및 분석
  2. 알고리즘 설계
  3. 복잡도 분석
  4. 구현
  5. 테스트 및 최적화

12.2 최적화 기법

  • 시간-공간 트레이드오프: 메모리를 더 사용하여 시간을 단축
  • 전처리: 미리 계산하여 쿼리 시간 단축
  • 캐싱: 계산 결과 저장으로 중복 계산 방지
  • 병렬화: 작업을 여러 프로세서로 분산

12.3 자료구조 선택 가이드

  • 배열: 인덱스 접근이 빈번한 경우
  • 연결리스트: 삽입/삭제가 빈번한 경우
  • 스택: LIFO 패턴의 데이터 처리
  • 큐: FIFO 패턴의 데이터 처리
  • 해시테이블: 빠른 검색이 필요한 경우
  • 트리: 계층적 데이터나 정렬된 데이터
  • 그래프: 복잡한 관계를 표현해야 하는 경우