자료구조(Data Structure)
- 데이터를 관리(CRUD)하는 방법, 알고리즘의 재료
리스트(List)
- 데이터를 줄 세워 관리하는 방법
- 배열 리스트(Array List) : 배열을 활용한 리스트
- 연결 리스트(Linked List) : 노드와 링크를 활용한 리스트
- 원형 연결 리스트(Circular Linked List) : 연결 리스트의 마지막 노드가 첫 노드를 참조해 원형을 이루는 연결 리스트
- 양방향 연결 리스트(Doubly Linked List) : 각 노드가 앞 뒤 노드 모두를 참조하고 있는 연결 리스트
스택(Stack)
- 데이터를 줄 세우고, 선입후출 방식으로 관리하는 방법
큐(Queue)
- 데이터를 줄 세우고, 선입후출 방식으로 관리하는 방법
힙(Heap)
- 큐에 우선순위 개념을 도입하여 데이터를 관리하는 방법
- 힙의 조건 :
- 완전 이진 트리
- 모든 노드는 값을 갖고, 항상 자식 노드보다 크거나(최대힙) 작아야(최소힙) 한다.
이진 트리(Binary Tree)
- 모든 노드가 2개 이하의 자식 노드를 갖는 트리
- 포화 이진 트리(Full Binary Tree) : 모든 노드가 정확히 2개의 자식 노드를 가지면서 꽉 채워진 트리, 노드의 개수가 2^n - 1개인 이진 트리
- 완전 이진 트리(Complete Binary Tree) : 마지막 층을 제외한 모든 층의 노드가 가득차고, 마지막 층의 좌측부터 차례대로 노드가 채워진 이진 트리
- 이진 검색 트리(Binary Search Tree) : 각 노드의 값이 유일하고, 임의의 노드의 값은 자신의 좌측 아래에 위치한 모든 노드의 값보다 크고, 자신의 우측 아래에 위치한 모든 노드의 값보다 작은 이진 트리
- 균형 검색 트리(Blanced Search Tree) : 이진 검색 트리의 좌우 높이 균형을 맞춘 트리
- AVL 트리(Adelson-Velskii Landis Tree)
- 레드-블랙 트리(Red-Black Tree)
- B트리
해쉬 테이블(Hash Table)
- 저장하려는 데이터의 값이 곧 저장될 위치가 되도록 데이터를 관리하는 방법
해쉬 함수(Hash Function)
- 데이터의 값을 받아 해쉬 테이블 상에 저장될 위치를 반환하는 함수
해쉬 테이블 충돌 해결
- 체이닝(Chaining) : 해쉬 테이블 상에서 같은 주소로 저장되려는 값을 모두 하나의 연결 리스트로 관리하는 방법
- 개방 주소 방법(Open Addressing) : 저장될 수 있는 공간을 찾을 때까지 계속 해쉬 테이블을 탐색하는 방법
그래프(Graph)
- 데이터들의 관계를 정점(Vertex)과 간선(Edge)로 표현한 자료구조
알고리즘(Algorithm)
- 입력을 받고 원하는 출력을 만들어 내서 문제를 해결하는 과정
재귀(Recursion)
- 자신과 똑같지만 크기가 다른 문제를 발견하고 이들 간의 관계를 통해 문제를 해결하는 방법
점근적 표기법
- 입력이 충분히 큰 경우의 복잡도인 점근적 복잡도를 이용하여 알고리즘의 시간 복잡도를 표기하는 방법
- O(Big O) 표기 : 증가율을 나타내는 함수의 최고 차항의 차수를 넘지 않는 모든 함수의 집합(최악의 상황, 점근적 상한)
- Θ(Seta) 표기 : 증가율을 나타내는 함수의 최고 차항의 차수와 동일한 함수의 집합
- Ω(Omega) 표기 : 증가율을 나타내는 함수의 최고 차항의 차수를 넘는 모든 함수의 집합(최선의 상황, 점근적 하한)
점화식
- 어떤 함수를 자신과 똑같은 함수를 이용해 나타내는 것, f(n) = n * f(n - 1)
기본 정렬 알고리즘
- 선택 정렬(Selection Sort) : 가장 큰 요소를 찾아 배열의 끝자리에 있는 요소와 자리를 바꾸는 작업을 반복하는 정렬
- 버블 정렬(Bubble Sort) : 인접한 두 요소를 비교하는 작업을 통해 가장 큰 요소를 배열의 끝자리로 보내는 작업을 반복하는 정렬
- 삽입 정렬(Insertion Sort) : 요소들을 정렬된 배열 속에 위치에 맞게 삽입하는 작업을 반복하는 정렬
고급 정렬 알고리즘
- 병합 정렬(Merge Sort) : 배열을 반으로 나누는 작업을 재귀적으로 반복한 뒤 정렬하여 다시 병합 하는 작업을 반복하는 정렬
- 퀵 정렬(Quick Sort) : 기준 요소보다 작은 요소를 좌측에, 큰 요소를 우측에 배치하는 과정을 재귀적으로 반복하는 정렬
- 힙 정렬(Heap Sort) : 힙의 조건을 만족하도록 배열을 만드는 정렬
동적 프로그래밍(Dynamic Programming)
- 큰 문제의 해답을 구하기 위해 작은 문제의 해답을 찾는 과정에서 중복 계산을 제거해 비효율을 줄이는 방법
- 탑다운(Top-down) 방식 : 큰 문제의 해답을 통해 작은 문제의 해답을 구하는 하향식 방법
- 바텁업(Bottom-up) 방식 : 작은 문제의 해답을 통해 큰 문제의 해답을 구하는 상향식 방법
최적 부분 구조(Optimal Substructure)
- 큰 문제의 해답에 그보다 작은 문제의 해답이 포함된 구조
메모하기(Memoization)
- 한 번 계산한 것을 메모해두어 다시 계산하지 않도록 하는 동적 프로그래밍 방법
그래프 탐색
- 너비 우선 탐색(BFS : Breadth-First Search) : 그래프에서 옆으로(너비를 기준으로) 모든 노드를 방문하는 방법
- 깊이 우선 탐색(DFS : Depth-First Search) : 그래프에서 아래로(깊이를 기준으로) 모든 노드를 방문하는 방법
그리디 알고리즘(Greedy Algorithm)
- 당장에 가장 좋아 보이는 선택을 반복해서 문제를 해결하는 알고리즘
백트래킹(Backtracking)
- 탐색을 하다가 더 나아갈 수 없으면 왔던 길로 되돌아가 다른 길을 찾는 알고리즘
브루트 포스 알고리즘(Brute Force Algorithm)
- 가능한 모든 경우의 수를 고려하여 문제를 해결하는 알고리즘
Leave a comment