일렉치는 취준생

DFS(Depth First Search) 깊이 우선 탐색 그래프로 표현된 모든 자료를 빠짐없이 탐색하는 알고리즘 stack과 재귀를 이용하여 구현 DFS 진행 과정 1. 시작 정점 v를 결정하여 방문 2. 정점 v에 인접한 정점 중에서 ( 1 ) 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push -> 정점 w에 방문 v = w로 바꾸고 다시 반복 ( 2 ) 방문하지 않은 정점이 X -> 탐색의 방향을 바꾸기 위해 스택을 pop -> 가장 마지막에 방문한 정점을 다시 v로 바꾸고 반복 v = stack.pop() 3. 스택이 공백이 될 때까지 2를 반복 DFS 예시 좌표 A B C D E F G visited F F F F F F F stack 1. A 출발 좌표 A B C D E F G vi..

DP(Dynamic Programing) 다이나믹 프로그래밍 문제를 각각 작은 문제로 나누어 해결한 후, 그 해를 이용해 큰 크기의 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결하는 방법 간단히 -> 작은거 부터 해결하고, 그 결과를 이용해 큰거 + 결과까지 다 해결한다 1. Bottom-Up ( 상향식 ) : 더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 품. -> 데이터를 테이블 형태로 만들면서 문제를 풀기 때문에 Tabulation이라고 부름 n = int(input()) dp = [0]*(n + 1) def fibo(n): dp[0] = 0 dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i..