1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programming7. Backtracking8. Branch and Bound여기서는 Decrease and conquer에 대해 다룬다.Decrease and Conquer란주어진 문제를 같지만 계산을 작게 만들어서 해결하는 방식이다. 분할정복과의 차이는, 분할정복은 작게 쪼갠 후 다시 통합하는 과정이 있지만, Decrease는 작게 쪼개서 없애버린 부분을 다시 합치지 않는다는 차이가 있다. 그래서 여기서는 '통합' 대신 '확장'이라는 말을 쓴다. Greedy나 DP처럼 특정 알고리즘이라기보다는 정의역을 ..
전공
여기서는 8가지 알고리즘 중 Divide and conquer에 대해 다룬다. 1. Brute force 2. Divide and conquer 3. Decrease and conquer 4. Transform and conquer 5. Greedy Method 6. Dynamic Programming 7. Backtracking 8. Branch and Bound Divide and conquer란분할 정복이라 불리는 알고리즘이다. 주어진 문제의 입력을 분할하여 최소 단위로 나눈다. 그리고 이렇게 최소단위로 나눈 부분문제에 대한 부분해를 구하고, 이를 취합한다. 총 3가지 분할 -> 정복 -> 통합 3가지의 과정을 거치는 것이다. 이렇게 큰 문제를 작은 문제로 쪼개어 접근하는 방식을 하향식 top-do..
앞으로 예제와 함께 알고리즘 수업에서 배운 내용들을 요약하여 올릴 것이다.총 올릴 알고리즘 분류는 아래 8가지이다.1. Brute force 2. Divide and conquer 3. Decrease and conquer 4. Transform and conquer 5. Greedy Method 6. Dynamic Programming 7. Backtracking 8. Branch and Bound여기서는 Brute Force에 대해 다룬다.Brute Force란될 때까지 다 해본다는 알고리즘이다. 문제 해결을 위해 모든 경우의 수를 찾을 때까지 반복하는 방법이다. 실패하는 경우는 없으나 컴퓨팅 자원이 다른 알고리즘에 비해서 심각하게 낭비된다. 가장 단순하고 직관적이다. Brute Force 예시Sel..
