[개념정리] 자료구조

`스택` : 
- 개념 : LIFO(Last in First out) 후입선출 구조로, 한쪽 끝에서만 삽입/삭제가 가능하다.
- 장점 : 최근 데이터에 빠르게 접근
- 단점 : 중간 데이터 접근이 어렵다 , 대규모 데이터셋 저장 공간 효율성 저하
- 시간복잡도 : 


`덱`
- 개념 : 파이썬으로 que 자료구조를 구현시 deque을 사용
- 장점 : 삽입, 삭제시 시간복잡도 O(1)
- 단점 : 인덱스 슬라이싱 불가

`백트래킹`
- 개념 : 유망하지 않은 경로를 조기에 차단하여 이전 단계로 돌아가는 효율적 알고리즘(가지치기, 대부분 재귀함수로 구현)
- 시간복잡도 : O(b^d), 각 노드의 분기수 * 최대 탐색 깊이 



`BFS` : 
- 개념 : 너비우선탐색으로 ,  que(FIFO : First In First Out 선입선출 구조)를 사용하여 풀 수 있다.
- 장점 : 최단 경로를 보장, 레벨 순서대로 탐색하므로 각 레벨에서 동시에 여러 경로를 탐색 가능
- 단점 : dfs에 비해 더 많은 메모리 사용 가능( 깊은 레벨에 있는 노드를 늦게 방문하여 목표 노드에 빨리 도달하지 못할 수 있음) 
- 시간복잡도 : 인접 리스트로 구현시, O(V+E), V는 노드 갯수, E는 간선 갯수

`DFS` : 
- 개념 : 깊이우선탐색으로,  한 방향으로 깊게 탐색하다가, 막히면 다시 돌아와서 다른 경로를 탐색 (stack 사용)
-  장점  :  bfs에 비해 더 적은 메모리 사용 가능
- 단점 : 얻어진 목표 노드까지의 경로가 최단 경로라는 보장이 없음
- 시간복잡도 : O(V+E)

`동적계획법`
- 개념 : 문제를 작은 하위 문제로 나누고, 하위 문제의 해결책을 저장해서 큰 문제를 해결하는 bottom-up 설계방식(주로 반복문 사용)
- 예시 : 피보나치 수열

`메모이제이션`
- 개념 : 계산 결과를 저장하고 재사용하는 최적화 기법(주로 재귀함수에서 사용)
- 장점 : 필요한 결과만 저장하므로 때에 따라 메모리 절약 가능
- 단점 : 


`재귀함수`