[TIL] 2025-01-28 (알고리즘)

Today I Learned (2025-01-28)

---

목차

• Today I Learned (2025-01-28)
• 오늘 공부한 내용
  • 1. 알고리즘
• 어려웠던 내용
• 궁금한 내용과 부족한 내용
• 오늘 하루

---

오늘 공부한 내용

1. 알고리즘

• DFS, BFS, 백트래킹

  • 정리
  • 그래프는 node와 edge로 이루어져 있다.
  • 방향성과 순환성이 각각 있거나 없거나
    • 둘 다 없으면 트리
  • 수 많은 그래프/트리 종류와 알고리즘들이 존재한다.
  • 그래프를 코드로 구현할 때는 2가지 방법이 있다.
    • 인접행렬
      • edge 가 많은 그래프일 때 쓰는게 좋다.
      • edge 탐색이 빠르다.
    • 인접리스트
      • edge 가 적은 그래프일 때 쓰는게 좋다.
      • 메모리를 적게 쓴다.
  • DFS, BFS, 백트래킹은 전부 완전탐색 알고리즘
    • 최악의 경우 모든 노드를 탐색하는 건 동일
  • 최단거리를 구할 때는 BFS 사용
  • DFS는 재귀 (or 스택), BFS는 큐로 구현
  • 가지치기를 하면 백트래킹

• 이진탐색

  • 탐색 전에 반드시 정렬되어 있어야 한다.
  • 살펴보는 범위를 절반 씩 줄여가면서 답을 찾는다.
  • 정렬 O(NlogN) + 이진탐색 O(logN) -> 결과적으로 O(NlogN)
  • 미리 정렬되어 들어오면 이진탐색만 하면 되므로 O(logN)

---

어려웠던 내용

• 알고리즘들

---

궁금한 내용과 부족한 내용

• 알고리즘

---

오늘 하루

• 오늘도 알고리즘 데이