Algorithm_Baekjoon

백준 알고리즘

https://velog.io/@pppp0722/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%AC%B8%EC%A0%9C-%EC%9C%A0%ED%98%95-%EC%A0%95%EB%A6%AC

자료구조 정리

해시 테이블

- key-value 쌍
- 시간초과가 날 경우 해시 자료구조 사용을 고려

힙, 우선순위 큐

- 우선순위를 고려하는 문제에서 사용
- ex) Dijkstra

스택, 큐

- 선입선출, 후입선출
- 그래프, 트리 문제에서 주로 사용
- 스택 - dfs
- 큐 - bfs

알고리즘 정리

브루트포스(완전탐색)

DFS, BFS, 백트래킹

- 모든 경우를 탐색해야 할 경우에 사용
- 무작정 모든 경우를 탐색하면 시간초과 날 수도 있음
- 탐색을 최소한으로 하도록 만들어야함

다이나믹 프로그래밍

- 조금씩 점차적으로 풀이하는 유형, 점화식을 떠올리면 쉬움
- bottom-up 접근, memoization

그리디

부분적인 최적해가 전체적인 최적해가 되는 문제에서 사용
- Priority Queue 활용하는 경우 많음
- 정렬
- 배낭 문제

이분탐색

- 순차적인 배열 탐색으로는 시간초과가 나는 문제에서 사용
- 시간복잡도 O(logN)로 그냥 순회하는 O(N)보다 빠르다.

트리

그래프

- 최단경로 구하는 문제
  - Dijkstra
  - Bellman-ford
  - BFS
  - 플로이드-워셜
- DFS
- BFS
- 위상정렬
- Minimum Spanning Tree
    - Kruskal - union find

union find

- 노드를 집합에 속하게 하는 Union 연산과 
  노드의 루트 노드를 찾는 Find 연산으로 이루어진다.

Minimum Spanning Tree

- Kruskal - union find
- Prim

투포인터, 슬라이딩 윈도우

- 배열에서 인덱스 2개를 사용해야 할 때 for문 2번하면 시간초과
  인덱스 2개를 while문 한번으로 사용하면서 문제 해결
- 구간합

string