HW#01 : 피보나치 수열의 값 찾기 문제에 대한 두 가지 접근법에 대한 일반화HW#01 : 피보나치 수열의 값 찾기 문제에 대한 두 가지 접근법에 대한 일반화

Posted at 2011. 3. 17. 11:16 | Posted in Computer Science/알고리즘

피보나치 수열에서 알고리즘의 접근은 Sequential Approach와 Divide and Conquer Approach가 있었다. 이 방법에서 Divide and Conquer Approach가 Sequential Approach 보다 효과적이지 못하다는 것을 배웠다. 그러면 우리는 이 문제에 대해 일반화 시킬 수 있을까? 그것이 첫 번째 숙제이다.

My Solution)
두 가지 접근 방법이 있다고 가정하자. 하나는 Sequential Approach이고 다른 하나는 Divide and Conquer Approach이다. 우리의 목표는 집합에서 원소를 찾는 문제와 피보나치 수열 문제를 통해 일반화된 요약을 도출하는 것이다.

집합 : 유한 원소를 다룬다.
피보나치 수열 : 재귀 형태로 미지수 x에 따라 값이 변화한다.

Domain이 지정되어 있다면 Divide and Conquer Approach가 Sequential Approach보다 효율적이고, Domain이 지정되어 있지 않다면 Sequential Approach가 Divide and Conquer Approach보다 효율적이다.

Instructor's Solution)
하위 문제가 Overlapping이 많이 발생하는 경우, 분할 정복 접근보다는 순차접근이 효과적이다.

결과 : B

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기