[알고리즘] 분할정복법(divide and conquer) 알고리즘 질문드립니다.
글쓴이: gyeseon Lee@Google / 작성시간: 일, 2017/04/23 - 1:38오전
안녕하세요.
대학교에서 컴퓨터공학을 배우는 한 학생입니다.
과제에 대해서 이런식으로 질문을 드려되 되나 싶어 의문이 들지만, 해결방법을 잘 모르겠어서 질문을 남깁니다..
=========
어떤 배열 X[n]에서 인접한 두 수의 합, 즉 X[i]+X[i+1]의 합이 최대가 되는 쌍을 구하려고 한다. 이 문제를 우리는 분할정복법(Divide and Conquer)로 구하고자 한다.
(a) 이를 위한 분할정복법에 의거한 Recursive 형식의 재귀적 알고리즘의 Pseudo code(대략의 방법을 알 수 있는 코드)로 제시하고 - 단 이 코드에서 for 나 while과 같은 looping control 을 사용하면 안된다.
(b) 자신이 제시한 알고리즘의 complexity를 계산하시오.
=========
비슷한 알고리즘으로 '최대합 알고리즘'을 이용해서 해보려고 하는데 그 방법에서는 for나 while같은 반복문이 들어갑니다. 그래서 계속 막히는데, 반복문을 사용하지 않으면서 문제를 해결하는 방법을 알고싶습니다.
혹시 알고계시는 방법이 있으시면 조언좀 부탁드리겠습니다.
Forums:
재귀적으로 프로그램을 짜려면 생각 전환이 필요합니다.
재귀적으로 프로그램을 짜려면 생각 전환이 필요합니다.
즉, 해당 함수가 불리는 시점에서의 각 데이터들이 어떻게 존재하는지를 생각하셔야합니다.
일단 X[i]+X[i+1]의 합이 최대가 되는 쌍을 구해야하므로 일단 저걸 다 해봐야하겠지요.
i가 3이라면 아래 경우수가 나오겠습니다.
X[0]+X[0+1]
X[1]+X[1+1]
X[2]+X[2+1]
고등학교 수학에서(고등학교 나온지가 너무 오래되서 기억이 가물가물하지만... 암튼 고등학교에서 배웠던거 같네요) 점화식을 배우셨을겁니다.
그 점화식이 수학에서 재귀적 풀이법과 동일합니다.
아무튼 위에서 나열한 경우 수의 공통점이 좀 보이지 않으신가요?
일단 X[i]+X[i+1]를 함수화를 시켜보세요. 함수화라는 것은 코드를 일반적이게 짠다는 것입니다.
즉, 어떤 입력이 들어오든간에 정해진 계산식을 수행하고, 입력에 따른 알맞은 결과를 내는 것이지요.
그리고 여기서 증가하는 값이 어떤건지 봐보세요. i라는 값이겠지요.
그런데 제가 나열한 경우 수에서 뭔가 규칙이 보이지 않나요?
그 규칙을 위에서 수행한 함수화 된 코드에 적용해보는 것입니다.
그러면 재귀적으로 함수를 호출할 수 있고 그 결과를 적당한 배열에 차곡차곡 넣은 다음에 그 결과가 가장 큰 값의 X[i]+X[i+1]쌍, 즉 i값이 바로 위 문제의 a번 정답이 되겠지요.
b는 학교에서 배운 복잡도를 적용해보세요. 복잡도는 그냥 공식이라서 코드가 필요 없으니 넘어가겠습니다.
-------------------------------------------------------------------------------
It's better to appear stupid and ask question than to be silent and remain stupid.
댓글 달기