http://todayhumor.com/?science_29686 << 문제 : 심심하니까 문제 둘. 과반수!
먼저 문제 1, 2번을 보도록 하죠.
1번은 생각을 해본다면, 답이 3회인 것을 바로 알 수가 있죠.
첫번째와 두번째가 다르고, 두번째와 세번째가 다른 경우, 첫번째와 세번째가 같냐 다르냐에 따라서 과반이 결정되니까요.
2번은 조금 더 생각을 해야합니다.
잘 생각해보시면 3번의 질문으로 답을 낼 수 없을 때가 있다는 점을 알 수 있습니다.
그리고 정답인 4번의 질문은 다음과 같습니다.
1-2, 1-3을 비교 합니다.
만약 둘 다 같으면 과반. ( 1-2-3 이 모두 같죠 )
둘 중 하나만 다르면 1-4를 비교한 뒤에 과반 판단 가능. ( 왜 그럴까요? 잘 생각해봅시다. )
둘 다 다르다면, 2-3, 3-4 를 비교한 뒤에 과반 판단 가능. ( 이것도 마찬가지로 왜 그럴까요? )
자 그러면 마지막 3번 문제. 좀 더 일반적으로 생각해봅시다.
풀이를 N의 홀짝에 따라 따로 적는게 귀찮으므로, 일단 N이 짝수라고 가정하고 해봅시다.
1~N 번째의 숫자가 있습니다. 그렇다면 다음의 알고리즘을 사용해보아요.
1. 기준을 정합니다. 맨 처음에는 기준을 첫번째 수로 정합니다.
2. 기준이나 기준 뒤에 있는 수들 중, 기준과 같은 수가 몇 개인지 세는 카운터를 만들죠.
3. 카운터를 1로 합니다. ( 기준은 자기 자신과 같으므로 이미 같은걸 하나 찾았죠 )
4. 기준 뒤의 수들과 기준을 비교합니다. 만약 같다면 카운터+1, 다르면 카운터-1
5. 카운터가 음수로 떨어지면 그 때 비교한 그 수가 다시 기준이 됩니다.
6. 2~5를 반복해서 마지막 수 까지 비교를 합니다.
7. 잘 생각해보시면 마지막에 기준이었던 수만이 과반이 될 수 있는 자격을 가지고 있어요. ( Why? )
8. 그 기준과 나머지를 비교해서 과반인지 판정합니다.
이 알고리즘을 사용하되, 굳이 비교하지 않아도 답이 뻔한 경우를 빼주면 2N-4번 만에 과반을 판정할 수 있어요.
자 그러면 우리는 비교 횟수의 상한을 찾았어요! 답은 무조건 2N-4보다 작거나 같겠네요.
그러면 하한을 찾으면 답을 알 수 있겠죠. 하한은 상대자 논법을 사용하면 구할 수 있답니다.
나머지는 숙제로 해오세요 여러분~ 다음 문제에서 만나요.
숙제.
1. N이 짝수일 때 하한을 찾아보세요.
2. N이 홀수일 때 상한을 찾아보세요.
3. N이 홀수일 때 하한을 찾아보세요.
ps.
창식이와 친구는 아낀 라면으로 라면파티를 했다고 합니다.
FSM님의 축복이 가득하시길! Ramen.
글쓰기