아까 알고리즘 문제를 하나 올렸습니다.


문제)

single linked list가 있습니다.


노드는 이런식이라고 정의 되었다고 하죠.

struct node {

node *next;

int val;

};


우리에겐 node *head가 주어져 있습니다.

그리고 우리는 리스트의 랜덤한 임의의 노드를 리턴하고 싶습니다. 

단, 모든 노드는 같은 확률로 선택될수 있어야 합니다.

리스트에 몇개의 노드가 있는지는 모릅니다.


한번의 순회와 추가메모리의 사용없이 임의의 노드를 리턴하는 함수는?

(함수호출에 의한 스텍메모리 사용도 추가메모리 사용으로 간주)


node* get_random_node() {

// TO DO...

}


풀이)

Reservoir sampling으로 검색하시면 더 많은 자료를 보실수 있겠지만 간략히 설명을 드리자면요.

해답의 코딩인 아래와 

node* get_random_node() {

node *cur = head, *ret = nullptr; // ret에 답을 저장합니다.

int idx = 1;

while(cur) {

if(rand() % idx == 0) ret = cur;

cur = cur->next;

++idx;

}

return ret;

}


우선 우리는 head에서 시작해서 넥스트로 이동하면서 링크드 리스트를 순회합니다. 

별표를 현재의 위치라 했을때


1)

head -> next -> next -> next -> next -> .......

idx                   1         2        3         4        5

cur                   *

if(rand() % idx == 0)  1

시작점에서 if의 확률이 100%이므로 ret = 1st 노드 입니다.

다음 노드가 널이면 즉 노드가 하나뿐인 리스트므로 1st 노드를 리턴하는게 맞습니다.


2)

head -> next -> next -> next -> next -> .......

idx                   1         2        3         4        5

cur                                *

if(rand() % idx == 0)           1/2

이전 확률               1


2번째 노드가 선택될 확률이 1/2입니다. 2번째 노드 이전의 노드들이 ret에 선택되었을 확률은 1이므로 1 - 1/2로 

1번째 노드가 ret에 선택될 확률 역시 1/2입니다.


3)

head -> next -> next -> next -> next -> .......

idx                   1         2        3         4        5

cur                                          *

if(rand() % idx == 0)                     1/3

이전 확률               1/2


3번째 노드가 선택될 확률이 1/3입니다. 3번째 노드 이전의 노드들이 ret에 선택되었을 확률은 1/2 이므로 (1 - 1/3)*1/2로 

1번째 노드와 2번째 노드가 ret에 선택될 확률 역시 1/3입니다.


4)

head -> next -> next -> next -> next -> .......

idx                   1         2        3         4        5

cur                                                    *

if(rand() % idx == 0)                                1/4

이전 확률               1/3


4번째 노드가 선택될 확률이 1/4입니다. 4번째 노드 이전의 노드들이 ret에 선택되었을 확률은 1/3 이므로 (1 - 1/4)*1/3로 

1, 2, 3번째 노드가 ret에 선택될 확률 역시 1/4입니다.


.....


n)

head -> next -> next -> next -> next -> .......

idx                   1         2        3         4        5                 n

cur                                                                               *

if(rand() % idx == 0)                                                          1/n

이전 확률               1/(n-1)


n번째 노드가 선택될 확률이 1/n입니다. n번째 노드 이전의 노드들이 ret에 선택되었을 확률은 1/(n-1) 이므로 (1 - 1/n)*1/(n-1)로 

1, 2, 3.... n-1번째 노드가 ret에 선택될 확률 역시 1/n입니다.


그럼 즐프하세요.