앞의 포스팅을 통해 "최대합 구하기"에 대한 내용을 언급한 바 있습니다. "생각하는 프로그래밍"은 각 컬럼의 마지막에 연습문제를 제시함으로써 정말 "생각"할 수 있는 기회를 주곤 하는데요, 해당 컬럼의 10번 연습문제는 다음과 같습니다.
10. 최대합 대신에 0에 가장 가까운 합을 가지는 부분 벡터를 찾는 것이 목적이라 하자, 여러분이 이 문제를 풀기 위해 디자인 할 수 있는 가장 효육적인 알고리즘은 무엇인가? 어떤 알고리즘 디자인 기법을 적용할 수 있는가? 또 주어진 실수 t에 가장 가까운 합을 가지는 부분 벡터를 찾는다고 하면 어떻겠는가?
책을 읽는 목적이 좀더 효율적인 프로그래밍을 하고, 많은 생각을 하기 위함이라면, 이런 연습문제를 좀더 착실히(?) 풀어볼 필요가 있습니다. 실제로 도움도 많이 될테구요.
나이가 들어서인지 풀릴 듯 하면서도 잘 풀리지가 않았습니다. 가장 효율적인 알고리즘은 앞에서 이야기한 O(n)에 푸는 방법일테니까요.
고민을 하고 있다가, 잠시 차 한잔해야지 하고 밖에 나갔다가 불현듯 떠오르는 생각에 코드를 적어보니, 역시나 되더군요. 아직 많이 녹슬지는 않았나봅니다. ^^
먼저 부분합이 0에 가까워지는 케이스입니다.
min_abs(a,b)를 다음과 같이 정의해보기로 합니다.
int min_abs(int a, int b)
{
if( abs(a) < abs(b) ) return a;
else return b;
}
{
if( abs(a) < abs(b) ) return a;
else return b;
}
즉, 절대값이 작은 값을 반환하는 함수인데요, 예를 들어 -5 와 3을 입력하면 3이 나오고, -10 과 20을 입력하면 -10이 나오게 됩니다.
위와 같이 min_abs를 정의하고,
minendinghere = x[0]
minsofar = x[0]
for i=[1,n)
minendinghere = min_abs(minendinghere + x[i], x[i])
minsofar = min_abs( minsofar, minendinghere)
minsofar = x[0]
for i=[1,n)
minendinghere = min_abs(minendinghere + x[i], x[i])
minsofar = min_abs( minsofar, minendinghere)
와 같이 적용하니 정확하게 0 에 가장 가까운 부분합을 표시하게 됩니다.
책에서 주어졌던 숫자 배열인
31, -41, 59, 26, -53, 58, 97, -93, -23, 84
에 대해서 적용해보면
Close to Zero : 4
From 6 To 7
97 -93
From 6 To 7
97 -93
97과 -93을 더했을 때 4가 나오며 이 값이 0에 가장 가깝다는 것을 알 수 있습니다.
또한, 문제에서 임의의 실수 t에 가까운 부분합을 찾는 부분이 있는데, 이 역시 간단하게 적용이 가능합니다.
위에서 정의한 min_abs()를 아래와 같이 변경하는 것으로 구현이 가능합니다.
int min_abs(int a, int b)
{
if( abs(TARGET_NUMBER - a) < abs( TARGET_NUMBER - b) ) return a;
else return b;
}
{
if( abs(TARGET_NUMBER - a) < abs( TARGET_NUMBER - b) ) return a;
else return b;
}
즐거운 금요일이네요. 모두 행복하세요~
p.s. 연습문제를 더 살펴보니 13번에 다음과 같은 문제가 있네요.
13. 최대합 부분벡터를 찾는 문제에서 실수로 이루어진 n*n 배열이 주어졌고, 직사각형 모양의 부분 배열에 대한 최대합을 구해야 한다. 이 문제의 복잡성은 어느정도인가?
주말 동안 생각해볼 좋은 주제하나 얻었네요~
댓글을 달아 주세요