-
1.
iterator를 이용해서 배열을 순차적으로 한번만 돎, random access X
배열의 길이는 알려지지 않았다.
이 중 n개를 뽑아야 하는데 배열의 길이를 m이라고 한다면 배열 모든 원소를 같은 확률인 n/m의 확률로 뽑아야 함.
메모리의 용량은 n개의 원소들을 저장할 수 있는 배열 하나이다.
n=1인 경우부터 시작
iterator 순회하면서 1개를 배열에 투입.
2부터 iterator 마지막까지 1/n+1 ... 1/n+k의 확률로 뽑아서 배열에 있는 수와 변경하거나 1-(1/n+1), ... 1-(1/n+k) 의 확률로 뽑히지 않거나 계산한다.
모든 원소의 뽑힐 확률이 1/m = n/m으로 동일하다
n의 일반적인 경우에 대해서 이야기 해보자
마찬가지로 n개의 원소에 대해서 무조건 투입하고,
n+1번째 원소가 들어갈 확률은 n/(n+1)이다.
n+2번째 원소가 들어갈 확률은 n/(n+2)이다.
m번째 원소가 들어갈 확률은 n/m이다.
그러면 중간 원소들이 뽑힐 확률이 n/m이 되는지 확인해보자
m=n+1인 경우에서의 첫 번째 원소가 배열에 남아있을 확률에 대해서 확인해보자
1번째 원소가 들어갈 확률 * n+1번째 원소가 들어가고 1대신 다른 원소가 빠질 확률 +
1번째 원소가 들어갈 확률 * n+1번째 원소가 들어가지 못하는 확률 = n/m
1 * n/n+1 * n-1/n + 1 * 1/n+1 = n/n+1
귀납적으로 증명이 가능하다.
마지막에 뽑히는 원소가 n/m이라는 확률을 가지는 것부터 시작해서 역으로 접근하면 좀 쉽게 풀 수 있다.
2.
A,B 수열이 주어지고 A에 연산을 적용해서 B와 동일하게 만드는 최소 비용
연산은 두 가지 존재
1) 임의의 A 원소를 B로 바꾼다. ex) A[i] = B[i]
2) 연속된 구간의 A원소를 B원소로 바꾼다. A[i..j] = B[i..j]
1번 연산의 cost는 3
2번 연산의 cost = 길이 + 6
입력으로 A와 B의 다른 원소들 인덱스가 오름차순으로 주어진다.
O(N^2) dp로 가능
dp[i] := i번째 까지 최소 비용
dp[i] = dp[i-1]+3
dp[i] = 0<=j<=i dp[i] = min(dp[j-1]+num[i]-num[j]+6)
O(N)
3*원소의 수 vs 최대 원소 - 최소 원수(길이) +6
원소 > 길이/3 + 6
이므로
관찰 0 길이가 점점 길이지면 길어질 수록 그 안에 있는 원소에 대해서 2번 연산 적용시키는 것의 효율이 좋은 것을 알 수 있다.
관찰 1 원소/길이 비율에 따라서 다르므로 단순하게 몇 칸 이상 차이나는 segment 이런거는 무용지물이라고 판단된다.
관찰 2 X segment와 Y segment에 각각 2번 연산을 적용시키는 것 vs 합쳐서 2번 연산시키는 것에 대한 연산은 X,Y 원소의 수 합 + 6 vs X 최소 Y최대의 차이가 된다. 여기에서 연산을 통해서 만약 어떤 두 segment 사이의 원소가 7이상 차이가 나면 나누는 것이 이득이다.
dp[i] := i 까지의 최소 비용
dp[i] = min(dp[i-1]+3, num[i]-min_num+1+6)
if(num[i]-num[i-1]>6) min_num = num[i]
이렇게 하면 될 것 같다.
우선 단순하게 1번 연산을 시키는 경우와 2번 연산을 시키는 경우에 대해서는 dp[i] = min(dp[i-1]+3, num[i]-min_num+1+6) 에서 커버한다고 생각이 들었고,
이제 두 X segment와 Y segment로 나누는 것이 이득인지 아닌지는 관찰 2에서 확인한 것처럼 생각하면 될 것 같다.
너무 차분히 생각안하고 떠들기에 바빴다......... ㅠ
이또한 경험이고 실력인걸 어쩌겠는가