자료구조와 알고리즘 중에서 자주 사용되는 것들은 어떤 것이 있나요?
1. 한마디 정리
스택/큐, 해시 테이블, 트리, 그래프, 정렬, 탐색 등이 있겠습니다.
2. 내가 생각한 꼬리질문
1) 스택(Stack)
후입선출(LIFO) 구조로 데이터를 저장하는 자료구조입니다.
새로운 데이터는 항상 스택의 맨 위에 쌓이며,
가장 최근에 추가된 데이터가 가장 먼저 제거됩니다.
2) 큐(Queue)
선입선출(FIFO) 구조로 데이터를 저장하는 자료구조입니다.
새로운 데이터는 항상 큐의 뒤쪽에 추가되고,
가장 오래된 데이터는 가장 앞쪽에서 제거됩니다.
3) 해시 테이블(Hash Table)
키-값(key-value) 쌍을 저장하는 자료구조입니다.
해시 함수를 사용하여 각 키를 고유한 인덱스로 매핑하고, 해당 인덱스에 값을 저장합니다.
해시 테이블은 매우 빠른 검색과 삽입을 지원합니다.
4) 이진 검색 트리(Binary Search Tree)
모든 노드에 대해
왼쪽 서브트리의 키는 부모 노드의 키보다 작고,
오른쪽 서브트리의 키는 부모 노드의 키보다 큰 이진 트리입니다.
이진 검색 트리는 효율적인 검색, 삽입, 삭제를 지원합니다.
5) 힙(Heap)
완전 이진 트리 형태의 자료구조로,
최대 힙(Max Heap)과 최소 힙(Min Heap)이 있습니다.
최대 힙은 부모 노드가 자식 노드보다 큰 값을 가지며,
최소 힙은 부모 노드가 자식 노드보다 작은 값을 가집니다.
힙은 우선순위 큐 등 다양한 알고리즘에서 사용됩니다.
6) 검색(Search)
자료구조에서 특정 요소를 찾는 작업을 의미합니다.
검색 알고리즘은 주어진 데이터 요소 집합에서 원하는 값을 찾는 데 사용됩니다.
7) 삽입(Insertion)
자료구조에 새로운 요소를 추가하는 작업을 의미합니다.
삽입 알고리즘은 자료구조의 크기를 동적으로 확장하는 데 사용됩니다.
8) 삭제(Deletion)
자료구조에서 특정 요소를 제거하는 작업을 의미합니다.
삭제 알고리즘은 자료구조의 크기를 동적으로 축소하는 데 사용됩니다.
9) 정렬(Sorting)
데이터를 특정 기준에 따라 순서대로 정렬하는 작업을 의미합니다.
정렬 알고리즘은 대부분의 컴퓨터 과학 애플리케이션에서 사용되며, 데이터 검색 및 분석을 용이하게 합니다.
10) 재귀(Recursion)
함수가 자신을 호출하는 것을 의미합니다.
재귀는 알고리즘의 간결성과 가독성을 높이는 데 사용됩니다.
11) 분할 정복(Divide and Conquer)
큰 문제를 작은 문제로 분할하여 해결하는 방법을 의미합니다.
분할 정복 알고리즘은 병합 정렬(Merge Sort) 및 퀵 정렬(Quick Sort)과 같은 정렬 알고리즘에서 사용됩니다.
12) 동적 프로그래밍(Dynamic Programming)
큰 문제를 작은 문제로 나누어 해결하는 방법을 사용하여 최적화 문제를 해결하는 알고리즘입니다.
동적 프로그래밍 알고리즘은 최단 경로 찾기, 배낭 문제 등에 사용됩니다.
13) 그래프(Graph)
노드(Node)와 간선(Edge)으로 이루어진 자료구조입니다.
그래프는 다양한 문제를 해결하는 데 사용됩니다.
그래프 탐색 알고리즘 중 DFS(Depth-First Search)와 BFS(Breadth-First Search)가 자주 사용됩니다.
14) 탐색 알고리즘
탐색 알고리즘은 주어진 데이터에서 원하는 값을 찾아내는 알고리즘입니다. 이를 위해서는 데이터의 구성 형태나 크기, 탐색 대상의 종류 등에 따라 적합한 알고리즘을 선택해야 합니다.
탐색 알고리즘에는 다음과 같은 알고리즘이 있습니다.
1. 선형 탐색(Linear Search)
데이터를 앞에서부터 차례대로 비교하면서 값을 찾아내는 방법입니다. 시간 복잡도는 O(n)입니다.
2. 이진 탐색(Binary Search)
데이터를 정렬된 상태로 유지하고, 중간 값과 비교하면서 값을 찾아내는 방법입니다. 시간 복잡도는 O(log n)입니다.
3. 해시 탐색(Hash Search)
해시 함수를 이용하여 특정 값을 찾아내는 방법입니다. 시간 복잡도는 O(1)입니다.
4. 깊이 우선 탐색(Depth First Search, DFS)
그래프에서 한 노드에서 시작하여 최대한 깊게 탐색하는 방법입니다.
5. 너비 우선 탐색(Breadth First Search, BFS)
그래프에서 한 노드에서 시작하여 인접한 모든 노드를 먼저 탐색하는 방법입니다.
6. A* 알고리즘(A* Algorithm)
최단 경로를 찾는 문제에서 사용하는 알고리즘으로, 효율적인 탐색을 위해 휴리스틱 함수를 이용합니다.
7. 이동 통로 문제(Moving Target Problem)
이동하는 대상이 있을 때, 대상의 위치가 바뀔 때마다 새로운 경로를 찾는 문제입니다.
위 알고리즘 외에도 다양한 탐색 알고리즘이 있으며, 이를 적절하게 사용하여 원하는 값을 빠르게 찾아내는 것이 중요합니다.
3. 스터디원 꼬리질문