컴퓨터알고리즘#3
LeeMir, 10 March 2021
재귀
양팔저울 불량동전 문제
- 1000개의 동전에서 하나가 가벼운 불량 동전일 때 골라내는 문제
- 2개씩 무식하게 비교 => 평균적으로 250번 근처에서 해결될 것
- 반복문, 비재귀적으로 구현
- 문제를 분할
- 분할정복(Divide & Conquar)
- 전체를 절반으로 나눈 후 저울에 올림
- 500개를 양쪽에 올려서 가짜동전이 있는 집단을 또 반으로 나누는 것을 반복
- 동적 프로그래밍
- 탐욕기법
- 분할정복(Divide & Conquar)
재귀
- 알고리즘 자신을 사용하여 정의된 알고리즘을 재귀적(recursive)이라고 말한다
- 비재귀적(nonrecursive) 또는 반복적(iterative) 알고리즘과 대조
- 재귀의 요소
- 재귀 케이스 : 차후의 재귀호출은 작아진 부문제(subproblems)들을 대상으로 이루어진다
- 베이스 케이스 : 부문제들이 충분히 작아지면, 알고리즘은 재귀를 사용하지 않고 이들을 직접 해결한다
- 작동원리
- 보류된 재귀호출(즉, 시작했지만 와료하지 않고 대기중인 호출들)을 위한 변수들에 관련된 저장/복구는 컴퓨터에 의해 자동으로 수행된다
- 대기중인 호출들은 시스템 스택에 저장되었다가 꺼내진다
- 기본 규칙
- 베이스 케이스
- 베이스 케이스를 항상 가져야 하며, 이는 재귀 없이 해결될 수 있어야 한다
- 진행 방향
- 재귀적으로 해결되어야 할 경우, 재귀호출은 항상 베이스 케이스를 향하는 방향으로 진행되어야 한다
- 정상작동 가정
- 모든 재귀호출이 제대로 작동한다고 가정하라
- 적절한 사용
- 꼭 필요할 때만 사용하라, 저장/복구 때문에 성능이 저하되기 때문이다
- 베이스 케이스
- 의사 코드에서 프로그래밍 언어로 옮기기 쉽기 때문에 가독성이 좋다
- 나쁜 재귀
- 잘못 걸계된 재귀
- 베이스 케이스가 없거나 도달 불능
- 재귀 케이스가 베이스 케이스를 향해 작아진 부문제를 대상으로 재귀하지 않음
- 나쁜 재귀 사용의 영향
- 부정확한 결과
- 미정지
- 저장을 위한 기억장소 고갈(메모리 초과)
- 잘못 걸계된 재귀