Page 41 고등학교 프로그래밍 교과서

미션 해결하기

가게에서 50 mg의 추 6개와 40 mg의 추 1개를 사 왔다. 그런데 추를 섞어서 구별할 수 없게 되었다. 양팔 저울을
이용하여 40 mg의 추를 가장 빨리 찾는 방법을 알아보자.

문제 분석

문제: 7개의 추 중 무게가 다른 하나인 40 mg 추를 찾아야 한다.
조건: 양팔 저울을 이용할 수 있으며, 가능한 저울을 적게 사용하여 찾아야 한다.

알고리즘 설계

A 알고리즘: 1번과 2번 추를 비교한다. 만일 무게가 같다면, 1번과 3번 추를 비교한다. 이때 무게가 같다면, 나머지 추를 차례로 1번과 비교한
다. 무게가 다르다면, 무게가 적은 쪽이 40 mg이다.

B 알고리즘: 1번과 2번 추를 비교한다. 만일 무게가 같다면, 3번과 4번 추를 비교한다. 이때 무게가 같다면, 5번과 6번 추를 비교한다. 만일 무
게가 같다면, 나머지 7번 추가 40 mg이다.

C 알고리즘: 1, 2, 3번 추와 4, 5, 6번 추를 동시에 올려 비교한다. 만일 무게가 같다면 7번 추가 40 mg이다. 만일 어느 한쪽( 4, 5, 6번 쪽)
이 가볍다면 가벼운 쪽 ( 4, 5, 6) 중 무작위로 두 개를 골라 무게를 비교한다. 만일 한쪽이 가볍다면 그것이 40 mg 추이고,
같다면 남아 있는 추가 40 mg이다.

알고리즘 분석 및 선택

알고리즘 최대 비교 횟수
A 6회
B 3회

C 2회

설계한 알고리즘 중에서 최대 비교 횟수를 분석한 결과, 가장 정확하고 빠른 알고리즘은 C 알고리즘이다.

스스로
스스로
해결하기 다음 자연어로 표현된 알고리즘을 순서도로 표현해 보자.
해결하기

자연어 순서도

• 두 수 a, b를 입력받는다.
• a, b를 비교하여 큰 수에서 작은 수를 뺀 값을 c에 저장
한다.
• c를 출력한다.

3. 알고리즘 39

(책)2015프로그래밍-교과서3차심의본 본문.indb 39 2017-09-05 오후 4:15:48