[CS] 자료 구조와 알고리즘

기본 자료 구조

1. 배열 (Array)

   • 개념: 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료 구조.
   • 특징: 인덱스를 사용하여 요소에 접근할 수 있습니다. 접근 시간은 O(1).
   • 장점: 접근 속도가 빠르다.
   • 단점: 크기가 고정되어 있으며, 삽입/삭제가 비효율적.

2. 연결 리스트 (Linked List)

   • 개념: 각 요소가 노드로 구성되며, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함.
   • 종류: 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 환형 연결 리스트(Circular Linked List).
   • 장점: 크기가 가변적이며, 삽입/삭제가 용이.
   • 단점: 임의 접근 시간이 O(n).

3. 스택 (Stack)

   • 개념: LIFO(Last In, First Out) 원칙을 따르는 자료 구조.
   • 연산: push(삽입), pop(삭제), peek(가장 위 요소 확인).
   • 사용 사례: 함수 호출 스택, 연산자 우선순위 계산.

4. 큐 (Queue)

   • 개념: FIFO(First In, First Out) 원칙을 따르는 자료 구조입니다.
   • 연산: enqueue(삽입), dequeue(삭제), front(가장 앞 요소 확인).
   • 종류: 순차 큐, 원형 큐, 우선순위 큐.
   • 사용 사례: 작업 스케줄링, 프린터 대기열.

5. 해시 테이블 (Hash Table)

   • 개념: 키-값 쌍을 저장하는 자료 구조로, 해시 함수를 사용하여 키를 인덱스로 변환.
   • 연산: 삽입, 삭제, 검색 모두 평균 O(1)의 시간 복잡도를 가진다.
   • 충돌 해결 방법: 체이닝(Chaining), 개방 주소법(Open Addressing).
   • 사용 사례: 데이터베이스 인덱싱, 캐싱.

6. 트리 (Tree)

   • 개념: 계층 구조를 나타내는 자료 구조로, 노드와 간선으로 구성.
   • 종류: 이진 트리(Binary Tree), 이진 탐색 트리(BST), AVL 트리, 힙(Heap), 트라이(Trie).
   • 특징: 노드의 개수에 따라 깊이가 증가.
   • 사용 사례: 데이터베이스 인덱싱, 파일 시스템.

7. 그래프 (Graph)

   • 개념: 노드(정점)와 간선으로 구성된 자료 구조로, 네트워크 구조를 나타낸다.
   • 종류: 방향 그래프(Directed Graph), 무방향 그래프(Undirected Graph), 가중치 그래프(Weighted Graph).
   • 표현 방법: 인접 행렬(Adjacency Matrix), 인접 리스트(Adjacency List).
   • 사용 사례: 소셜 네트워크, 도로망, 웹 페이지 링크 구조.

알고리즘의 개념과 분석

알고리즘의 개념: 문제를 해결하기 위해 명확히 정의된 단계적인 절차 또는 방법.

시간 복잡도: 알고리즘이 실행되는 데 걸리는 시간을 입력 크기에 따라 분석.

• Big-O 표기법: 최악의 경우 성능을 나타내며, 예를 들어 O(n), O(log n), O(n^2) 등.

공간 복잡도: 알고리즘이 실행되는 데 필요한 메모리 공간을 입력 크기에 따라 분석.

• Big-O 표기법: 메모리 사용량을 나타냅니다.

정렬 알고리즘

1. 버블 정렬 (Bubble Sort)

   • 개념: 인접한 두 요소를 비교하여 필요시 교환하며, 이를 반복하여 정렬.
   • 시간 복잡도: O(n^2) (최악, 평균), O(n) (최선 - 이미 정렬된 경우).
   • 특징: 단순하지만 비효율적.

2. 삽입 정렬 (Insertion Sort)

   • 개념: 정렬된 부분과 정렬되지 않은 부분으로 나누어, 정렬되지 않은 요소를 적절한 위치에 삽입하여 정렬.
   • 시간 복잡도: O(n^2) (최악, 평균), O(n) (최선 - 이미 정렬된 경우).
   • 특징: 작은 데이터 집합에 효율적.

3. 퀵 정렬 (Quick Sort)

   • 개념: 피벗을 선택하고, 피벗을 기준으로 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 분할하여 정렬.
   • 시간 복잡도: O(n^2) (최악 - 불균형 분할), O(n log n) (평균, 최선).
   • 특징: 평균적으로 빠르며, 분할 정복 알고리즘.

4. 합병 정렬 (Merge Sort)

   • 개념: 배열을 반으로 나누고, 각각을 재귀적으로 정렬한 후 병합.
   • 시간 복잡도: O(n log n) (최악, 평균, 최선).
   • 특징: 안정 정렬이며, 추가적인 메모리 공간이 필요.

탐색 알고리즘

1. 이진 탐색 (Binary Search)

   • 개념: 정렬된 배열에서 중간 요소를 기준으로 비교하여, 탐색 범위를 반씩 줄이며 탐색.
   • 시간 복잡도: O(log n).
   • 특징: 데이터가 정렬되어 있어야 하며, 효율적.

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

   • 개념: 그래프에서 한 노드의 모든 자식 노드를 방문한 후, 다음 형제 노드를 방문하는 방식.
   • 시간 복잡도: O(V + E) (V: 정점 수, E: 간선 수).
   • 특징: 재귀적으로 구현하거나 스택을 사용하여 구현할 수 있다.

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

   • 개념: 그래프에서 한 노드의 모든 자식 노드를 먼저 방문한 후, 자식 노드의 자식 노드를 방문하는 방식.
   • 시간 복잡도: O(V + E) (V: 정점 수, E: 간선 수).
   • 특징: 큐를 사용하여 구현하며, 최단 경로 탐색에 유용.