목록CS/알고리즘 (8)

영벨롭 개발 일지

[알고리즘]그래프 탐색하기: BFS & DFS

그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제를 그래프 순회 문제(graph traversal problem)이라고 합니다. 그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도로 사용될 수 있기 때문에 그래프 탐색 문제(graph search problem)이라고도 합니다. 그래프 탐색에서 아직 방문하지 않은 노드들 중 다음으로 살펴볼 노드들의 리스트를 open list, 방문한 노드들의 리스트를 closed list라고 말합니다. 그래프 탐색 알고리즘으로 너비 우선 탐색(BFS, Breadth-First Search)와 깊이 우선 탐색(DFS, Depth-First Search)가 있습니다. 너비 우선 탐색(BFS, Breadth-First Search) BFS는 탐색 과정에..
CS/알고리즘 2022. 2. 25. 20:31
[알고리즘]다이나믹 프로그래밍(Dynamic Programming, DP)

1. Dynamic Programming(동적 계획법)이란? 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘입니다. 2. DP의 원리, Memoization 동적 계획법의 원리는 처음 진행된 연산은 기록해 두고 이미 진행했던 연산이라면 기록한 값을 가져와 중복 계산을 줄이는 것입니다. 이것을 메모이제이션(Memoization)이라고 합니다. 3. DP의 조건 작은 문제가 반복될 경우 같은 문제에 대한 결과가 항상 같을 경우 4. DP 사용 예시: 피보나치 수열 DP가 사용되는 예시로 피보나치 수열을 들겠습니다. (1) 재귀호출을 이용한 풀이 //재귀호출을 통한 피보나치 수열 구하기 int fibonacci(int n){ if(n
CS/알고리즘 2022. 2. 23. 15:38
이전 Prev 1 2 Next 다음