공부/코테
알고리즘 스터디 이론 기록용
연숲
2023. 3. 23. 11:53
공부해야 할 것들 정리
- 시간복잡도와 공간복잡도
- 문자열
- 브루트 포스 알고리즘
- 그리디
- 구현
- DFS/BFS
- 정렬
- 이진탐색
- 다이나믹 프로그래밍
- 최단 경로
- 그래프 이론
1. 시간복잡도와 공간복잡도
시간복잡도를 표현하는 방법으로 빅오 표기법을 많이 사용한다.
코드내에서 가장 큰 연산이 큰 부분을 기준으로 시간복잡도를 계산하는 것이고
어떤 코드가 for문, 중첩 for문으로 이루어져있으면 시간복잡도는 O(n^2)이 되게 된다.
알고리즘, 유형별 시간복잡도를 파악하고 있으면 문제를 풀기전에 알고리즘을 먼저 떠올리고 풀 수 있어서 좋다.
2.문자열
3, 브루트 포스 알고리즘
완전 탐색 알고리즘으로, 효율은 떨어지지만 간단한 것이 for, while을 이용한 순차탐색, 좀 더 복잡한 것이 dfs, bfs 등등