원문 : Largest product in a grid.



In the 20x20 grid below, four numbers along a diagonal line have been marked in red.


08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48


The product of these number is 26 x 63 x 78 x 14 = 1788696.


What is the greatest product of four adjacent numbers in the same direction( up, down, left, right, or diagonally ) in the 20x20 grid?


아래의 20x20 그리드에서, 대각선을 따라 존재하는 네 개의 숫자가 붉은 색으로 표시되어 있습니다.


08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48


이 네 숫자의 곱은 26 x 63 x 78 x 14 = 1788696 입니다.


20x20 그리드의 같은 방향( 위쪽, 아래쪽, 왼쪽, 오른쪽, 대각선 )에 있는 4 개의 인접한 숫자들의 곱 중에서 가장 큰 숫자는 무엇일까요?


Brute-Force


이 문제를 가시화하면 다음과 같습니다. ( i, j ) 요소를 중심으로 살펴 보시다. 그러면 아래 그림에서 검은색을 중심으로 색칠해져 있는 부분들의 곱을 구해서 가장 큰 숫자들을 찾으면 됩니다.



그런데 딱 봐도 루프를 돌 때 중복되는 부분이 많을 것 같다는 생각이 듭니다. 특정 방향은 다른 좌표를 중심으로 하는 셸을 계산할 때 서로 겹치므로 배제될 수 있습니다( 예를 들어 왼쪽과 오른쪽, 위쪽과 아래쪽, 위쪽 대각선과 아래쪽 대각선 ).



이 정도로 최적화라고 부르긴 좀 뭐해서 여기까지 Brute-Force 라 생각하도록 하겠습니다.



답은 70600674 입니다.


Other's solution


다른 사람들의 구현을 살펴 봤는데, 루프를 도는 방식에 조금 차이가 있을 뿐이고 크게 다르지는 않더군요.


