1. 정렬
- 리스트 어떤 식으로 정렬이 되는지 알고리즘적으로 분석을 하였다.
- 실 사용시 sort 함수를 이용하여 list 를 정렬 하면 됨
2. 스택, 큐, 해쉬
-
스택
- Stack 은 LIFO 방식으로 마지막으로 들어간 데이터가 나오는 형식이다.
- push(data) : 맨 앞에 데이터 넣기
pop() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기 - 삽입과 삭제에 효율화 되어 있어 linked list 로 나타내 주기 편리함.
- head.data 를 가지고 삽입/ 삭제를 하면 됨
-
큐
- Queue 는 FIFO 방식으로 처음 들어온 데이터가 처음 나가는 형식이다.
- 줄서 있을 때 처음 선 사람이 먼저 배식 받고 나가는 형식이다.
- enqueue(data) : 맨 뒤에 데이터 추가하기
dequeue() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기 - stack 과는 달리 tail 그러니까 가장 뒤의 데이터를 뽑아서 사용한다.
-
해쉬
- hash 는 key 를 이용해 데이터를 빠른 속도로 뽑아올 수 있다.
- 스택이나 큐처럼 데이터를 쭉 돌려 보지 않고 key 라는 키워드만 있으면 바로 뽑아올 수 있어서 효율 적이다.
하지만 공간복잡도가 커짐으로 시간복잡도를 위해 공간복잡도를 사용하는 꼴이다. - put(key, value) : key 에 value 저장하기
get(key) : key 에 해당하는 value 가져오기 - hash() 를 사용하면 임의의 값이 index에 적용이 되고 같은 수를 나눠줌으로 각자 데이터를 다른 index에 저장할 수 있다.
이 때, 수많은 데이터로 index가 겹치게 된다면 이 것을 "충돌" 이라고 표현 하는데 "체이닝(링크드리스트)" 방식이나 "개방주소법(배열의 다음곳에 넣는 방법) 을 사용한다.
3. 트리, 힙(Tree, Heap)
-
트리
-
트리는 비선형계층적 구조를 가지고 있다.
-
Node: 트리에서 데이터를 저장하는 기본 요소
Root Node: 트리 맨 위에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
Child Node: 어떤 노드의 하위 레벨에 연결된 노드
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
Sibling: 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level
-
이진트리
- 이진트리는 각 노드가 최대 2개의 노드를 가진다.
- 완전이진트리 : 이진트리이고, 왼쪽부터 데이터가 채워진다.
그렇게 때문에 배열로 표현이 가능하다!
-
-
힙
-
heap 은 최대, 최소값을 빠르게 구하기 위해 고안된 트리이다.
-
데이터를 추가할 시 제일 아래단, 즉 배열에 마지막에 추가하게 되고
그 윗 단의 데이터와 값의 크기를 비교하여 max heap 일 시 root로 큰 값이 가게 되고, min heap 일 시 최소값이 가게 된다.
-
-
DFS & BFS
- 위가 DFS, 아래가 BFS 설명이다.
- DFS 가장 깊숙히 들어가기 때문에 Stack 을 이용하여 표현이 가능하고
BFS 는 인접데이터를 비교하여 찾기 때문에 Queue 를 이용하여 표현이 가능하다.
- 위가 DFS, 아래가 BFS 설명이다.
4. 동적계획법(Dynamic programming)
- 피보나치 수열로 보는 동적계획법!
- 피보나치 수열은 재귀함수로 표현 가능!
하지만 그 사이 데이터 저장이 불가능!
- 피보나치 수열은 재귀함수로 표현 가능!
- 메모이제이션 : 문제를 쪼개 기록하며 결과를 기록하며 저장하는것!
- Top-down 법 : 높은 수에서 낮은수로 데이터를 구해 저장하는것! 100 > 99
- bottom up 법 : 낮은수에서 높은수로 데이트를 구해 저장하는것! 1 > 2
5. CPU 특강
안녕하시오.