Brute force & Greedy
2019. 03. 25 (Mon)
I. 반복과 재귀
반복과 재귀는 유사한 작업을 수행할 수 있다.
반복: 수행하는 작업이 완료될 때까지 반복
재귀: 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용
프로그램 구조
순차
선택
반복
반복 구조
초기화
조건검사
실행
업데이트
재귀적 알고리즘
기본 경우(base case): 더 내려가지 않는 부분. 마지막 부분
유도된 경우(inductive case): 내려가는 부분. 중간 과정 부분
반복보다 간결하고 이해하기 쉽다
메모리 구조에서 스택을 사용하기 때문에, 메모리 및 속도 성능저하가 발생
II. 완전검색
케이스를 물어보는 문제에 대해 적용
모든 케이스를 검사
- 이후 최적화를 생각
우선 완전검색으로 접근하여 해답을 도출하고, 성능 개선을 위해 다른 알고리즘을 사용하고 결과를 확인
문제마다 어떤 것을 조사해야되는지 다르다 => 접근 방법이 다르다.
1. 순열
서로 다른 n개의 원소들 중 r개를 뽑아서 한 줄로 나열하는 것
nPr = n*(n-1)*(n-2)*…*(n-r+1)
nPn = n*(n-1) => n으로 끝나는 수에 대한 n-1 순열
비트로 선택하냐 마냐를 표시 가능
중복순열
2. 조합
서로 다른 n개의 원소들 중 r개를 순서없이 골라낸 것
점화식: nCr = n-1Cr-1 + n-1Cr
그러나 점화식으로 해결하려고 하면 중복되는 부분이 많다 => DP로 해결
중복조합
BFS로 구현
3. 부분집합
각 원소를 선택하냐 마냐를 표시하여 구현
비트로 선택여부를 표시 가능
trade - off의 문제(최적의 문제)
III. 그리디 알고리즘
최적해를 구하는 데 사용되는 근시안적인 방법
매 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
- 그러나 언제나 그것이 최적이라는 보장은 없다. 검증이 필요
그리디 알고리즘을 검증없이 사용하는 것은 위험하므로, 항상 확실한 검증 후 사용해야 한다
1. 동작과정
해 선택: 부분 문제의 최적해를 구하고, 부분 해 집합에 추가
실행 가능성 검사: 부분 해 집합이 실행 가능한지 확인. 문제의 제약 조건을 위배하지 않는지 확인
해 검사: 부분 해 집합이 문제의 해가 되는지 확인
2. Best-First Search
너비우선 검색 기반
휴리스틱 함수를 사용하여, 최적의 해를 가진 노드를 우선순위 큐에 삽입
- 기대치(휴리스틱)을 기반으로 우선순위 큐 구성
우선순위 큐에서 하나씩 꺼내면서 탐색
문제는 기대치(휴리스틱)를 설정하는 방법