확률에 대해서 조금 배우다 보면 접하게 되는 문제 중 하나입니다.
제가 더 잘 설명할 수 있는 것은 아니니, 문제 자체에 대한 설명은 위에 걸어둔 링크를 참고해 주시기 바랍니다.
문제의 의미는 간단해서 부분확률에 관해 조금만 이해하고 있으면 금방 이해할 수 있습니다.
이 문제가 유명한 이유는, 어려워서가 아니라 직관적으로 생각했을 때 얻어진 답하고, '답'이 다르다는 데 있습니다. ( 물론 자신이 생각해서 얻은 답이 맞았다면 그분은 좀 더 '확률적인' 두뇌를 가지고 계신지도 모르겠네요. )
저도 이건 한 번 들어본 적이 있었지만, 알고리즘 수업에서 다시 듣고서 이해가 안가더군요.
설명이 틀렸다는 것도 아니지만, 그렇다고 바로 이해가 가는 것도 아니라서…….
결국, 그다음 시간이 프로그래밍 연습시간이니까 간단하게 프로그램으로 확인해보고자 했습니다.
문제자체가 쉬운 만큼, 프로그램도 쉬워서 문제없이 컴파일되고…….
결과에 깜짝 놀랐습니다.
“왜 선택을 안바꿨을때가 바꿨을때보다 오히려 2배 좋은거지?”
뭐... 이건 간단한 실수였지만요.
결국 바꿨을 때가 더 좋다고 프로그램도 그러고, 받아들이기로 했습니다.
[codes]
#include<stdio.h>
#include<stdlib.h>
#define LEN 1000000
int arr[LEN];
int main()
{
int a,bc[2],select,statics,dynamics;
int i,seed;
scanf("%d",&seed);
for(i=0;i<LEN;i++)
arr[i]=rand();
i=statics=dynamics=0;
while(i<LEN-3)
{
a=arr[i++];
bc[0]=arr[i++];
bc[1]=arr[i++];
if(a==bc[0]||bc[0]==bc[1]||bc[1]==a)
continue;
if(bc[0]<bc[1])
select=1;
else
select=0;
if(a<bc[select])
dynamics++;
else
statics++;
}
printf("static: %d\n dynamic: %d\n",statics,dynamics);
}
[/codes]
Haskell로도 써보려고 했는데, 아직 Rand 모듈 사용법을 공부 안해서 다음에...
Posted by SCiRE
