알고리즘3 [ 알고리즘 ] 분할 정복 알고리즘(Divide and conquer algorithm) 분할 정복 알고리즘이란? 등차수열의 공식과 연관지어 생각해본다! 분할 정복 알고리즘은 문제를 나눌 수 없을 때 까지 작게 나누어서(Divide) 각각을 해결하여 정복(Conquer)하는 알고리즘이다. -이처럼, 분할 정복은 하위 문제를 재귀적으로 해결하기 때문에 하위 문제 각각은 원래 문제보다 범위가 작아야 하며 하위 문제는 각 문제마다 탈출 조건이 존재해야 합니다. 분할정복 알고리즘 설계 요령 (1) Divide : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다.-> 이 과정이 가장 중요한 과정. (2) Conquer : 나누어진 하위 문제를 재귀적으로 해결한다. 즉 하위 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 탈출 조건으로 놓고 해결한다... 2021. 1. 18. [ 알고리즘 ] 동적 프로그래밍 =Dynamic Programming=동적계획법 동적 프로그래밍이란? 큰 문제를 여러 개의 하위 문제로 쪼개고, 이 하위 문제들을 먼저 해결한 후 이를 이용해서 더 큰 문제를 풀어나가는 방법이다. (=먼저 입력크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다) ▶ Bottom-up 방식 - 동적 프로그래밍은 각 하위 문제들이 서로 관계가 없을 때, 즉 서로 의존하지 않는 경우에만 쓸 수 있다. 동적 프로그래밍이 필요한 이유(배경) 예를들어 피보나치 수열을 보자. 피보나치 문제를 풀 때 재귀적 방법(Recursion)과 Dynamic Programming 방법이 있다. 재귀적 방법 def fi.. 2021. 1. 11. [ 알고리즘 ] DFS와 BFS DFS(Depth First Search, 깊이 우선 탐색)란? 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법으로 스택 또는 재귀 호출을 이용한다. 1. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사함 2. 즉 넓게(wide) 탐색하기 전에 깊게(deep) 탐색함 3. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함 4. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 5. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림 DFS의 과정 DFS의 시간 복잡.. 2021. 1. 4. 이전 1 다음
