c0smicb0y

백트래킹정의 : 여러 해들 중에 조건에 맞는 모든 해를 찾는 알고리즘. 알고리즘1. 후보 해를 선택한다.2. 조건에 따라 후보 해에 적절성 검사를 시행한다. 통과하지 못하면 지금 현재 선택한 후보 해를 버리고 1로 돌아가 후보 해를 다시 선택한다.3. 적설성 검사가 통과한 경우 이 후보 해가 문제의 해가 되는지 검사한다. 검사를 통과하면 이것이 문제의 해이고, 검사를 통과하지 못하면 1로 돌아가 후보 해를 계속해서 선택한다. 백트래킹의 활용1. 미로 탈출로 찾기재귀함수를 통해 백트래킹으로 미로 탈출로를 찾아보자. 알고리즘1. 시작점을 현재 위치로 지정하고, 이동방향을 북으로 설정한다.2. 현재 위치에서 가고자 하는 이동 방향으로 이동이 가능한지 확인한다. 벽과 이미 지나온 길은 이동가능한 길이 아니다.3..

탐욕 알고리즘정의 : 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘 동적 계획법과 마찬가지로 최적화 문제를 푸는데 사용한다.근시안적으로 해를 구할 당시에 가장 최적인 해를 구한다.탐욕 알고리즘은 동적 계획법보다 효율적이긴 하지만 동적 계획법처럼 반드시 최적의 해를 구해준다는 보장을 하지 못한다. 알고리즘1. 해 선택 (Selection Procedure) : 지금 당시에 가장 최적인 해를 구한뒤, 이를 부분해 집합에 추가한다.2. 적절성 검사 (Feasibility Check) : 새로운 부분해 집합이 적절한지 검사한다.3. 해 검사 (Solution Check) : 새로운 부분해 집합이 문제의 해가 되는지 검사한다. 아직 문제의 해가 완성되지 않았다면 1번부터 다시 시작한다. ..

동적 계획법 정의 : 어떤 문제가 반복적이고 최적 하위구조로 이루어질때, 하위구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법 최적 하위구조(Optimal Substructure)란 전체 문제의 답이 부분 문제의 답으로부터 만들어지는 구조를 말한다. 예를 들어 어떤 문제를 7개의 하위문제로 나눌 수 있을때, 7개의 하위문제의 답을 모두 얻어야 이 문제의 답을 구할 수 있다면 이 문제는 최적 하위구조를 갖추었다고 할 수 있다. 분할정복과 비슷해 보이지만, 분할정복은 문제를 큰부분에서 작은부분으로 나누는데반해(Top-Down), 동적 계획법은 제일 작은 부분부터 큰 문제로 풀어 올라간다(Bottom-Up). 또한 분할정복은 나눈 문제들을 완전히 새로운 하나의 독립된 새로운 문제로 보지만,..

분할정복 정의 : 분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다. 알고리즘을 설계하는 요령 (1) Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다. (2) Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다. (3) Combine : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다. 문제를 제대로 나누면 Conquer하는 것은 쉽기 때문에 Divide를 제대로 하는 것이 가장 중요하다.분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아내릴 수 있다. 분할정복의 응용 1. 병합 정렬 (Me..