자료구조 및 알고리즘에 대해서 뚜렷하지 않던 것을 머리속에서 꺼내서 정리해보고자 한다.

시간 복잡도 & 공간복잡도

• 시간복잡도란 해당 코드가 실행되는데 걸리는 시간
• 공간복잡도란 해당 코드가 실행되는데 필요한 메모리 양이다.

Data Structures

정의 : 데이터를 어떻게 저장 및 조직하고, 그 위에서 어떤 연산을 제공할지 정한 것

why?? : 데이터를 어떻게 저장 및 연결 할지를 정의해 탐색, 삽입, 삭제 등 연산 복잡도를 목표 성능으로 달성하게 하기 위함

• 배열
• 연결리스트
• 스택
• 큐
• deque
• hashmap
• heap
• tree
• graph

Algorithms

정의 : 문제를 풀기 위해 입력을 출력으로 바꾸는 유한한 절차 & 규칙의 집합

why ?? : 입력을 출력으로 바꾸는 절차를 설계해 정확성을 보장하면서 시간 및 공간 비용을 최소화 하기 위함

기본

• 정렬
• 탐색
• 그리디
• 분할 정복
• 동적 계획법(DP)
• 백트래킹
• 슬라이딩 원도우
• 투 포인터

그래프

• BFS
• DFS
• 위상 정렬
• 최단 경로
• MST
• SCC

등등 더 존재한다.