Randomized Algorithm

[ 무작위 알고리즘 ]

무작위 알고리즘(Randomized Algorithm) or 랜덤화된 알고리즘은 무작위성을 사용하여 알고리즘의 일부를 랜덤하게 작동하게 만든다. 이런 방식의 알고리즘을 사용하기 좋은 경우는 바로 입력값의 적절한 분포를 알기 어려울 때이다. 입력값의 분포를 모르기 때문에 무작위성을 사용하여 기댓값을 동일한 확률로 처리하기 위함이다. 확률을 따라 운이 좋으면 소요시간이 짧아질 수도 있고 최악의 경우 최대 O(n)까지 비용이 발생한다. O(n)의 뜻을 이해하지 못하겠다면, 이전 글인 시간복잡도 관련한 글을 읽어보는 것을 추천한다. 

 

(1) 정렬 방법 : Permute-by-sorting 

원소마다 임의의 Priority를 할당하고 그 순서대로 정렬한다.

import random

def permute_by_sorting(arr):
    n = len(arr) - 1
    k = random.randrange(0, n)
    arr = sorted(arr, key=lambda val: val[k])
    return arr

arr = [
    ('kayser', 'A', 22),
    ('sam', 'B', 39),
    ('jeen', 'B', 45)
    ]
arr = permute_by_sorting(arr)
print(arr)

> [('jeen', 'B', 45), ('kayser', 'A', 22), ('sam', 'B', 39)]

 

(2) 교환 방법 : Randomize-in-pace

특정 인덱스 i와 n사이의 원소 위치를 교환한다.

import random

def randomize_in_pace(arr):
    n = len(arr) - 1
    for i in range(len(arr)):
        k = random.randrange(0, n)
        arr[i], arr[k] = arr[k], arr[i]
    return arr
    
arr = [10, 20, 30, 40, 50, 60]
print(arr)
arr = randomize_in_pace(arr)
print(arr)

> [10, 20, 30, 40, 50, 60]
> [60, 10, 30, 20, 50, 40]

 

(3) 선택 방법 : On-line-maximum

인덱스 0부터 임의인덱스 K까지의 최고점 1인을 선정 후 K+1부터 N까지 최고점 이상 1인이 발견되면 즉시 종료한다.

import random

def on_line_maximum(arr):
    n = len(arr) - 1
    threshold = max(arr[0:random.randrange(0, n)])
    print("threshold : " + str(threshold))
    for i in range(len(arr)):
        if arr[i] > threshold:
            return arr[i]
    return 0

arr = [10, 20, 30, 40, 50, 60]
print(arr)
val = on_line_maximum(arr)
print(val)

> [10, 20, 30, 40, 50, 60]
> threshold : 40
> 50

 

 

[ 고용문제 ]

 

무작위 알고리즘을 적용하기 좋은 예는 고용문제이다. 인사팀의 고용문제에서 10명의 지원자가 있고 헤드헌터가 존재한다고 가정한다. 헤드헌터가 한 명의 인력을 인사팀에 소개하는 비용이 100원 발생한다. 이때 1번부터 10번까지 전부 면접을 보게 될 경우, 인사팀은 헤드헌터에게 1000원을 지급해야 한다. 인사팀은 비용도 줄이고 인력도 1~10번을 전부 보는 게 아니라 중간에 괜찮은 사람이 있으면 뽑길 원했다. 그래서 1~10번까지 일단 번호를 섞어서 확률적으로 괜찮은 인력이 중간쯤에서 만날 수 있을 것으로 예상한다.

 

코드에서 A~J까지의 사람이 있고 각자 점수가 있다. 해당 점수는 면접 후에 정해지는 점수라는 가정하에 39점을 넘을 경우 합격으로 한다. 먼저 A~J까지의 사람을 랜덤하게 섞어 'A' > 'B' > 'D' > 'G' > 'E' > 'H' > 'C' > 'F' > 'J' > 'I'라는 순서를 만들었다. 'A' > 'B' > 'D' > 'G'까지 면접을 보았고 점수는 39점을 넘지 못했다. 그리고 'E'를  면접보고 40점이 나왔고 'E'는 입사자가 되었다. 

import random

people = {"A":10, "B":11, "C":20, "D":7, "E":40, "F":22, "G":23, "H":2, "I":15, "J": 21}

people_keys = list(people.keys())
random.shuffle(people_keys)

print(people_keys)

winner = ""
winner_point = 0

for human in people_keys:
    if people[human] > 39:
        winner = people[human]
        print("면접자는 " + str(human))
        print("입사자는 " + str(human))
        break
    elif people[human] > winner_point:
        print("면접자는 " + str(human))
        print("모집공고 중입니다.")

> ['A', 'B', 'D', 'G', 'E', 'H', 'C', 'F', 'J', 'I']
> 면접자는 A
> 모집공고 중입니다.
> 면접자는 B
> 모집공고 중입니다.
> 면접자는 D
> 모집공고 중입니다.
> 면접자는 G
> 모집공고 중입니다.
> 면접자는 E
> 입사자는 E

 

결국 손해를 조금이나마 피해보려는 느낌의 알고리즘으로써 실제로는 알고리즘을 코드에 적용할 때도 확률을 높이기 위한 수단으로 밖에 사용되지 않는다. 하나의 For문이고 데이터가 많으면 많을수록 시간도 정비례하게 늘어나는 알고리즘으로 시간복잡도는 O(n)이다.