공부/코테

알고리즘 스터디 이론 기록용

연숲 2023. 3. 23. 11:53

공부해야 할 것들 정리

  1. 시간복잡도와 공간복잡도
  2. 문자열
  3. 브루트 포스 알고리즘
  4. 그리디
  5. 구현
  6. DFS/BFS
  7. 정렬
  8. 이진탐색
  9. 다이나믹 프로그래밍
  10. 최단 경로
  11. 그래프 이론

 

1. 시간복잡도와 공간복잡도

시간복잡도를 표현하는 방법으로 빅오 표기법을 많이 사용한다.

코드내에서 가장 큰 연산이 큰 부분을 기준으로 시간복잡도를 계산하는 것이고

어떤 코드가 for문, 중첩 for문으로 이루어져있으면 시간복잡도는 O(n^2)이 되게 된다. 

알고리즘, 유형별 시간복잡도를 파악하고 있으면 문제를 풀기전에 알고리즘을 먼저 떠올리고 풀 수 있어서 좋다.

 

2.문자열

 

3, 브루트 포스 알고리즘

완전 탐색 알고리즘으로, 효율은 떨어지지만 간단한 것이 for, while을 이용한 순차탐색, 좀 더 복잡한 것이 dfs, bfs 등등