모바일 오유 바로가기
http://m.todayhumor.co.kr
분류 게시판
베스트
  • 베스트오브베스트
  • 베스트
  • 오늘의베스트
  • 유머
  • 유머자료
  • 유머글
  • 이야기
  • 자유
  • 고민
  • 연애
  • 결혼생활
  • 좋은글
  • 자랑
  • 공포
  • 멘붕
  • 사이다
  • 군대
  • 밀리터리
  • 미스터리
  • 술한잔
  • 오늘있잖아요
  • 투표인증
  • 새해
  • 이슈
  • 시사
  • 시사아카이브
  • 사회면
  • 사건사고
  • 생활
  • 패션
  • 패션착샷
  • 아동패션착샷
  • 뷰티
  • 인테리어
  • DIY
  • 요리
  • 커피&차
  • 육아
  • 법률
  • 동물
  • 지식
  • 취업정보
  • 식물
  • 다이어트
  • 의료
  • 영어
  • 맛집
  • 추천사이트
  • 해외직구
  • 취미
  • 사진
  • 사진강좌
  • 카메라
  • 만화
  • 애니메이션
  • 포니
  • 자전거
  • 자동차
  • 여행
  • 바이크
  • 민물낚시
  • 바다낚시
  • 장난감
  • 그림판
  • 학술
  • 경제
  • 역사
  • 예술
  • 과학
  • 철학
  • 심리학
  • 방송연예
  • 연예
  • 음악
  • 음악찾기
  • 악기
  • 음향기기
  • 영화
  • 다큐멘터리
  • 국내드라마
  • 해외드라마
  • 예능
  • 팟케스트
  • 방송프로그램
  • 무한도전
  • 더지니어스
  • 개그콘서트
  • 런닝맨
  • 나가수
  • 디지털
  • 컴퓨터
  • 프로그래머
  • IT
  • 안티바이러스
  • 애플
  • 안드로이드
  • 스마트폰
  • 윈도우폰
  • 심비안
  • 스포츠
  • 스포츠
  • 축구
  • 야구
  • 농구
  • 바둑
  • 야구팀
  • 삼성
  • 두산
  • NC
  • 넥센
  • 한화
  • SK
  • 기아
  • 롯데
  • LG
  • KT
  • 메이저리그
  • 일본프로야구리그
  • 게임1
  • 플래시게임
  • 게임토론방
  • 엑스박스
  • 플레이스테이션
  • 닌텐도
  • 모바일게임
  • 게임2
  • 던전앤파이터
  • 마비노기
  • 마비노기영웅전
  • 하스스톤
  • 히어로즈오브더스톰
  • gta5
  • 디아블로
  • 디아블로2
  • 피파온라인2
  • 피파온라인3
  • 워크래프트
  • 월드오브워크래프트
  • 밀리언아서
  • 월드오브탱크
  • 블레이드앤소울
  • 검은사막
  • 스타크래프트
  • 스타크래프트2
  • 베틀필드3
  • 마인크래프트
  • 데이즈
  • 문명
  • 서든어택
  • 테라
  • 아이온
  • 심시티5
  • 프리스타일풋볼
  • 스페셜포스
  • 사이퍼즈
  • 도타2
  • 메이플스토리1
  • 메이플스토리2
  • 오버워치
  • 오버워치그룹모집
  • 포켓몬고
  • 파이널판타지14
  • 배틀그라운드
  • 기타
  • 종교
  • 단어장
  • 자료창고
  • 운영
  • 공지사항
  • 오유운영
  • 게시판신청
  • 보류
  • 임시게시판
  • 메르스
  • 세월호
  • 원전사고
  • 2016리오올림픽
  • 2018평창올림픽
  • 코로나19
  • 2020도쿄올림픽
  • 게시판찾기
  • 오유인페이지
    개인차단 상태
    Lim극한님의
    개인페이지입니다
    가입 : 12-01-17
    방문 : 97회
    닉네임변경 이력
    회원차단
    회원차단해제
    게시물ID : programmer_13469
    작성자 : Lim극한
    추천 : 0
    조회수 : 559
    IP : 49.173.***.160
    댓글 : 2개
    등록시간 : 2015/09/22 23:35:25
    http://todayhumor.com/?programmer_13469 모바일
    알고리즘 질문 하나만.. (분할정복)
    옵션
    • 창작글
    • 본인삭제금지
    출저는 문제 링크입니다. <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>
    출처 http://codeforces.com/contest/480/problem/E

    이 게시물을 추천한 분들의 목록입니다.
    푸르딩딩:추천수 3이상 댓글은 배경색이 바뀝니다.
    (단,비공감수가 추천수의 1/3 초과시 해당없음)

    죄송합니다. 댓글 작성은 회원만 가능합니다.

    번호 제 목 이름 날짜 조회 추천
    알고리즘 질문 하나만.. (분할정복) [2] 창작글본인삭제금지 Lim극한 15/09/22 23:35 42 0
    20
    이상하게 배3은 미친듯이 즐겼는데.. [2] 본인삭제금지 Lim극한 15/05/22 23:39 25 1
    19
    임베디드 재밌네요(한탄 + 질문글) [3] Lim극한 15/04/23 23:20 66 0
    18
    입덕할려고 하는대... [8] Lim극한 15/02/27 19:32 82 0
    17
    으잉? 어베스트 쓰니까 이런기능이 있네요 Lim극한 12/12/14 13:34 24 0
    16
    어머머 Lim극한 12/11/20 20:47 34 0
    15
    튜토리얼 다껜 뉴비입니다 [1] Lim극한 12/11/15 19:57 28 0
    14
    이게 가능해요? ㄷㄷㄷ [3] Lim극한 12/10/28 19:03 54 3
    13
    팀스삐크 할려면 마이크 사야되나요? [2] Lim극한 12/10/27 20:00 25 0
    12
    전투기 레파토리.txt [4] Lim극한 12/10/22 22:43 54 0
    11
    배필하면서 느낀점.jpg Lim극한 12/10/11 20:08 34 1
    10
    티아라가 좋아하는 게임악당 Lim극한 12/07/28 18:03 206 0
    9
    배필3 오류질문점... [1] Lim극한 12/07/14 13:36 33 0
    8
    업글질문입니당 [9] Lim극한 12/05/11 20:22 59 0
    7
    견적 질문입니당...고수님들의 조언이 필요해여~~ Lim극한 12/05/06 12:59 50 0
    6
    컴퓨터 견적좀 봐주세요~~ㅠㅜ [2] Lim극한 12/04/29 21:15 65 0
    5
    배필-배컴2 개인적 맵소감 Lim극한 12/04/24 19:57 43 0
    4
    방금 똥싸고왔음 Lim극한 12/03/31 22:47 69 1
    3
    의류브랜드 추천좀해주세요~ [3] Lim극한 12/02/19 18:15 74 0
    2
    칸카드 가기 vs 2편 합본 사기 [1] Lim극한 12/02/01 18:48 56 0
    1
    업글질문점... [5] Lim극한 12/01/27 16:15 69 0
    [1]
    단축키 운영진에게 바란다(삭제요청/제안) 운영게 게시판신청 자료창고 보류 개인정보취급방침 청소년보호정책 모바일홈