-
사전 지식
C언어의 구조체, 포인터, 동적 할당, 재귀 호출, 지수와 로그 기초
자료구조와 알고리즘에서 우선적으로 C언어를 사용한다.
알고리즘을 짤 때 이 알고리즘이 효율적인지 계산하기 위해 지수와 로그가 필요하다. -
자료구조란?
- 데이터를 저장하는 방법 (모양)
- 데이터가 책이면 자료구조는 책장이다.
- 단순구조
➡️ 정수
➡️ 실수
➡️ 문자
➡️ 문자열 - 파일구조
➡️ 순차파일
➡️ 색인파일 - 선형구조
➡️ 스택(Stack)
➡️ 큐(Queue)
➡️ 리스트(List) - 비선형구조
➡️ 트리(Tree)
➡️ 그래프(Graph)
- 선형구조 : 데이터를 일렬로 연결
- 연결리스트 - 단일 연결리스트, 이중 연결 리스트 (배열의 단점을 극복하기 위해 나옴)
- 트리 - 이진 탐색 트리 (자식 노드의 최대 개수가 2개인 트리 구조)
- 그래프 - 방향, 접점을 가지는 구조 (지하철 노선도와 같은 모양)
-
알고리즘이란?
- 문제를 해결하는 방법
- 자료구조를 구현하려면 알고리즘이 필요함
-
알고리즘 종류
- 유클리드 알고리즘 - 두 수 사이의 최대공약수를 구하기
- 정렬 알고리즘 - 원소들을 정렬하기
- 탐색 알고리즘 - 원소 찾기
- DFS 알고리즘 - 깊이 우선 탐색 (이진 탐색 트리)
- BFS 알고리즘 - 너비 우선 탐색 (이진 탐색 트리)
- 그래프 알고리즘 - 그래프 구조에서의 삽입, 탐색
- 그외: 해시 알고리즘, 탐욕 알고리즘, 동적 계획법
