완전 탐색(brute-forse)과 Greedy algorithm

-반복과 재귀

 

 재귀

 -재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은문제의 해를 이용하는 방법

 - 함수 호출은 메모리 구조에서 스택을 사용함 ->재귀 호출은 반복적인 스택 호출을 의미하므로 메모리와 속도에서 성능 저하 발생함

 

*재귀가 반복보다 추가적인 메모리와 연산을 발생시킴

 

-완전탐색

완전 탐색의 경우 모든 경우의 수를 다 확인해야함

Ex)Tsp 문제에서 N=12이상이면 시간 복잡도가 폭발적으로 증가함

->재귀호출을 이용해서 tsp 완전탐색

-요소의 크기가 작을 때는 빠르게 답을 찾아낼 수 있음

 

-Greedy algorithm

문제 제시: 거스름돈을 줄때 지폐와 동전의 수를 최소화하기 

-최적해를 구하는데 사용되는 방법

-여러 경우중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 최종해에 도달

 ->여기서 그 순간 최적이라고 선택되는것은 local optimal 이지만 그것들을 수집해 최종해에 도달했다 해도 그것이 optimal이 아닐 수도 있음

 

ex) 거스름돈이 800원이라 치자

case1 -500,100,50,10원이면 500 -1 100-3

case2-500,400,100,50,10이라 치면 500-1,100-3하겠지만 이것은 최적이 아님 ->400 2개가 최적

 

//문제 제시 : Knapsack문제 

이건 알고리즘 시간에 지겹도록 했으니까 설명은 패스

- 0-1knapsack은 담거나 안 담거나 둘중 하나 정함

완전탐색의 경우 - 물건의 개수가 증가하면 시간복잡도 증가 => 2^n이니까 

greedy로 -1)값이 비싼것부터 채움 

              2)무게가 가벼운 것부터 채움

               3)kg당 값

  =>최적해 풀 수 없음

-물건을 쪼갤 수 있다하면 0-1이 아니면 최적해 찾을 수 있음

 

한번 baby-gin문제를 완전탐색이 아니라 greedy로 풀어봅시다

run은 하나씩 증가하는 경우 ex) 234

tri는 한 숫자가 3개 이상 등장 ex) 223423

 

1)먼저 입력(333234)이 들어오면 각 숫자가 몇번 나왔는지 count 

 3-4번 2-1번 4-1번

2)run조사 2-3-4 1번씩 나옴 =>run이니까 삭제

3만 3번 남음

3)tri조사 3만 3번 남음

=>baby gin

 //run을 먼저 조사할지 tri를 먼저 조사할지가 문제임 -예제에 따라 못 구할 수도 있음

  triple 먼저 해야하는듯

 

내일 이거 문제 풀어봐야지