알고리즘 자료구조 강의 자료입니다.
알고리즘은 프로그램의 설계도로, 프로그램의 결과는 이 설계도를 바탕으로 지어진 건물에 비유할 수 있습니다. 알고리즘은 수학적 개념에 가깝고, 프로그래밍은 이를 구현하는 과정입니다. 이 둘은 서로에게 필수적이며, 알고리즘에 따라 프로그램의 속도나 처리 방식이 달라질 수 있습니다. 따라서, 알고리즘을 이해하고 선택하는 것이 중요합니다.
알고리즘의 성능을 평가하는 척도로, 시간 복잡도와 공간 복잡도가 있습니다. 시간 복잡도는 알고리즘의 수행 시간을 평가하는 척도로, 입력 크기에 따라 수행 시간이 어떻게 증가하는지를 나타냅니다. 시간 복잡도는 빅오 표기법으로 표현하며, 최악의 경우를 나타냅니다.
알고리즘의 시간 복잡도는 입력 크기에 따라 알고리즘의 수행 시간이 어떻게 증가하는지를 나타냅니다. 아래는 일반적인 시간 복잡도 표기와 그 의미를 정리한 표입니다.
| 표기법 | 명칭 | 설명 |
|---|---|---|
| ( O(1) ) | 상수 시간 | 입력 크기에 상관없이 항상 일정한 시간이 소요됩니다. |
| ( O(\log n) ) | 로그 시간 | 입력 크기가 커질수록 수행 시간이 로그 함수 형태로 증가합니다. |
| ( O(n) ) | 선형 시간 | 입력 크기에 비례하여 수행 시간이 증가합니다. |
| ( O(n \log n) ) | 로그 선형 시간 | 입력 크기와 로그 함수의 곱 형태로 수행 시간이 증가합니다. |
| ( O(n^2) ) | 이차 시간 | 입력 크기의 제곱에 비례하여 수행 시간이 증가합니다. |
| ( O(2^n) ) | 지수 시간 | 입력 크기에 따라 수행 시간이 지수 함수 형태로 증가합니다. |
| ( O(n!) ) | 팩토리얼 시간 | 입력 크기에 따라 수행 시간이 팩토리얼 함수 형태로 증가합니다. |
이 표는 알고리즘의 효율성을 평가할 때 유용하게 사용됩니다. 시간 복잡도가 낮을수록 알고리즘이 더 효율적입니다.
공간 복잡도는 알고리즘의 메모리 사용량을 평가하는 척도로, 입력 크기에 따라 알고리즘의 메모리 사용량이 어떻게 증가하는지를 나타냅니다. 공간 복잡도는 빅오 표기법으로 표현하며, 최악의 경우를 나타냅니다.
자료구조는 데이터를 효율적으로 저장하고 관리하는 방법을 의미합니다. 데이터를 저장하는 방식에 따라 성능이 달라지며, 알고리즘의 성능을 높이기 위해 자료구조를 잘 선택하는 것이 중요합니다. 자료구조에는 배열, 연결 리스트, 스택, 큐, 트리, 그래프 등이 있으며, 각각의 특징과 사용법을 알고 있어야 합니다.
선형 자료구조는 데이터를 일렬로 저장하는 방식으로, 데이터를 순차적으로 접근할 수 있습니다. 대표적인 선형 자료구조로는 배열, 연결 리스트, 스택, 큐 등이 있습니다.
- 정의: 배열은 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조입니다.
- 특징:
- 인덱스를 통해 각 요소에 직접 접근 가능 (시간복잡도 O(1))
- 크기가 고정되어 있어 미리 크기를 설정해야 함
- 삽입, 삭제가 비효율적 (평균적으로 O(n))
- 정의: 연결 리스트는 각 요소가 노드로 이루어져 있으며, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함하는 자료구조입니다.
- 특징:
- 동적 메모리 할당으로 크기 제한이 없음
- 삽입, 삭제가 배열보다 효율적 (시간복잡도 O(1) ~ O(n))
- 인덱스 접근이 불가능하며 순차 탐색만 가능 (시간복잡도 O(n))
- 정의: 스택은 후입선출(LIFO, Last In First Out) 방식으로 작동하는 자료구조입니다.
- 특징:
- 데이터 삽입과 삭제가 한쪽 끝에서만 이루어짐
- 삽입(푸시)와 삭제(팝)의 시간복잡도는 O(1)
- 주로 함수 호출 관리, 역순 작업 등에 사용됨
- 정의: 큐는 선입선출(FIFO, First In First Out) 방식으로 작동하는 자료구조입니다.
- 특징:
- 데이터 삽입은 뒤쪽(후단), 삭제는 앞쪽(전단)에서 이루어짐
- 삽입(인큐)와 삭제(디큐)의 시간복잡도는 O(1)
- 주로 작업 대기열, 버퍼 관리 등에 사용됨
- 정의: 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다.
- 특징:
- 큐와 스택을 합친 형태로, 양쪽 끝에서 삽입과 삭제가 가능
- 삽입과 삭제의 시간복잡도는 O(1)
- 주로 스크롤, 양방향 탐색 등에 사용됨
- 큐와 스택의 장점을 모두 가지고 있어 다양한 상황에 활용 가능
- 정의: set은 중복을 허용하지 않고, 순서가 없는 자료구조입니다.
- 특징:
- 중복을 허용하지 않고, 순서가 없는 자료구조
- 삽입, 삭제, 검색의 시간복잡도는 O(1) ~ O(n)
- 주로 집합 연산, 중복 제거 등에 사용됨
- 해시 테이블, 트리 등 다양한 방식으로 구현 가능
비선형 자료구조는 데이터를 계층적으로 저장하는 방식으로, 데이터를 순차적으로 접근할 수 없습니다. 대표적인 비선형 자료구조로는 트리, 그래프 등이 있습니다.
- 정의: 트리는 계층적인 구조로 데이터를 저장하는 자료구조입니다.
- 특징:
- 노드와 간선으로 이루어져 있으며, 루트 노드에서 시작하여 각 노드가 자식 노드를 가짐
- 이진 트리, 이진 탐색 트리, AVL 트리, 힙 등 다양한 종류가 있음
- 주로 계층적인 데이터를 표현하거나 탐색, 정렬 등에 사용됨
- 정의: 그래프는 정점과 간선으로 이루어진 자료구조로, 노드와 간선의 집합으로 표현됩니다.
- 특징:
- 방향성에 따라 유향 그래프와 무향 그래프로 나뉨
- 노드 간의 관계를 표현하며, 최단 경로, 네트워크 흐름 등 다양한 문제에 사용됨
- 인접 행렬, 인접 리스트 등 다양한 방식으로 표현 가능
- 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 등 다양한 탐색 알고리즘이 존재
- 최단 경로 탐색, 최소 신장 트리, 위상 정렬 등 다양한 문제를 해결할 수 있음
- 그래프는 네트워크, 지도, 도로 등 다양한 현실 세계의 문제를 표현하고 해결하는 데 사용됨
- 정의: 힙은 완전 이진 트리로 구성된 자료구조로, 최댓값과 최솟값을 빠르게 찾아내기 위해 고안된 자료구조입니다.
- 특징:
- 최대 힙과 최소 힙으로 나뉘며, 부모 노드가 자식 노드보다 크거나 작은 조건을 만족
- 삽입, 삭제, 최댓값/최솟값 검색의 시간복잡도는 O(log n)
- 우선순위 큐, 힙 정렬 등 다양한 문제에 사용됨
- 힙은 완전 이진 트리이므로 배열로 표현 가능하며, 인덱스 계산을 통해 효율적인 구현이 가능
- 힙은 최댓값과 최솟값을 빠르게 찾아내는 데 사용되며, 우선순위 큐, 힙 정렬 등 다양한 문제에 사용됨
- 힙은 완전 이진 트리이므로 배열로 표현 가능하며, 인덱스 계산을 통해 효율적인 구현이 가능
- 정의: 해시 테이블은 키(key)에 데이터(value)를 저장하는 자료구조로, 키를 해시 함수를 통해 해시값으로 변환하여 데이터를 저장하고 검색하는 방식입니다.
- 특징:
- 키를 해시 함수로 변환하여 해시값으로 저장하므로 빠른 검색이 가능
- 충돌(Collision)을 해결하기 위한 방법으로 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있음
- 삽입, 삭제, 검색의 시간복잡도는 O(1) ~ O(n)
- 해시 테이블은 검색이 빠르고 간단한 키-값 저장소로 사용되며, 캐시, 데이터베이스 인덱스, 집합 등 다양한 문제에 사용됨
- 정의: Map은 키(key)와 값(value)을 한 쌍으로 저장하는 자료구조로, 키를 통해 값을 검색하거나 수정할 수 있습니다.
- 특징:
- 키와 값의 쌍을 저장하며, 키를 통해 값을 검색하거나 수정할 수 있음
- 삽입, 삭제, 검색의 시간복잡도는 O(1) ~ O(n)
- 해시 테이블, 트리 등 다양한 방식으로 구현 가능
- Map은 키-값 쌍을 저장하고 검색하는 데 사용되며, 해시 테이블, 트리 등 다양한 방식으로 구현 가능
알고리즘은 문제를 해결하는 절차나 방법을 의미하며, 주어진 입력을 출력으로 변환하는 과정을 나타냅니다. 알고리즘은 효율성을 평가하는 시간 복잡도와 공간 복잡도를 고려하여 설계되어야 하며, 주어진 문제에 대해 최적의 해결 방법을 찾는 것이 중요합니다.
- 입력: 외부에서 제공되는 자료가 있어야 합니다.
- 출력: 적어도 하나 이상의 결과가 있어야 합니다.
- 명백성: 각 명령어는 명확하고 명백해야 합니다.
- 유한성: 유한 번의 명령어를 수행한 후에는 반드시 종료해야 합니다.
- 효과성: 모든 명령어는 명백하고 실행 가능한 연산이어야 합니다.
- 일반성: 모든 경우에 적용 가능해야 합니다.
- 최적성: 다른 알고리즘에 비해 더 나은 성능을 가져야 합니다.
- 알고리즘의 성능 평가: 알고리즘의 성능은 시간 복잡도와 공간 복잡도로 평가합니다.
- 시간 복잡도: 알고리즘의 수행 시간을 평가하는 척도로, 입력 크기에 따라 수행 시간이 어떻게 증가하는지를 나타냅니다.
- 공간 복잡도: 알고리즘의 메모리 사용량을 평가하는 척도로, 입력 크기에 따라 메모리 사용량이 어떻게 증가하는지를 나타냅니다.
- 알고리즘의 효율성: 시간 복잡도와 공간 복잡도가 낮을수록 알고리즘이 더 효율적입니다.
- 버블 정렬: 인접한 두 원소를 비교하여 정렬하는 방식으로, 시간 복잡도는 O(n^2)입니다.
- 선택 정렬: 주어진 리스트에서 최솟값을 찾아 맨 앞으로 이동하는 방식으로, 시간 복잡도는 O(n^2)입니다.
- 삽입 정렬: 각 원소를 적절한 위치에 삽입하는 방식으로, 시간 복잡도는 O(n^2)입니다.
- 퀵 정렬: 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어 정렬하는 방식으로, 시간 복잡도는 O(n log n)입니다.
- 병합 정렬: 리스트를 반으로 나누어 각각 정렬한 후 병합하는 방식으로, 시간 복잡도는 O(n log n)입니다.
- 힙 정렬: 최대 힙 또는 최소 힙을 구성하여 정렬하는 방식으로, 시간 복잡도는 O(n log n)입니다.
- 기수 정렬: 자릿수를 기준으로 정렬하는 방식으로, 시간 복잡도는 O(d(n+r))입니다.
- 계수 정렬: 특정 범위의 정수를 세는 방식으로, 시간 복잡도는 O(n+r)입니다.
- 버킷 정렬: 데이터를 여러 개의 버킷으로 나누어 정렬하는 방식으로, 시간 복잡도는 O(n^2)입니다.
- 셸 정렬: 삽입 정렬을 보완한 방식으로, 시간 복잡도는 O(n log n)입니다.
- 카운팅 정렬: 특정 범위의 정수를 세는 방식으로, 시간 복잡도는 O(n+r)입니다.
- 완전 탐색: 가능한 모든 경우의 수를 탐색하는 방법으로, 브루트 포스(Brute Force)라고도 불립니다.
- 탐욕 알고리즘: 각 단계에서 최적의 선택을 하는 방법으로, 현재 상태에서 가장 좋은 선택을 하는 방법입니다.
- 분할 정복: 문제를 나눌 수 없을 때까지 나누어서 각각을 해결한 후, 결과를 합쳐서 최종 결과를 얻는 방법입니다.
- 동적 계획법: 큰 문제를 작은 문제로 나누어 해결한 후, 작은 문제의 해답을 이용하여 큰 문제를 해결하는 방법입니다.
- 백트래킹: 해를 찾는 도중에 해가 될 가능성이 없는 경우, 그 경로를 포기하는 방법으로, 최적화 문제와 결정 문제를 해결할 수 있습니다.
- 분기 한정법: 해를 찾는 과정 중에 유망하지 않은 경우를 찾아서 제외하는 방법으로, 백트래킹과 유사하지만 유망성을 검사하는 절차가 추가됩니다.
- 비트 마스크: 이진수 표현을 자료구조로 쓰는 기법으로, 집합을 배열로 나타내는 방법입니다.
- 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법입니다.
- 최단 경로 알고리즘: 그래프에서 두 정점 사이의 경로의 길이가 최소가 되는 경로를 찾는 방법으로, 다익스트라, 플로이드-와샬, 벨만-포드 등의 알고리즘이 있습니다.
- 그리디 알고리즘: 각 단계에서 최적의 선택을 하는 방법으로, 탐욕 알고리즘과 유사하지만 최종 결과를 보장하지는 않습니다.
- 배낭 알고리즘: 배낭에 담을 수 있는 무게의 최댓값이 정해져 있을 때, 가치의 합이 최대가 되도록 물건을 넣는 방법으로, 동적 계획법을 활용합니다.
- 이분 탐색: 정렬된 배열에서 특정한 값의 위치를 찾는 방법으로, 시간 복잡도는 O(log n)입니다.
- 그래프 이론: 정점과 간선으로 이루어진 자료구조로, 최단 경로, 최소 신장 트리, 위상 정렬 등 다양한 문제를 해결할 수 있습니다.
- 트리 이론: 계층적인 구조로 데이터를 저장하는 자료구조로, 이진 트리, 이진 탐색 트리, AVL 트리, 힙 등 다양한 종류가 있습니다.
- 정수론: 정수와 정수 사이의 관계를 다루는 수학의 한 분야로, 최대 공약수, 소수, 소인수 분해 등을 다룹니다.