Algorithm Strategy
2019. 03. 28 (Thur)
알고리즘 분류에 따라 다양한 방법을 고려할 것
코드를 그대로 그려보며 시뮬레이션 해보기
라이브러리에 의존하지 말고, 로직을 파악한 후 직접 논리를 구현 할것
분석 != 디자인 != 코딩
- 서로를 구분하여 진행
1. 완전 탐색(Brute Force)
Greedy를 완전탐색 탐색 여부를 결정짓는데 사용 가능
가지치기: 체계적으로 탐색 공간을 줄이기
해법으로 생각할 수 있는 모든 경우의 수를 확인
경우의 수가 상대적으로 작을 때 유리
순열로 모든 경우의 수를 생각
구현 : 중첩된 for문, 백 트래킹(재귀)
일단 정확한 답을 구하는 것 부터 생각
2. 그리디 알고리즘(Greedy Algorithm)
최적의 해를 구하는데 사용되는 근시안적인 방법
- TSP : 순열접근
여러 시점에서 결정할 때 마다, 그 순간 최적이라고 생각하는 것을 선택해 해답을 도출
그리디로 풀어도 괜찮다는 검증이 있어야함
- 검증없이 사용하는 것은 굉장히 위험함
많은 부분을 탐욕 알고리즘으로 풀고 나머지 부분을 푼다
동전 거스름돈
[5000, 1000, 500, 100, 50, 10] 중 최소 갯수로 거스름돈 주기
- 1700을 거스른다
1. 5000원 선택 - X
2. 1000원 선택 - O
- 실행 가능? - O
- 전체 해? - O
3. 1000원 다시 선택
- 실행 가능? - X
4. 500원 선택 - O
- 실행 가능? - O
- 전체 해? - X
5. 500원 다시 선택 - X
- 실행 가능? - X
6. 100원 선택
7. 100원 다시 선택
[1, 4, 5]
- 8을 거스른다
답이 맞지 않는다
=> 중복 순열(조합) 완전 검색으로 푼다
- 선택할 필요가 없는 가능성을 가지치기 한다.
- 최소 갯수(짧은 거리)니까 depth가 가장 낮은 것을 찾는다. : BFS
2. 동적 계획법(Dynamic Programming)
풀면서 항상 생각: 꼭 계산한 걸 반복해서 계산할 필요가 있을까?
Do Not Recompute! 계산한 것을 또 계산할 필요가 없다
재귀는 반복으로 할 수 있고, 반복도 재귀로 할 수 있다
완전검색을 완전히 할 줄 안다 하면 DP를 생각
최종 위치가 있으면 그 하부의 sub 집합이 존재
재귀 방법: 하나의 계산에 대해 하부의 집합에서 결과를 가져와 사용한다!
반복문 방법: 재귀와 반복문은 호환되니, 앞에서 부터 채워가자!
완전 탐색 => 가지치기 => 재귀 DP => 반복문 DP로 넘어가는 논리가 보여야 한다
결국에는 점화식이 중요
3. 시뮬레이션 문제
꼼꼼하게 모든 경우를 제어하기