반응형
알고리즘 4주차 - Dynamic Programming

기술개발/Algorithm 2021. 2. 10. 16:26

Dynamic Programming(동적 계획법) 피보나치 수열 - DP를 공부하기 전 몸풀기 📖 수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. [위키백과] Fibo(4) = Fibo(3) + Fibo(2) = 2 + 1 = 3 Fibo(5) = Fibo(4) + Fibo(3) = 3 + 2 = 5 Fibo(6) = Fibo(5) + Fibo(4) = 5 + 3 = 8 ..... Fibo(n) = Fibo(n - 1) + Fibo(n-2) 비슷한 구조가 반복되니 재귀 로 문제를 풀 수 있을 것이다. # 코드 스니펫 input = 20 def fibo..

알고리즘 4주차 - 개요(트리, 힙, 그래프, BFS, DFS, 동적계획법)

기술개발/Algorithm 2021. 2. 2. 23:05

4주차에 배우는 것 트리, 힙의 개념과 활용법 그래프, BFS, DFS Dynamic Programming의 개념과 필요성 트리 & 힙 트리를 이용하면 계층 구조의 데이터를 쉽게 표현 가능 힙을 이용하면 최댓값, 최솟값을 쉽게 뽑을 수 있음 BFS & DFS BFS(Breadth First Search): 너비 우선 탐색, 모든 것들을 하나씩 방문해야지만 다음 것을 봄 DFS(Depth First Search): 깊이 우선 탐색, 깊이로 내려가며 방문 각 탐색의 장단점 알기 Dynamic Programming 동적 계획법 부분 문제의 해를 통해 전체 문제를 해결하는 방법 DP라고도 하며 알고리즘 문제를 해결하는데 매우 많이 사용되는 편

반응형