대학생 자기계발! 취업에 도움이 되는 알고리즘 문제

IT 회사 신입사원 면접 때 단골손님처럼 등장하던 문제 5개는?

 

4월 넷째 주 : 약병 찾기 [클릭]

4월 마지막 주 : 빠진 숫자

5월 첫째 주 : 과반수 넘는 구슬

5월 둘째 주 : 사이클

5월 셋째 주 : 한붓그리기

 

빠진 숫자

 

1~10 사이의 서로 다른 숫자가 적혀있는 10개의 구슬이 있다. 그중에서 1개의 구슬을 빼고, 9개의 구슬을 주머니에 담았다. 주머니에 담긴 구슬만 보고, 담지 않은 구슬에 적힌 숫자를 찾는 것이 문제이다.

 

 

---

 

 

 

위 그림처럼 주머니에서 구슬을 하나씩 꺼내어 구슬에 쓰인 숫자를 표의 해당하는 곳에 표시해보자. 마지막까지 표시되지 않은 곳의 숫자가 바로 우리가 찾는 숫자이다.

 

그런데 만일 구슬이 많아서 표를 만들어 사용할 수 없다면 어떻게 빠진 숫자를 찾아야 할까?

(단, 종이 한쪽 귀퉁이에 덧셈이나 뺄셈을 하는 것은 허용된다.)

 

일단 이해하기 쉽게 구슬을 10개로 제한하여 생각해보자. 빠진 숫자는 1+2+ ... + 10 = 55에서 주머니 속의 9개의 구슬에 적힌 숫자들의 합을 뺀 값과 같다. 아래의 그림을 보면 이해하기 쉬울 것이다.

 

 

 

이와 같이 표를 만들지 않더라도 간단한 덧셈, 뺄셈을 이용하면 빠진 숫자를 찾을 수 있다 :)  ♥ 끝 ♥

 

---

 

어제보다 1mm 똑똑해진 느낌을 받으셨나요? ^_^

다음 주에는 수요일에 새로운 문제를 가지고 올게요! 

 

 

★이 글은 <알고리즘 첫걸음>을 참고하여 작성되었습니다.