주사위를 굴리는 풀이

주사위로 골라요

어떤 풀이는
다음에 무엇을 할지
주사위를 굴려 정해요.
생각해서 고르는 게 아니라,
그냥 운에 맡기는 거죠.
버튼을 누를 때마다
주사위가 한 번씩 굴러요.
무슨 눈이 나올지
미리 알 수 없어요.

누르면 주사위가 굴러요. (다음 눈은 미리 알 수 없어요)

왜 일부러 운에 맡길까요?
늘 똑같이 고르면,
누군가 그 버릇을 노려
일부러 어렵게 만들 수 있어요.
무작위로 고르면
그런 노림수를 피해가요.
다음 단계에서
진짜 쓸모를 봐요.

무작위 기준을 써요

빠른 정렬 중에는
기준 하나를 정해
그보다 작은 건 왼쪽,
큰 건 오른쪽으로 나누는
방식이 있어요.
그런데 늘 맨 끝값을
기준으로 삼으면,
이미 줄 선 입력에선
쪼개기가 한쪽으로만 쏠려
아주 느려져요.

늘 끝값 기준 vs 무작위 기준, 쪼개는 횟수를 견줘봐요. (한쪽 쏠림 = 느림)

기준을 무작위로 고르면
어떤 입력이 와도
한쪽으로만 쏠릴 일이
거의 없어져요.
나쁜 입력을 노린
함정도 통하지 않죠.
그래서 평균적으로
쪼개기가 골고루 되고,
정렬이 빨라져요.

많이 던져 어림해요

무작위는 어림에도 써요.
정사각형 안에
원을 하나 그려요.
그 안에 점을 마구 찍어요.
원 안에 든 점과
전체 점의 비율을 보면,
원이 차지한 넓이를
어림할 수 있어요.
점을 하나씩 찍어봐요.

점을 찍을수록 비율이 참값에 가까워져요. (원 안 점 / 전체 점)

점이 적을 땐
어림이 들쭉날쭉해요.
그런데 점을 많이 찍을수록
비율이 참값에 착 붙어요.
한두 번의 운은 못 믿어도,
수없이 던진 평균은
믿을 만하거든요.
이게 많이 던져
답을 어림하는 방법이에요.

확실성과 속도, 맞바꿔요

무작위 풀이는 공짜가 아니에요.
빠르고 간단한 대신,
매번 똑같은 답을
장담하진 못해요.
운이 나쁘면
가끔 느릴 수도 있죠.
무엇을 얻고
무엇을 내주는지,
양쪽을 눌러 견줘봐요.

얻는 것과 내주는 것을 눌러 견줘요. (빠름·간단 vs 같은 답 장담 못함)

그래서 무작위는
늘 좋은 게 아니라
알맞은 자리가 있어요.
빠르고 간단함이
약간의 불확실보다
더 값질 때 써요.
확실성을 조금 내주고
속도와 단순함을
사오는 거예요.

한눈에 정리해요

무작위 풀이를
한눈에 모아봐요.
주사위로 고르고,
무작위 기준으로 함정을 피하고,
많이 던져 답을 어림하고,
확실성과 속도를 맞바꿔요.
핵심을 차례로 눌러
스스로 정리해봐요.

핵심 네 가지를 차례로 눌러 정리해요. (주사위 · 무작위 기준 · 많이 던져 어림 · 맞바꿈)

운에 맡긴다고 하면
허술해 보이지만,
잘 쓰면 무작위는
빠르고 든든한 도구예요.
앞으로 데이터가 어마어마하게
많아지는 곳에서,
많이 던져 어림하는 이 생각은
더 크게 쓰여요.
그 이야기는 다음에요.