자료구조와 알고리즘
1. 자료구조
: 데이터를 구성하고 저장하는 방식이나 조직화된 형태를 말합니다 효율적인 데이터 관리와 처리를 위해 사용되며, 다양한 작업을 수행하기 위한 연산이나 알고리즘을 적용하기 위한 기반을 제공합니다.
배열 (Array)
:데이터를 일렬로 저장하는 자료구조로, 인덱스를 사용하여 데이터에 접근할 수 있습니다. (검색, 삽입, 삭제 등의 연산을 수행할 때 사용될 수 있다.)
연결 리스트 (Linked List)
:각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다
- 각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값으로 가진다)
- 해시테이블에서 서로 다른 키가 동일한 인덱스로 매핑될 수 있는 충돌을 해결하는 방법 중 하나=> 충돌이 발생한 인덱스에 연결 리스트를 생성하고, 충돌하는 키와 값을 해당 연결 리스트에 추가하는 방식
참고: https://ybworld.tistory.com/85
스택 (Stack)
:후입선출 (LIFO, Last-In, First-Out)의 특성을 가지고 있습니다. 데이터의 삽입과 삭제가 스택의 한쪽 끝에서만(가장 최근에 삽입된 쪽) 이루어집니다
큐 (Queue)
:선입선출 (FIFO, First-In, First-Out)의 특성을 가지고 있습니다. 데이터의 삽입은 큐의 한쪽 끝에서 이루어지고, 삭제는 다른 한쪽 끝에서 이루어집니다(너비 우선 탐색 (BFS, Breadth-First Search) 등에서 사용)
트리 (Tree)
: 계층적인 관계를 나타내기 위해 사용됩니다. 대표적으로 이진트리, 이진 탐색 트리, AVL트리 등이 있습니다
그래프 (Graph)
: 노드와 간선으로 이루어진 자료구조로 다양한 관계를 표현할 수 있습니다. 방향 그래프와 무방향 그래프, 가중치 그래프 등 다양한 종류가 있습니다
해시 테이블 (Hash Table)
:키와 값으로 이루어진 데이터를 저장하는 자료구조로, 키를 해시 함수를 통해 해시값으로 변환한 뒤, 해당 해시값에 해당하는 버킷에 데이터를 저장하고 검색하는 방식으로 동작합니다. 빠른 검색과 삽입을 필요로 하는 경우에 사용될 수 있습니다.
힙 (Heap)
: 최댓값이나 최솟값을 빠르게 찾기 위한 완전 이진 트리입니다. 보통 우선순위 큐를 구현하는데 사용됩니다
* 완전이진트리: 노드들이 왼쪽부터 차례대로 채워진 이진트리, 마지막 레벨을 제외한 모든 레벨에서 노드가 가득 차 있고, 마지막 레벨에서는 왼쪽부터 순서대로 노드가 채워져 있는 특징
참고: https://hocheon.tistory.com/70
2. 알고리즘
: 문제를 해결하지 위해 정의된 일련의 규칙들의 집합입니다. 탐색 알고리즘, 정렬 알고리즘, 그래프 알고리즘, 동적 계획법, 탐욕 알고리즘, 분할 정복, 그리디 알고리즘 등이 있습니다
이진 탐색(Binary Search) /탐색 알고리즘
: 정렬된 배열이나 리스트에서 특정 값을 빠르게 찾는 알고리즘입니다. 탐색 범위를 반으로 나눠가며 탐색하는 특징을 가지고 있습니다
퀵정렬(Quick Sort) /정렬 알고리즘
: 평균적으로 빠른 속도를 가지는 정렬 알고리즘으로 분할 정복 방식을 사용합니다. 배열을 피벗(pivot)을 기준으로 분할하고 정렬하는 과정을 반복하여 정렬을 수행합니다.
*pivot: 선택된 원소
*분할 정복: 문제를 더 작은 부분 문제로 나누어 해결하는 알고리즘 설계 기법
참고: https://www.daleseo.com/sort-quick/
병합정렬(Merge Sort) /분할 정복
: 분할 정복 방식을 사용하는 안정적인 정렬 알고리즘으로, 배열을 반으로 나눈 뒤 각각의 재귀적으로 정렬하고 병합하여 정렬된 배열을 생성합니다
*재귀적: 함수가 자기 자신을 호출하는 것, 즉 함수 내에서 동일함 함수를 호출하여 작업을 수행하는 것
깊이 우선 탐색(DFS, Depth-First Search) /그래프 알고리즘
: 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로, 스택 또는 재귀 함수를 사용하여 구현합니다(미로 찾기, 그래프 탐색 등)
너비 우선 탐색((BFS, Breadth-First Search) /그래프 알고리즘
: 그래프에서 인접한 모든 노드를 먼저 탐색하는 알고리즘으로, 큐를 사용하여 구현합니다.(최단 경로, 네트워크 탐색 등)
그리디 알고리즘(Greedy Algorithms)
: 각 단계에서 가장 최선의 선택을 하고 알고리즘으로 지역적으로 최적인 선택들의 집합을 구하여 전역적으로 최적인 해를 찾습니다. 최적 부분 구조와 탐욕 선택 속성을 가집니다
*최적 부분 구조: 큰 문제를 작은 부분 문제로 분할하여 해결할 때 작은 부분 문제의 최적해를 조합하여 전체 문제의 최적해를 구할 수 있는 경우
*탐욕 선택 속성: 각 단계에서 최적해를 선택하면 이를 결합하여 전체적인 최적해를 얻을 수 있는 경우
