출저는 문제 링크입니다. <div><br></div> <div>대략 설명을 드리면 2차원 배열이 있고(. 이랑 X로 표현)</div> <div>그 배열에서 최대 정사각형의 변의 길이를 구하라는 문제인데요</div> <div><br></div> <div>. . <b>. . . .</b></div> <div>. X<b>. . . .</b></div> <div>. . <b>. . . .</b> <- 요런 4 * 6 배열의 경우 4을 아웃풋으로 뽑으라는 문제입니다. (굻게 표시된 점)</div> <div>X. <b>. . . . </b></div> <div><br></div> <div>(X 의 좌표를 계속 주고 이때 최대 길이를 구하라고 하지만 중요하진 않으니 스킵)</div> <div><br></div> <div>제가 생각한 알고리즘이 있기는 한데 이게 맞는 접근 방법인지 봐주시기 바랍니다.</div> <div>--- (분할) ---</div> <div>일단 문제의 크기를 4개로 나눕니다. 가로, 세로를 반으로 쪼개서 재귀함수에 넣습니다.</div> <div><div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201509/1442931384m1uzVZ4TPmwH.png" width="800" height="335" alt="그림1.png" class="chimg_photo" style="border:none;"></div>그림으로 나타내면 다음같습니다.</div> <div><br></div> <div>--- (반환) ---</div> <div>위에처럼 쪼개는 연산을 반복해서 크기가 1이 될때까지 이어갑니다.</div> <div>1이 되면 하나의 좌표가 나오는대 이 좌표에 해당하는 배열값이 만약 . 이라면 1을 반환하고 X 라면 0을 반환합니다.</div> <div>반환 단계는 그냥 이정도로만 간단히 나옵니다.</div> <div><br></div> <div>--- (통합) ---</div> <div>이제부터가 쫌 골때리는 통합단계인데요.</div> <div>그 전에 먼저 함수 설명을 드리자면</div> <div>square square_caculate(int startX, int startY, int endX, int endY) // (여기서 square는 정사각형의 시작 좌표와 길이, 사분면의 위치를 담고있습니다)</div> <div>{</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>if(startX == endX && startY == endY) {<span class="Apple-tab-span" style="white-space:pre;"> </span>// 반환 단계</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>if(배열[startX][startY] == '.') return~;</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>else return~;</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="font-size:9pt;line-height:1.5;"><span class="Apple-tab-span" style="white-space:pre;"> </span>square1 = square_caculate(...);<span class="Apple-tab-span" style="white-space:pre;"> </span>//분할 단계</span></div> <div><span style="font-size:9pt;line-height:1.5;"><span class="Apple-tab-span" style="white-space:pre;"> </span></span><span style="font-size:9pt;line-height:1.5;">square2 = </span><span style="font-size:9pt;line-height:1.5;">square_caculate(...);</span></div> <div><span style="font-size:9pt;line-height:1.5;"><span class="Apple-tab-span" style="white-space:pre;"> </span></span><span style="font-size:9pt;line-height:1.5;">square3 = </span><span style="font-size:9pt;line-height:1.5;">square_caculate(...);</span></div> <div><span style="font-size:9pt;line-height:1.5;"><span class="Apple-tab-span" style="white-space:pre;"> </span></span><span style="font-size:9pt;line-height:1.5;">square4 = </span><span style="font-size:9pt;line-height:1.5;">square_caculate(...);</span></div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span></div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>.<span class="Apple-tab-span" style="white-space:pre;"> </span>//통합단계</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>.</div> <div><span class="Apple-tab-span" style="white-space:pre;"> </span>.</div> <div>}</div> <div>이런식으로 구성할려고 하고 있습니다.</div> <div>그래서 통합 단계에서는 4분할 한 각 영역의 최대 정사각형에 대해 조사를 합니다.</div> <div>만약 1사분면에서 최대 길이가 3이 나왔다면 오른쪽 아래 대각선 방향으로,</div> <div>2사분면에서 최대 길이 4가 나왔다면 왼쪽 아래, 3사분면은 왼쪽 위... 이런 방식으로 조사를 진행합니다.</div> <div>이렇게 조사를 진행 해서 최대 길이가 나오는 구조체 square를 반환합니다.</div> <div>여기서 조사한다는건 어쩔수 없이 브루트포스로 검사하고요.</div> <div><br></div> <div>그래서 이런식으로 알고리즘을 짜볼려구 하는데</div> <div>제가 접근하는 방법이 맞는지, 혹시라도 틀렸으면 알맞은 알고리즘좀 알켜주시면 고맙겠습니다~~</div> <div><br></div> <div>ps: 알고리즘 혼자공부는 쫌 어렵네여..</div> <div>특히 외국 알고리즘 문제들은.. ㄷㄷㄷ</div> <div><br></div> <div>ps2: 제가 분할 정복이랑 구조체를 쓴 이유는, 요 두 개를 써야 솔루션이 된다고 하네요..(위 링크 보시면 옆에 태그가 있습니다)</div> <div><br></div> <div><br></div>
댓글 분란 또는 분쟁 때문에 전체 댓글이 블라인드 처리되었습니다.