알고리즘 Peak Finding 2D 질문

게시물 수정 , 삭제는 로그인 필요

Divide and Conquer로 풀려는데 강의에서 주어진 예제 table에는 잘 풀리는데 제가 임의로 만든 table에서는 풀리지 않습니다.

제가 만든 table이 잘못된 것인지, Divide and Conquer에 대해 잘못 이해한 것인지 궁금합니다.

(아래)Divide and Conquer 순서(원문 그대로 작성합니다.):

- Pick middle column j = m/2

- Find global maximum on column j at (i, j)

- Compare (i, j-1), (i, j), (i, j+1)

- Pick left columns if (i, j-1) > (i, j)

- Similarly for right

- (i, j) is a 2D-peak if neither condition holds

- Solve the new problem with half the number of columns

- When you have a single column, find global maximum and you're done

(아래)임의로 만든 테이블:

10	18	9	11	30	13
16	32	42	28	5	19
31	21	23	41	48	36
7	19	4	13	43	17
25	6	33	47	3	37

(아래)본인의 풀이:

1. Pick middle column j 

-> j = 3

2. Find global maximum on column 3 at (i, 3)

-> i = 2

3. Compare (2, 2), (2, 3), (2, 4)

4. Compare left. (2, 2) < (2, 3)

5. Compare right. (2, 3) > (2, 4)

6. (2, 3) is a 2D-peak. because neither condition holds

위 과정으로 (2, 3)의 value 42가 global maximum이라는 결론인데, table을 보면 실제로는 (3, 5)의 48이 global maximum이지 않습니까?

제가 어느 부분을 제대로 이해하지 못한 것인지 궁금합니다.