깊이우선탐색
-> 백트래킹
넓이우선탐색
재귀와 동적 프로그래밍
ex) 피보나치 수열 구하기
1. 노가다 재귀로 구하기
fibo(n) = fibo(n-1)+fibo(n-2)
fibo(n-1) = fibo(n-2) + fibo(n-3)
fibo(n-2) = fibo(n-3) + fibo(n-4)
처럼 호출하게 되면 1+2+2^2+ ... + 2^n-1번 호출을 하게 된다. 그럼 결국 O(2^n) 시간이 걸린다.
우리가 궁금한건 n개의 fibo들인데...
2. 메모이제이션 ( 하향식 접근 )
이전에 구해둔 값을 배열에 저장해두자.
3. 상향식 접근
배열에 저장해둘 거 없이 fibo(0), fibo(1)부터 구해보자
ex) 0-1 배낭 문제
탐욕 알고리즘(Greedy Algorithm)
배열에 저장
https://www.hackerrank.com/challenges/greedy-florist/problem
다익스트라 알고리즘
ex) 도시 간의 최단 거리 구하기
크루스칼 알고리즘 ( 최소 신장 트리 )
m
신장 트리 : 모두 연결되어 있고 사이클이 없는 그래프
https://gist.github.com/developer-sdk/123570b5c2813fe9a25352c2fb9e0527
https://abcd1439.github.io/mst/
http://journee912.tistory.com/66
해야 할것
정렬 및 탐색
이진 트리 ( 순차 .. )
정규표현식