이 포스팅은 알고리즘 노트 시리즈 2 편 중 2 번째 글 입니다.

  • Part 1 - 01: Python 알고리즘 팁 정리
  • Part 2 - This Post
▼ 목록 보기

자료구조 특징 및 사용처

Stack

Queue

Deque

Heap

Trie

Linked List

해야되는 알고리즘 정리

개념 정리

  • 그래프 용어 정리
    • V, E
    • 경로
    • 연결 그래프
    • 부분 그래프
    • 가중치 포함 그래프
    • 순환 경로
    • 순환 그래프, 비순환 그래프
    • 트리 - 비순환적, 비방향성 그래프 (그냥 순환 없이 연결된 것)
      • 트리 방문 방법
        • Preorder
          • 자신
          • 좌측
          • 우측
        • inorder
          • 좌측
          • 자신
          • 우측
        • postorder
          • 좌측
          • 우측
          • 자신
    • Rooted Tree - 한 정점이 뿌리로 지정된 트리
    • 신장 트리 : 연결, 비방향성 그래프에서 순환 경로를 제거하면서 연결된 부분 그래프
    • 최소 신장 트리 : 신장 트리중 가중치가 최소가 되는 부분 그래프
    • 저장하는 방법
      • 인접 행렬
      • 인접 리스트

완전 탐색

  • BFS
  • DFS

정렬

  • 버블 정렬
  • 삽입 정렬
  • 병합 정렬
  • 퀵 정렬
  • 순환 정렬

분할 정복

  • 이분 탐색
    • Upper Bound
    • Lower Bound
    • 값 제안

동적계획법

  • 플루이드 워셜 알고리즘

그리디

  • 다익스트라
  • Union Find
  • 최소 스패닝 트리

백트래킹

  • 트리 탐색 방법
  • n queen

정규표현식