문제 풀이

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에서 확인한 것처럼 생각하면 될 것 같다. 

 

 

너무 차분히 생각안하고 떠들기에 바빴다......... ㅠ

이또한 경험이고 실력인걸 어쩌겠는가