알고리즘14 동적 계획법(다이나믹 프로그래밍, DynamicProgramming), 다른 알고리즘들과의 비교 재귀함수와 비교해 함께 공부하면 좋다. 동적 계획법의 정의 큰 문제를 작은 문제로 나누어 푸는 문제를 말한다. → 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 동적 계획법 사용 조건 DP는 항상 사용할 수 없기에 아래 사용 조건을 만족할 때 사용한다. 1. 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결 할 수 있다. → 최적 부분 구조(Optimal substructure) 2. 동일한 작은 문제를 반복적으로 해결한다. → 중복되는 부분 문제(Overlapping subproblem) Memoization 기법 이전에 풀었던 문제의 정답이나 결과 값을 저장하여, 이후의 문제를 풀 때 다시 계산하지 않고, 미리 계산된 값을 불러와서 문제를 해결하는 방법이다. →.. 2023. 4. 11. 재귀함수(Recursion) 동적 계획법(DP)와 비교해 함께 공부하면 좋다. 재귀함수의 정의 함수 안에 자신의 함수를 다시 호출하는 함수를 의미한다. 재귀함수는 자신의 로직을 내부적으로 반복하다가, 일정한 조건이 만족되면 함수를 이탈하여 결과를 도출한다. ➕분할 정복(Divide and Conquer) 방식의 하나로 재귀함수를 활용한다. 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘을 분할 정복 알고리즘이라고 한다. 재귀함수를 활용해 Top-Down(하향식 접근)해결 방식을 사용하는 특징이 있다. 재귀함수를 구현하는 두가지 방법 1. 재귀함수를 호출하는 부분을 상단에 두고 표현할 수 있다. # if문에서 보이는 것과 같이 일정한 조건을 만족하지 않으면 # 계속해서 자기 자신의 함수로 .. 2023. 4. 11. 백트래킹(BackTracking)의 개념과 DFS와의 차이 백트래킹(BackTracking)의 정의 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색한다. 해가 아니거나 다시 돌아가서(=back) 최적의 해를 찾는다. 백트래킹의 구현 보통 백트래킹의 구현은 BFS와 DFS와 함께 구현한다. 재귀로 보통 구현되고, 재귀 함수가 호출되고 조건에 맞지 않으면 종료되고 그전에 호출된 재귀로 돌아오므로, 백트래킹에서 말하는 ‘가능성이 없으면 후보를 포기해 정답을 찾아가는’ 방식이다. 안되는 조건은 없애면서 탐색하기 때문에 시간복잡도가 선형적으로 증가할 법한 문제에서 백트래킹을 적용하면 시간복잡도를 줄일 수 있다. 모든 경우의 수에서 한정 조건을 만족하는 경우를 탐색하는 것이기 때문에 완전 탐색 기법인 BFS와 DFS가 모두 구현이 가능하다. 하지만 한정 조건에 부합.. 2023. 4. 11. 그래프(Graph)의 탐색 👉 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 깊이 우선 탐색(DFS, Depth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다. 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다. →너비 우선 탐색보다 좀 더 간단하다. ➕참고 스택(Stack) 자료구조를 이해 해야 힌다. DFS 동작 과정과 구현 [탐색 방법] 탐색 시작 노드를 스택에 삽입하고 방문처리 한다. (재방문 방지를 위함) 스택 최상단 노드에 방문하지 않은 인접노드가 있다면 그 노드를 스택에 넣고 방문처리 한다. 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다. 방문하지 않은 노드가 없을 때 까지 반복한다. [동.. 2023. 4. 11. 이전 1 2 3 4 다음
