CANADATRIP 소스 코드 관련해서 질문이 있습니다. Shiner11 안녕하세요 저는 방학 기간 구종만 님의 알고리즘 문제해결전략 책을 가지고 프로그래밍을 학습 중인 컴퓨터학을 이중전공 중인 대학생입니다. 다름이 아니라 지난 번에 12장의 <최적화 문제 결정문제로 바꿔 풀기> 장에서 CANADATRIP문제를 풀던 중 궁금증이 생기는 부분이 있는데 제가 스스로 해결을 할 수가 없어서 이렇게 알고스팟 질문과 답변 게시판을 이용하게 되었습니다. 교재 P.458에 나와있는 소스코드를 보면 최적화와 관련하여 소스코드가 다음과 같이 나와 있습니다. int optimize() { // 반복문 불변식: !decision(lo) && decision(hi) int lo = -1, hi = 8030001; while(lo+1 < hi) { int mid = (lo + hi) / 2; if(decision(mid)) hi = mid; else lo = mid; } return hi; } 제가 이 코드를 보고 든 의문점은 int optimize() { int lo = 0, hi = 8030000; while(lo < hi) { int mid = (lo + hi) / 2; if(decision(mid)) hi = mid; else lo = mid; } return hi; } 이렇게 lo와 hi의 값을 바꿔주고 while문 안의 조건에서 lo에 1을 더하는 것을 없애줌으로써도 코드를 구할 수 있지 않을까였는데..(돌려보니 시간초과가 뜨더군요...) 혹시 이러한 현상이 발생하는 원인에 대해 설명 좀 해주시겠어요? 제 머리로는 도저히 이해를 못하겠습니다... ㅜㅜ 7년 전
2개의 댓글이 있습니다. Corea lo가 1이고, hi가 2일 때를 생각해보세요. mid가 1이 되고, 이 때decision(mid)가 false라면 lo가 계속 1이 됩니다. 7년 전 link Shiner11 제가 댓글을 너무 늦게 달았네요 ㅜㅜ 감사합니다~! 7년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Shiner11
안녕하세요
저는 방학 기간 구종만 님의 알고리즘 문제해결전략 책을 가지고 프로그래밍을 학습 중인 컴퓨터학을 이중전공 중인 대학생입니다.
다름이 아니라 지난 번에 12장의 <최적화 문제 결정문제로 바꿔 풀기> 장에서 CANADATRIP문제를 풀던 중 궁금증이 생기는 부분이 있는데 제가 스스로 해결을 할 수가 없어서 이렇게 알고스팟 질문과 답변 게시판을 이용하게 되었습니다.
교재 P.458에 나와있는 소스코드를 보면 최적화와 관련하여 소스코드가 다음과 같이 나와 있습니다.
제가 이 코드를 보고 든 의문점은
이렇게 lo와 hi의 값을 바꿔주고 while문 안의 조건에서 lo에 1을 더하는 것을 없애줌으로써도
코드를 구할 수 있지 않을까였는데..(돌려보니 시간초과가 뜨더군요...)
혹시 이러한 현상이 발생하는 원인에 대해 설명 좀 해주시겠어요?
제 머리로는 도저히 이해를 못하겠습니다... ㅜㅜ
7년 전