그런데 파이썬에서 동적으로 자료구조를 만드는 편리한( 코드가 짧은 ) 방법들이 있는데, 꽤 어렵네요. [ JASON'S CODE BLOG ] 에서는 다음과 같이 2 차 배열을 만듭니다.



파이썬은 문법이 뭔가 살짝 괴랄하지만 익숙해지면 편하게 쓸 수 있을 것 같아 보이네요.

주의 : 공부하면서 정리한 것이라서 잘못된 내용이 포함되어 있을 수 있습니다.



WPF 작업을 하다가 보면 직접 스크롤 뷰어의 동작을 제어하고 싶을 경우가 있습니다. 예를 들어 CustomControl 에서 마우스를 드래깅하면 스크롤이 갱신되는 것과 같은 작업을 원할 수 있습니다.


이 경우에 몇 ScrollViewer 를 직접 상속하는 커스텀 컨트롤을 만드는 것도 방법이지만, 다른 컨트롤을 상속해야 하는 경우에는 이런 방법을 사용할 수 없습니다.


하지만 왠만한 건 다 구현되어 있는 WPF 답게, WPF 는 스크롤에 대한 동작을 ScrollViewer 의 Content 로 지정된 컨트롤에서 제어할 수 있도록 하는 기능을 제공하고 있습니다.


그것은 IScrollInfo 라는 인터페이스를 통해서 이루어집니다. 이것은 24 개의 프라퍼티와 메서드를 구현할 것을 요구하는데요, 개수만 보면 정말 질릴 정도입니다. 하지만 기본 개념만 알고 있다면, 매우 편리하게 사용할 수 있다는 것을 알 수 있습니다.


Layouts of ScrollViewer & Content


일단 레이아웃에 대해서 간단히 살펴 보도록 하겠습니다.


그림1. ScrollViewer 와 Content 의 레이아웃.


그림1 에서 ScrollViewer 는 자신이 Content 로 포함하고 있는 컨트롤의 일부를 보여 주고 있습니다( 그림에는 "ScrollView" 라고 되어 있는데, "ScrollViewer" 입니다 ). 일반적으로 XAML 에서 다음과 같이 표현되겠죠.



FlowChartView 라는 것은 제가 개인적으로 만들고 있는 커스텀 컨트롤입니다. 다들 아실거라 생각하지만, 부연하자면, <ScrollViewer>, </ScrollViewer> 마커( marker ) 사이에 들어 가는 컨트롤은 ScrollViewer.Content 에 할당됩니다. 그래서 제가 위에서 계속 "Content 로 포함하고 있는" 이라는 표현을 쓰고 있는 겁니다. 


어쨌든 이렇게 하면 자동으로 스크롤 뷰어가 내부 내용을 인지하게 됩니다. 




하지만 안타깝게도 제가 만든 컨트롤은 크기를 지정하지 않았습니다. 내부에 Canvas 를 가지고 있으며, 그것의 크기가 결정되지 않았기 때문입니다. 그래서 ScrollViewer 는 Content 의 크기를 알 수 없습니다.


<ngv:FlowChartView Width="500" Height="500"/> 이런 식으로 크기를 지정하면 썸을 볼 수는 있습니다만, 사용자가 생성하는 노드들에 의해 크기가 결정되는 Canvas 를 만드려는 의도가 있으므로, 크기를 지정하는 것은 바람직하지 않습니다. 필자가 스크롤링하고자 하는 것은 FlowChartView 자체가 아니가 그 안에 들어 있는 Canvas 이기 때문이죠.


이야기가 다른 곳으로 샜는데, 다시 본론으로 돌아가도록 하겠습니다. 


  • Content 의 좌상단을 ( 0, 0 ) 이라고 할 때, Viewport 의 위치는 ( HorizontalOffset, VerticalOffset ) 으로 표현됩니다. 위의 그림1 에서 표현한 경우라면 HorizontalOffset VerticalOffset 은 모두 양수값이겠죠. 이것은 디바이스의 픽셀 값이 아니라, 사용자가 생각하는 논리적인 픽셀값을 의미합니다.
  • ViewportWidthViewportHeight 는 스크롤 뷰가 보여 줘야 하는 픽셀 단위의 크기를 말합니다.
  • ExtentWidth ExtentHeight 는 Content 의 픽셀 단위의 크기를 의미합니다.

레이아웃 자체는 매우 단순하며 IScrollInfo 의 메서드들은 위의 세 종류의 프라퍼티들을 결정하거나 이 프라퍼티들을 사용해서 스크롤링이 가능한지 여부를 판단하는 역할을 수행합니다.


FlowChartView 에서 IScrollInfo 인터페이스를 구현하도록 하겠습니다. 



먼저 위에 나온 프라퍼티의 기본값을 결정해 보도록 하죠.


  • ViewportWidth : FlowChartView 의 ActualWidth.
  • ViewportHeight : FlowChartView 의 ActualHeight.
  • HorizontalOffset : 0.
  • VerticalOffset : 0.
  • ExtentWidth : 1920. 물론 나중에는 실제 Content 의 크기를 계산해서 넣어 줘야 합니다.
  • ExtentHeight : 1080. 이것도 나중에는 실제 크기를 계산해서 넣어 줘야 합니다.





FlowChartView_SizeChanged() 메서드에서는 CanHorizontallyScroll CanVerticallyScroll 을 설정하는데요, 스크롤바를 제어할 수 있는지 여부를 의미하는 파라퍼티들입니다. 만약 CanHorizontallyScroll 이 false 를 반환한다면, ScrollViewer.HorizontalScrollBarVisibility Visible 일 때는 스크롤바가 딤( dim )될테고 Auto 일때는 접힐( collasped ) 것입니다.




하지만 아직까지 스크롤바를 누르거나 어떤 동작을 해도 아무 것도 변하지 않을 겁니다. 왜냐하면 입력에 대한 정의를 하나도 하지 않았기 때문입니다.


ScrollViewer Inputs


IScrollInfo 의 일부 메서드는 ScrollViewer 에 입력이 들어 왔을 때 어떤 동작을 수행해야 하는지를 결정합니다.


예를 들어 오른쪽에 있는 Vertical Scroll 영역의 썸 이외의 부분을 클릭하면 PageDown() 메서드가 호출됩니다. 



이제 PageDown() 메서드에서 적절한 동작을 해 주시면 됩니다. 예를 들어 다음과 같이 계산하는 것이 가능합니다.



즉 전체 ExtentHeight ViewportHeight 크기로 분할했을 때의 시작 위치를 지정하면 됩니다. 하지만 안타깝게도 균등 분할이 될 수 없으므로, 시작 위치는 반드시 0 이어야 하고 마지막 위치는 반드시 ExtentHeight - ViewportHeight 여야겠죠.


위는 단지 예일 뿐입니다. PageDown() 으로 이동해야 할 크기를 정해 놓고 사용할 수도 있고 썸을 제외한 나머지 부분을 균등분할해서 크기를 결정할 수도 있겠죠.



원래 PageDown() 내에서 VerticalOffset 을 결정할 수 있겠지만, 이런 메서드는 매우 많습니다. LineLeft/Right/Up/Down(), MouseWheelLeft/Right/Up/Down(), PageLeft/Right/Up/Down() 등의 메서드가 존재합니다. 그런데 이런 계산을 할 때마다 예외처리하는 것이 불편하기 때문에 SetVerticalOffset() 과 SetHorizontalOffset() 을 사용해서 최종적인 예외 처리 및 위치 결정을 수행합니다.


여기까지 하면 스크롤 바를 눌렀을 때 썸이 이동하는 것을 확인할 수 있습니다.



하지만 칸텐츠가 같이 이동하지 않고 있음을 발견할 수 있습니다. 마지막으로 구현해야 할 것이 하나 남아 있습니다. 실제로 FlowChartView 의 자식인 Canavs 위치를 이동시켜 줘야 합니다. 지금까지는 단지 ScrollViewer 와 관련한 작업만 한 거였습니다. 이것 때문에 저도 당황했었는데요, [ 1 ] 에서 답을 찾을 수 있었습니다.


현재 제가 구현하는 FlowChartView 의 ControlTemplate 에서 Canvas 요소는 다음과 같이 들어 가 있습니다. 그러므로 "PART_NodeViewsContainer" 의 위치를 변경해 주면 됩니다.



SetVerticalOffset() 에서 InvalidateArrange() 를 호출해 주고, 다음과 같이 ArrangeOverride() 에서 위치를 갱신합니다.



제 구현에서는 Canvas 컨테이너의 크기가 중요하지 않으므로 Size 에 0 을 넣었지만, 다른 사람들은 올바른 수치를 넣으면 됩니다. 그리고 스크롤을 했을 때의 칸텐츠 위치는 Viewport 에 대해서 상대적으로 이동해야 하므로 HorizontalOffset VerticalOffset 을 음수값으로 넣고 있습니다.


이제 스크롤링할 때 정상적으로 칸텐츠가 스크롤되는 것을 확인할 수 있습니다.



아! 깜박 잊은 게 하나 있는데요, FlowCharView 를 클릭하면 MakeVisible() 이 호출되면서 원래 위치로 돌아가 버립니다. 그러므로 MakeVisible() 에서도 꼭 InvalidateArrange() 를 호출해 줘야 합니다.



참고자료


[ 1 ] C# WPF Tutorial - Implementing IScrollInfo [Advanced], C#4 ALL.

'Programming > .NET' 카테고리의 다른 글

[ 번역 ] .NET 에서 클래스를 선택할까? 구조체를 선택할까?  (0) 2016.02.12
[ 8 ] Control Template  (0) 2012.10.24
[ 7 ] Style  (0) 2012.10.22
[ 6 ] WPF Content Model  (0) 2012.10.19
[ 5 ] DataTemplate  (0) 2012.10.17
[ 4 ] DataBinding  (0) 2012.10.14
[ 3 ] Dependency property.  (0) 2012.10.11
[ 2 ] XAML  (0) 2012.10.10
[ 1 ] WPF Architecture.  (0) 2012.10.08
[ 6 ] Proerty, indexer, attribute  (0) 2012.10.05

+ Recent posts