알고리즘2 다이나믹 프로그래밍(DP)이란 무엇일까 ? Dynamic Programming (동적 계획법)이란 ?동적계획법(다이나믹 프로그래밍) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간을 내어 풀 때 사용한다. 예를 들어 코딩 테스트 문제를 풀다 보면 아래와 같은 제한사항이 종종 나오는데, 간혹 제한사항에 주어지는 숫자의 범위가 크고 경우의 수가 엄청난 값의 문제들이 대부분 DP를 이용해서 풀어야 하는 것이라고 알게 되었다. Dynamic Programming 알고리즘 조건 1) problem이 sub-problem으로 나누어 질 때2) 각 sub-problem의 solution을 통해 상위 problem의 솔루션을 구할 .. 2024. 6. 18. 깊이 우선 탐색(DFS, Depth-First Search) 이란? 깊이 우선 탐색(DFS, Depth-First Search)깊이 우선 탐색 (DFS)는 하나의 순환 알고리즘으로 백트래킹에 사용하는 대표적인 탐색 알고리즘이다. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 주로, 재귀함수 또는 Stack으로 구현할 수 있다. 깊이 우선 탐색의 구현1. 순환 호출 이용def dfs_recursive(graph, start, visited = []):## 데이터를 추가하는 명령어 / 재귀가 이루어짐 visited.append(start) for node in graph[start]: if node not in visited: dfs_recursive(.. 2024. 6. 12. 이전 1 다음
