직사각형의 합 문제 풀이 및 해설
: 오늘은 DP 혹은 Dynamic Programming으로 불리는 동적계획법과 관련된 문제에 거의 집착(?)하듯이 풀었는데 이문제도 그 유형이다. 이 유형은 많이 풀어보는게 답이라해서.. 일단 이번주에는 최대한 많은 문제를 접해보고자 하는데.. 너무 어렵다.
문제 분석
- (x,y) ~ (z,a)까지 (임의의 x,y,z,a)의 범위에 해당하는 수들을 모두 더한 값을 리턴하는 것이 문제에서 요구하는 바이다.
- 조건으로 n,m 즉, 주어지는 표의 크기의 가로, 세로값이 최대 1000이므로, 표의 크기느 최대 1000 * 1000 = 1,000,000 임을 알 수 있다.
- 또한, 문제에서는 임의의 x,y,z,a에 대한 일종의 질문을 최대 백만번을 낸다고 한다. 즉, 특정 좌표부터 특정 좌표까지의 합을 묻는 질문을 최대 백만번 한다는 것. 이것을 토대로 봤을 때 최악의 경우에 백만번의 질문에 완전탐색으로 표를 분석한다면, 백만번 * 백만번이돼서 사실상 이미 완전탐색으로는 풀 수 없는 문제임을 알 수 있다.
문제 설계
- 완전탐색이 안되면 어떤 방법으로 풀어야할까?. 일단 내가 여태까지 배운 접근법 2가지는 분할정복법, 동적계획법이다. 둘다 재귀호출과 연관있는 해결책인데, 어쨌든, 그 둘을 사용해서 풀 수 있을까?.
- 둘중에 '동적계획법'을 사용해서 풀어보고자 한다. 그러면 일단,
1) 구해야할 값을 정의한다(부분 문제를 정의한다).
- 우리가 최종적으로 구해야할 값은 범위 내의 수들의 합이다.
- 그러면 그것과 유사한 것 그리고 피보나치 수열처럼 이전의 값을 사용해서 현재의 값을 구할 수 있는 형태, 혹은 재귀적 구조를 도출해낼만한 값을 구해보려고 해보자(아주 추상적이고, 어려운 말이지만..ㅎ)
- 합을 구한다는 측면에서, 그리고 앞에것을 이용해 뒤에것을 구한다는 방식을 염두해두고 시작해보면, 먼저, 0,0부터 임의의 (x,y)까지의 합을 구해보는 것을 시도해볼 수 있다.
: 그렇게 하다가 이런 규칙을 발견할 수 있어야한다. 이것은 솔직히 아이디어적인 측면이라 이걸 어떻게 발견해낼 수 있을거다 설명할 수가 없다. 이건 다량의 연습 혹은 솔직히 촉같은 것 같다.. 어쨌든 위의 그림을 설명해보면, (0,0)~(1,1) 까지의 합을 구하려면, 이러한 식이 성립한다는 것을 알 수 있다.T(n,m) = T(n,m-1)+T(n-1,m)-T(n-1,m-1) + T(n,m)
여기서 T(n,m)은 (0,0)을 기준으로 임의의 n,m까지의 수들의 합을 구하는 공식을 의미하고, 그 공식을 저 그림을 기준으로 설명해보면, T(1,1) 즉, 0,0을 기준으로 1,1까지의 수들의 합을 구해보면,T(1,1) = 표의 (1,0) + (0,1) - (0,0) + (1,1) = -2 + -8 + 1 + -9 = -18
임을 알 수 있다. 이는 빨간색 줄로 그은 부분의 합 + 노란색 줄로 그은 부분의 합 + 현재 찾고자하는 범위의 오른쪽 아래의 꼭지점이 되는 요소의 값(연두색 동그라미) - 노란색, 빨간줄 계산시에 두번 계산이 되는 (0,0) 을 식으로 정리한 것이다. 이 때, 주의할 점은 x=0인 줄, 즉, 첫번째 줄은 해당 공식이 통하지 않는다. 만약에 T(0,3)을 구하려고 위의 공식으로 T(0,2) + T(-1,3) - T(-1,2) + T(0,3)을 한다면 -1을 한 부분에 값이 없기 때문에 공식을 이용할 수 없게된다. 따라서 첫번째줄은 예외적으로 이전 요소까지의 합에 현재 요소를 더하는 식으로 계산해줘야한다.T(n,m) = 1) 첫번째줄 : = 실제표(n,m) + T(n,m-1) = 표에서 (n,m)에 해당하는 요소 + 그 그 축의 이전 요소까지의 합 2) 두번째줄부터 : = T(n,m-1)+T(n-1,m)-T(n-1,m-1) + T(n,m)
: 그럼 우리는 1번 단계로 어떤 값을 구할지를 결정했고(0,0부터 임의의 수 n,m까지의 요소들의 합을 구하기), 그것을 하다가 그것을 구하기 위한 식까지(위의 식)구했다. 이는 동적계획법의 2단계까지 과정을 진행했음을 보여준다.
3) 실제 코드로 구현 
: 위의 동적계획법 공식을 코드로 구현한 것인데, 실수했던 부분이 j-1, i-1이 각각 0보다 작을 경우, 즉, 위에서 세운 공식을 적용할 수 없는 부분을 첫번째줄만 예외적으로 처리를 해놨었는데, 그렇게하면 안되고, 맨위쪽이랑 맨 왼쪽줄을 예외처리해야한다. 실제로 구현을 할 때는 배열로 구현하기 때문에 x축이 -1이되는 계산, y축이 -1이 되는 계산을 예외적으로 처리해줘야함!
: 맨위에 문제에 있는 표를 테스트케이스로 돌려본 결과 0,0부터 특정 좌표까지의 합을 담은 배열을 만들 수 있었고, 위의 그림은 이를 출력해본 것이다. 잘출력했음을 알 수 있고, 이제 다음 스텝으로 넘어가야한다.
- 사실 아직 문제설계가 끝나지 않았다. 우리가 구해야하는 것은 (0,0)부터 특정좌표까지의 수들의 합이아니라 (x,y) ~ (z,a) 이렇게 임의의 x,y,z,a에 대해서 요소들의 합을 구해야하는 것이었다. 단지 그것을 구하기 위해 문제를 부분으로 나눠서 정리했고(동적계획법으로), 이제 원래 메인문제를 해결하면 된다.
: 문제에서 주어진 예시를 생각해보면, (1,2) ~ (3,3)을 구해보라는 것인데, 우리가 가진 정보를 바탕으로 이를 도출해보려면 우리는 일단 뭐든지 (0,0)부터 시작하는 정보를 가지고 있기에 그것을 활용하려면 위의 그림처럼 핑크색 부분(문제에서 예시로 묻는 부분)의 합을 구하고 싶으면 그것을 둘러싸면서 and (0,0)부터 시작하는 범위인 연두색 네모 부분에서 핑크색 부분을 제외한 파란색 부분과 주황색 부분을 빼주면 되지 않을까?(이 때 중복해서 더해준부분은 빼줘야함)연두색부분(0,0부터 시작해서 3,3까지의 범위) - [파란색 범위(0,0부터 시작해서 3,1까지의 범위) + 주황색 범위(0,0 부터 시작해서 0,3 까지의 범위) - 중복해서 빼준 범위인 노란색 범위]
: 위와 같은 공식을 떠올렸다면 충분히 문제를 풀 수 있다. 하지만 이 때, 또 분기처리해야할 부분이 있는데
- 이 때, location은 [x,y,z,a]인 리스트다(x,y,z,a는 순서대로 위에서 지정해준 인덱스 범위다)
- 이 때, board는 위에서 만들어준 0,0에서 특정 좌표까지의 합을 모아놓은 2차원 배열이다
분기처리
- 먼저, 만약 문제에서 제시한 question에서의 범위가 0,0에서 시작한다면 단순히 board에 정리해놓은 표에서 찾아서 바로 리턴해주면 된다(ex, (0,0) ~ (3,3)을 찾으라하면 board[3][3]을 해주면 된다.)
- 하지만 만약에 시작하는 꼭지점의 인덱스가 (0,x)라면
- 또는 (x,0) 의형태라면,
- 마지막으로 시작하는 꼭지점의 인덱스에 0이 없다면,
=> 이 부분이 우리가 처음 색깔있는 네모로 그려가며 표현했던 경우에 대한 분기처리이다. '연두색 - (파란색+주황색-노란색)'
마무리 및 코멘트
: 이 문제는 동적계획법에 더해서 분기처리 등 은근히 고려할 요소가 많았던 문제 같다. 하지만, 점점 동적계획법에 대해 자신감을 갖게되는 것 같다. 구해야할 값을 정의하는게 제일 중요한데, 그 값을 정의하는 과정에서 테케를 활용하고, 재귀적 구조를 찾아내야한다. 즉, 여태까지의 자신(n-1과 같은)을 활용해서 n을 구할 수 있는 구조 말이다. 이를 찾아내서 그것을 구할 수 있는 식을 찾아내고, 문제를 풀면된다. 말은 쉽지만 어려우므로 계속 연습하자.
완벽함 보다는 최선의 결과를 위해 끊임없이 노력하는 개발자