3개의 댓글이 있습니다.
-
-
JongMan -
O(n) 은 필요 없으시고요..? ^^; 이거 제 책 원고에 있는 문젠데 -_-;;;; 어떻게 이게 딱 질문으로 올라오지 -_-;;;;
[0,n) 구간의 숫자 a, b (a < b) 를 잡아서 p(b) - p(a) 를 최대화 하고 싶다고 하죠. [ 는 폐구간, ) 는 개구간을 나타냅니다.
let mid = n/2 라고 두고,
[0,n) 구간을 [0,mid), [mid,n) 의 두 구간으로 나눠 봅시다. 그렇다면 우리가 원하는 답은
1. 왼쪽 절반에 있다
2. 오른쪽 절반에 있다
3. 왼쪽 절반에서 사고, 오른쪽 절반에서 판다
셋 중 하나겠죠. 1 과 2 는 재귀호출로 해결 가능하고, 3 은 O(n) 으로 해결 가능하니 T(n) = 2 * T(n/2) + n = O(nlgn) 이 되겠습니다.
사실 O(n) 문제를 O(nlgn) 에 억지로 풀자면 뭔들 못 하겠습니까만.. ^^
15년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
세실
간단한 문제인데요. p라는 함수가 있는데 이 함수는 주식시장의 시세를 알려주는 함수입니다.
즉 p(1)은 1일째의 주식시장의 시세를 리턴하고 p(n)은 n일쨰의 주식시장의 시세를 리턴합니다.
그래서 가장 큰 차액을 할 수 있는 날을 찾는건데, 예를 들면 p(1) 10 p(3) 70 p(4) 30 p(5) 100
이면 p(1)에 사서 p(5)에 팔아서 90을 벌 수가 있다는 겁니다.
Brute Force는 n^2인데, 문제는 여기서 Divide and Conquer로 n log n으로 풀 수 있냐고 물어봤는데,
아시는 형은 (잘하시는 형인대) n으로 금방 풀어버리셧더라구요;
Divide and Conquer로 어떻게 풀 수 있을까요
답변 부탁드립니다.
15년 전