본문 바로가기

분류없음

이직 - 기술면접 대비

깊이우선탐색

 -> 백트래킹

넓이우선탐색




재귀와 동적 프로그래밍


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



해야 할것

정렬 및 탐색

이진 트리 ( 순차 .. )

정규표현식