2] 강남대로에 커피 전문점들을 개점하고자 n+1 개의 장소를 다음의 그림과 같이 물색하였고 각
장소에는 1 개의 coffee shop 을 개점할 수 있다. 단, 각 coffee shop i 의 예상 매출액은 Pi>0 이다.
위 그림에서 m0 는 가장 왼쪽에 위치한 장소이고, mi 는 장소 i 가 가장 왼쪽 장소로부터 떨어진
거리이다. Coffee shop 을 개점하는 조건은 2 개의 shop 이 적어도 x km 떨어져 있어야 한다. 단, x > 0.
위의 조건 하에서, 최대 total 예상 매출액을 찾는 알고리즘을 제시하시오. 또한, 제안한 알고리즘을
간단한 예제 (n>5)에 대해 trace 한 결과를 보이시오.
profit(i) = p1 i = 1
max{profit(i − 1), profit(pred(i)) + pi} 1 < i <= n, pred(i) > 0
max{profit(i − 1), pi} 1 < i <= n, pred(i) = 0
매장의 개설수에 따라 매출액이 증가한다고 생각하면
매장의 위치를 i라고 하면 (i-1)매장에 대한 매출액과 (i이전의 모든 매출액의 합 + i의 매출액)중 큰것을 최대매출로 생각하면 안되나요?
개업할때의 매출과 안할때의 매출을 부분해로 구한다는것이 이해가 잘 되지 않습니다 ㅠㅠ
매장의 위치를 i라고 하면 (i-1)매장에 대한 매출액과 (i이전의 모든 매출액의 합 + i의 매출액)중 큰것을 최대매출로 생각하면 안되나요? 네, 안됩니다. 왜냐하면 i 이전의 매장들에 대해서 거리가 x이상으로 떨어지지 않는 가게가 존재할 경우가 반례입니다. x= 1000; 거리 0 1 2 3 4 5 pi 2 3 4 5 6 7 이 경우 pi가 7인 경우가 최적입니다. 거리를 구분하기 위해 현 가게가 개업할 때와 개업하지 않을 때로 구분하여 동적계획법을 적용해야합니다. 아닐 경우, 작성자분께서 말씀하시는 것은 전체 총 합이라는 결과를 얻게 됩니다. (동적계획법으로 적어놓은 pred의 정의는 무엇인지 모르겠습니다.)
아래처럼 생각해도 될까요??의견 부탁 드립니다~^^
상점간 최소 거리 x = 10km 라고 가정
거리 매출
M0 0
M1 10 1
M2 3 2
M3 10 3
M4 5 4
M5 15 5
Mn = MAX(n번째 shop 이전에 동시 개업 가능한 shop의 매출액 합의 최대값 + n번째 shop의 매출액), n번째 shop을 개업하지 않을 경우의 매출액 합의 최대값)
M1 = MAX(1,0) = 1
M2 = MAX(2,1) = 2
2 : M1에서 M2의 거리가 3km이므로 M2매장을 OPEN하면 M1매장을 오픈하지 못하므로 최대매출액은
M2를 오픈했을때의 2임
1: M2를 오픈하지 않을 경우의 최대 매출액은 1
M3 = MAX(2+3,2) = 5
2: M2까지의 오픈가능 매장의 최대매출액의 합
3: M3 오픈했을때의 매출액
2: M3오픈하지 않았을때의 최대매출액의 합
M4 = MAX(2+4,5) = 6
2:M3에서 M4까지의 거리가 5km이므로 M4가 오픈되면 M3는 오픈하지 못하므로 M2까지 최대매출액적용
4:M4 오픈했을때의 매출액
5:M4를 오픈하지 않았을때의 최대매출액의 합
M5 = MAX(6+5, 6) = 11
6: M4에서 M5의 까지의 거리가 15km이므로 M4 매장도 오픈 가능하므로 M4까의의 최대매출액의 합은 6
5: M5 오픈했을때의 매출액
6: M5를 오픈하지 않았을때의 최대매출액의 합
부분해 :m0 m1 m2 m3 m4 m5
1 2 5 6 11
상점간 최소 거리 x = 10km 라고 가정
거리 매출
M0 0
M1 10 1
M2 3 2
M3 10 3
M4 5 4
M5 15 5
Mn = MAX(n번째 shop 이전에 동시 개업 가능한 shop의 매출액 합의 최대값 + n번째 shop의 매출액), n번째 shop을 개업하지 않을 경우의 매출액 합의 최대값) // 동적계획법의 정의를 잘 하셨습니다.
M1 = MAX(1,0) = 1
M2 = MAX(2,1) = 2
2 : M1에서 M2의 거리가 3km이므로 M2매장을 OPEN하면 M1매장을 오픈하지 못하므로 최대매출액은
M2를 오픈했을때의 2임 // 맞습니다
1: M2를 오픈하지 않을 경우의 최대 매출액은 1
M3 = MAX(2+3,2) = 5
2: M2까지의 오픈가능 매장의 최대매출액의 합
3: M3 오픈했을때의 매출액
2: M3오픈하지 않았을때의 최대매출액의 합
M4 = MAX(2+4,5) = 6
2:M3에서 M4까지의 거리가 5km이므로 M4가 오픈되면 M3는 오픈하지 못하므로 M2까지 최대매출액적용
// M3을 오픈하지 못한다해서 M2를 오픈할 수 있는 것은 아닙니다. 5km이므로 거리가 -5km인 상점만 열 수 있으므로, M4를 제외한 나머지 상점은 앞에서 오픈할 수 없습니다.
4:M4 오픈했을때의 매출액
5:M4를 오픈하지 않았을때의 최대매출액의 합
M5 = MAX(6+5, 6) = 11
6: M4에서 M5의 까지의 거리가 15km이므로 M4 매장도 오픈 가능하므로 M4까의의 최대매출액의 합은 6
// M4를 열 수 있음은 맞지만, 앞에서 M4의 값이 잘못되었습니다.
5: M5 오픈했을때의 매출액
6: M5를 오픈하지 않았을때의 최대매출액의 합
부분해 :m0 m1 m2 m3 m4 m5
1 2 5 6 11
거리 10km 3km 10km 5km 15km
또한, 처음에 거리를 기준으로 정렬을 하셔야 합니다. 재귀를 사용하셔서 메모이제이션 하시는 것이 아니라면,
반복문에서는 한 번의 루프후 종료이므로 전체 해를 구할 수 없습니다.
작성자님의 방법에서는
x= 3
m1 11 5
m2 7 4
m3 3 3
m1 = (5+4,5)
m2 = (4+3,4)
m3 = (3+0,3)
이지만, 실제로는 m1 = (5+4+3,5) 입니다.
(정렬을 하였을 경우)
table의 정의는 잘 하셨지만, 프로세스가 정의대로 돌아가지 않습니다.
메모이제이션을 이용하시면 가능합니다. 하지만 시간복잡도의 증가가 일어납니다.
정렬을 하지 않는 메모이제이션을 이용하는데에 n2이 걸립니다.
정렬을 한 다이나믹의 경우 조건의 idx를 잘 저장한다면, nlgn의 시간복잡도로 해결할 수 있습니다.
그러므로 n제한을 보시고 하시면 가능합니다.
또한, 재귀함수는 호출이 10000스택 이상으로 넘어갈 경우 런타임에러가 납니다.
n제한이 n2 이 가능할 경우라도 중간에 프로그램이 터질 수있기에
재귀의 경우는 시간 복잡도의 하계가 높은 문제에 대해서 사용해주시는 것이 좋습니다.
(시간복잡도의 하계란, n의 제한에 비례하므로 n 제한에 따라서 간편한 메모이제이션이라도 AC를 위해 다이나믹으로 바꿔주셔야합니다.)
문제를 풀 때는, 자신이 충분히 고민을 하고서 푸는 것이 좋습니다.
충분히 문제를 생각하지 않으셨다면 다시금 문제를 풀어보시고,
그럴 경우에도 모르시겠다면 제가 쓴 글을 보시길 바랍니다.
문제 자체가 기하평면이 아닌 일차원 수직선에 장소가 존재하는 형태인 듯 입력이 주어지므로 일차원 수직선 상 동적계획법으로 알려드리겠습니다. 문제시 댓글 남겨주세요
m0가 기준이므로 m0의 거리를 0으로 입력한 상태에서 모든 coffee shop들을 거리를 기준으로 정렬합니다.
이때, 우리가 필요한 정보를 저장할 공간을 table[]이라 정의하면 table[]은 다음과 같이 정의됩니다.
table[i] = max( table[ mi-x 보다 작거나 같은 m의 집합에서, 값이 가장 큰 m ] + Pi ] , table[i-1] )
정의의 의미는 다음과 같습니다.
i shop까지 고려한 최대치 = 이들중 최대값 ( i shop 이전에 동시 개업 가능한 shop의 Pi의 합의 최대치 + i shop의 Pi,
i shop을 개업하지 않을 경우의 최대치 )
즉, i shop을 개업할때의 최대치와, 개업하지 않을 경우의 최대치로 기억하는 것입니다.
처음에 정렬이 되어있으므로, 각 동적계획법당 1~i 까지를 탐색하며 기록하면 됩니다.
결국 동적계획법을 O( N2 ) 으로 해결할 수 있습니다.
생각해보자면, 우리는 정렬을 NlgN 만에 할 수 있고,
i를 탐색했을 때, mi-x보다 작거나 같은 값들중 가장 큰 값 m에 대한 index, j를 알 수 있으므로
다음번에 탐색할 i+1에 대해서 m(i+1)-x 보다 작거나 같은 값들중 가장 큰 값 m은 j보다 크거나 같은 것들 중에 존재함을 알 수 있습니다. 결국 탐색을 O ( N ) 만에 할 수 있으므로, 정렬의 시간복잡도인 O ( NlgN ) 만에 문제를 해결 할 수 있습니다.