성균관대학교 문제적해결과 알고리즘 기말자료 - 코딩과 알고리즘 이론을 중심으로

소개

"성균관대학교 문제적해결과 알고리즘 기말자료 - 코딩과 알고리즘 이론을 중심으로"에 대한 내용입니다.

목차

없음

본문내용

1. 분할 정복 알고리즘(Divide & Conquer Algorithm → DCA)
- 주어진 문제를 최소 단위로 분할하여 문제를 해결하는 방식.
- 작은 단위의 문제로 분할 → 작은 단위의 문제(sub problem)을 풀다보면 → 전체 문제 해결(정복)
- 분할 정복 알고리즘 설계
1단계 분할: 하나 이상의 작은 단위로 분할.
2단계 정복(해결): 작은 단위의 문제를 정복(해결) + 작은 단위의 문제가 계속 분할. 가능한 경우 분할 작업을 우선 적용.
3단계 통합: 작은 단위 정복에서 얻어진 해결 방법 통합하여 원래 문제의 답 구함. (기본 단위에서 처음 단계까지 거꾸로 가는 과정!)

* 프로그래밍의 다섯 단계
1. 변수 선언 → 데이터 입력하기 위해. 파이썬의 경우, 따로 변수 선언이 필요치 않지만 구조화된 프로그래밍은 데이터 넣으려면 변수 선언해야 함. (ex) 입력(input), 임시(temp), 출력(print)
2. 초기화 → 변수 선언하지 않으면 문제 발생하는 경우가 있음. 변수를 사용자에게 익숙한 값으로 초기화. (ex) 입력(input), 임시(temp), 출력(print)
3. 데이터 입력
4. 연산 → 알고리즘 설계. 설계된 알고리즘에 따라 입·출력을 각각 정의함.
5. 결과 출력

- 이 과정이 진행되면 전체 하나의 문제가 수많은 작은 문제로 구성이 되고, 실제 그 작은 문제 안에서는 아주 간단한 연산만 진행됨.
- 작은 문제가 분할 작업 가능할 경우, 분할 작업 우선 적용 후 정복 단계로 넘어옴.
- 정복에서 얻은 값을 통합하면 원래 문제 즉, 전체 문제의 해를 구할 수 있음.

* DCA와 재귀 호출 비교

- 재귀 호출 → 피보나치 수열을 생각하자.
즉, 하나의 수를 구하기 위해서 계속해서(재귀적으로) 자기 자신()을 호출해주는 것.
‘n개로 분할 되는 경우 첫 단계에서 1개의 문제 해결’ → “분할 정복 아닌가?” → NO

왜 그럴까? 이 역시 차근차근 살펴보도록 하자.

이제 분할 정복을 살펴보자. 분할 정복은 재귀호출과 유사 BUT 분할을 먼저 한 후, 단위문제가 남았을 때 단위문제를 해결한다.

참고자료

· 없음