elice2 탐욕적 알고리즘 탐욕 알고리즘그리디 알고리즘은 동적 프로그래밍 사용시 지나치게 많은 일을 한다는것에서 착안된 알고리즘 이다.각 단계에서 최선의 선택을 하는 기법이다.각단계에서 최선의 선택이 전체의 최선을 만든다는 가정하에 시작된다.동적 계획법보다 효율적이만 동적 계획법처럼 반드시 최적의 해를 구해준다는 보장은 없다.탐욕적 알고리즘은 동적 계획법보다 수행시간이 훨씬 빠르다.시간이나 공간적인 제약으로 인해 최적해를 찾기어려울경우, 근사해를 찾는 용도로 쓰인다.예시문제 가장 적은 수의 동전으로 해당 액수를 구성해주는것이 최적의 해이다. 우리는 140원의 거스름돈을 만들어 줘야한다.우리가 100원, 50원, 10원 동전을 여러개 가지고 있다는 가정하에 탐욕적알고리즘을 사용할 경우, 140원 보다 작으면서 후보 목록중에서 가장 .. 2018. 12. 24. 완전탐색 # **완전탐색** 문제를 해결하는 방법중 가장 기초 가능한 모든 경우를 시도해 보는것입니다. 문제가 주어지면 제일먼저 완전 탐색법으로 시도해보아야합니다. 가능한 모든 경우 = 탐색 공간 (search space) : 고려해야하는 모든 경우 완전 탐색법은 가능한 모든경우를 하나도 빠짐없이 모두 고려하기 때문에 틀릴 경우가 가장 적지만, 시간은 최대로 소요됩니다. 모든 가능성을 따져봐야 하기때문에 문제의 크기가 클수록 , 실행시간이 지수적으로 증가할수 있습니다. 대회에 참가하거나 아주 어려운 문제에 직면한 경우, 완전 탐색법을 적용하는것이 좋습니다. 실행시간 제한에 의해 실패할수 있지만, 정답 크기가 적은 경우에 부분점수를 획득할 수 있기때문입니다. 완전 탐색을 할 수있는 방법 1. brute force .. 2018. 12. 10. 이전 1 다음