분류 전체보기

조건 문제가 더 작은 문제로 쪼개질 수 있을 때 더 작은 문제의 solution으로 더 큰 문제의 solution을 구할 수 있을 때 : 최적 부분 구조 Optional substructure subproblem들이 겹칠 때 → memoization으로 줄일 수 있음. :중복되는 부분 문제 Overlapping subproblem 접근방법 approach/Technique top -down bottom - up 하향식 상향식 표현1 top-down bottom-up 표현2 memoization tobulation 가능한 에러 recur depth error 구현방식 recursion loop 특징1 직관적 비직관적 빠르기 비교적 느림 빠름 속도차이 이유 함수 호출이 많음 불필요한 함수 호출이 x memo..

Dijkstra 다익스트라 Floyd-Warshall 플로이드 워셜 어떤 문제에 사용할까? 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 노드/간선 갯수 적을 떄 사용 사용처 가중 그래프(weighted graph)에서 하나의 정점으로부터 시작하여 각각의 노드로 가는 각각의 최단경로를 찾는 데 효율적. 가중 그래프에서 정점간 모든 쌍 사이에서 가장 짧은 경로를 찾는데 적합함. (all-pairs shortest path algorithm) source - usecase a single-source shortest path algorithm a multi-source shortest path algorithm 정점 방문 방..

학습 자료 (레퍼런스) https://www.youtube.com/watch?v=xeSz3pROPS8 https://www.geeksforgeeks.org/topological-sorting/ 위상정렬 그래프 정점의 선형적 정렬(ordering)으로, vertex U에서 V로 가는 방향성이 유지된 채 정렬되는 것. 즉, U가 V를 가리킨다면(향한다면) 위상정렬 시 U는 언제나 V보다 먼저 등장해야 한다. 왜냐하면 U를 거쳐야 V를 갈 수 있기 떄문이다. 방향성이 있고 싸이클이 없는 그래프인 DAG(directed acycled graph) 에서만 가능하다. 선형 시간 복잡도를 보임 (O(V+E)) 결과물은 unique하지 않다. (레벨간의 순서 stable은 보장하지만, 결과물이 언제나 동일하지 않다.)..