어떻게 주사위를 굴리는 풀이

주사위로 고른다

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

누르면 주사위가 구른다. 다음 눈은 미리 알 수 없어요.

왜 일부러 운에 맡길까? 늘 똑같은 방식으로 고르면 누군가 그 버릇을 노려 일부러 어려운 입력을 만들 수 있다.
무작위로 고르면 그런 노림수를 피해 간다.
진짜 쓸모는 다음 단계에서 드러나요.

무작위 기준을 쓴다

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

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

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

많이 던져 어림한다

무작위는 어림에도 쓴다. 정사각형 안에 원을 넷으로 나눈 한 조각, 곧 사분원을 그리고 그 안에 점을 마구 찍는다.
사분원 안에 든 점이 전체 점 가운데 얼마인지 보면 사분원이 차지한 넓이를 어림할 수 있어요.
점을 하나씩 찍어 보자.

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

점이 적을 때는 어림이 들쭉날쭉하다. 그런데 점을 많이 찍을수록 비율이 참값에 착 붙는다.
한두 번의 운은 믿을 수 없어도 수없이 던진 평균은 믿을 만하기 때문이다.
이것이 많이 던져 답을 어림하는 방법이에요.

확실성과 속도를 맞바꾼다

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

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

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

한눈에 정리

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

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

운에 맡긴다고 하면 허술해 보이지만, 잘 쓰면 무작위는 빠르고 든든한 도구다.
데이터가 어마어마하게 많은 곳일수록 많이 던져 어림하는 이 생각이 더 크게 쓰인다.
다음 레슨에서는 점과 선으로 이어진 세상, 그래프로 넘어가요.