개발정리를 위한 개발로그, 발로그!

제목이 길다.


알고리즘 실력이 점점 떨어지는 것 같아. 예전에 구입하였던 프로그래밍 대회에서 배우는 알고리즘 문제해결전략이라는 책을 다시 보던 중 정리 차원에서 남긴다.

제목 그대로 1차원 배열에서 연속된 부분에서 그 합이 최대인 구간의 값을 구하면 되는 문제.

책에 제시된 샘플은 

[-7, 4, -3, 6, 3, -8, 3, 4]

답은 4,-3,6,3 구간으로 , 합을 구했을 경우 10이 나온다.


이 문제를 처음접했을때 가장 쉽게드는 생각은 다 구해서 최대 구간과 값을 구한다.

-> 가장 무식한 방법이 아닐까 싶다. 그래도 가장 확실히 구할 수 있다 라는 것에는 의심의 여지가 없다.


간단히 코드를 작성해보면 

int 결과 = 0;

for ( int i = 0 ; i < Array크기 ; i++ )  {

  int Sum = 0 ; 

   for ( int j = i ; j < Array크기 ; j++ )  

   Sum += Array[j];

   비교후 가장 큰 값 저장

  } 

}

<- 결과 리턴 


코드 보기가 약간 그지같긴 하지만 어쩔 수 없다,.


이렇게 진행하였을 경우 N제곱이 소비되기 때문에 큰 값이 들어오면 처리할 수가 없다.

그럼 2번째 방법으로 생각할 수 있는건, 어케어케 구하면서 진행하는 것이다. (?) 보통 동적 프로그래밍으로 코드를 작성하려면 나름 타당한 수식을 생각해서 이를 코딩으로 구현해야하기 때문에 곰곰히 생각을 해보았다. 요런건 보통 점화식을 통해 해결하는 경우가 많아 살짝 잘라서 생각을 해보았는데,

A 배열의 최대 부분합을 B 배열이라고 하면 B배열의 제일 왼쪽 혹은 오른쪽을 i 인덱스라 했을때 아래와 같이 표현할 수 있다. (편의상 제일 오른쪽 인덱스를 i라 하겠음 )


B = B[i-1](임의로 표현) + B[i] 


요렇게 하면 나름 타당한 점화식이라 할 수 있겠다. 초기 코드만 살짝 잘 처리해주면 큰 문제가 없을꺼 같다.

for ( int i = 0 ; i < 크기 ;  i++ ) {

 합 = max( 합 , 0 ) + A[i];

 결과 = max( 합, 기존 최대값 ) 

}

결과 리턴...


확실히 글로 쓰니 생각 정리가 명확히 된다.

이제 비슷한 문제 다시 리뷰하면서 생각을 좀 더 구체화 해보자!