자기계발 추천도서, 알고리즘 문제 풀고 어제보다 똑똑해지자!

어제보다 1mm 똑똑해진 느낌적인 느낌

생각의 폭이 넓어지는 느낌

 

언제 느껴보셨나요? 기분 좋은 느낌인 건 알겠는데 언제 어디서 경험했는지 모르시는 분들이 많이 계실지도 몰라요. 가볍게 몸은 풀어봤어도 가볍게 두뇌를 풀어보는 일은 자주 있는 일이 아니니까요. 앗! 저만 그런거였나요? ^_^

매일 반복되는 하루 중 단 몇 분이라도 새로운 뭔가를 시도한다면 어제보다 성장한 내가 될 수 있대요. 제목이 마음에 들어서 클릭하신 분이라면, '오늘의 새로운 뭔가'를 <가볍게 두뇌를 풀어보는 뭔가>로 해볼 수 있는 분이라는 생각이 들었어요!! 그렇다면 생각의 폭이 훅 넓어진 느낌 받으러 출발합니다.

IT회사 면접에도 자주 등장했던 알고리즘 문제라고 하니, 취업을 준비하시는 분들도 꼭 읽어 보세요.

그림으로 쉽게 이해할 수 있으니 걱정마시고 마음 편하게 읽으시면 됩니다 ^_^

 

 

---

 

 

잘못 만들어진 알약 찾기

 

같은 수의 알약이 담긴 10개의 병이 있다. 9개의 병에 들어있는 알약은 개당 1g인데 어느 한 병에만 1.1g인 알약들이 들어있다. 즉, 10개의 병들 중 1개의 병에는 잘못 만들어진 알약들이 들어있다. 저울을 마음대로 여러 번 사용할 수 있다면, 각 병에서 알약 1개씩 꺼내어 저울에 달아보면 언젠가는 저울이 1.1g을 가리킬 것이므로 잘못된 약병을 찾을 수 있다.

 

 

---

 

 

그런데!! 저울을 한 번만 사용하여 잘못된 약병을 찾아야 한다면 문제가 그리 쉬워 보이지 않는다.

 

 

 

---

 

 

저울을 단 한 번만 달아야 하기 때문에, 모든 병에서 알약을 꺼내어 저울에 달아보지 않고서는 무거운 알약이 어느 병에 들어있는지 알 수 없다. 만약 모든 병에서 1개의 알약을 꺼내어 저울에 달아보면 10.1g이 될텐데, 그 1.1g짜리 알약이 어떤 약병에서 나왔는지 알 수 없다.

 

 

---

 

 

위와 같은 시도의 결과를 살펴보면 각 병에서 다른 수의 알약을 꺼내야 한다는 것을 알 수 있다. 또한 병에서 몇 개의 알약을 꺼냈다는 것을 알고 있어야 잘못된 약병을 찾을 수 있다. 약병을 나란히 세워놓고, 약병에 번호가 좌에서 우로 1,2,3, ... 10으로 붙여져 있다고 생각하자.

그리고 첫 번째 병에서는 1개의 알약을 꺼내고, 두 번째 병에서는 2개의 알약을 꺼내고,  . . .  열 번째 병에서는 10개의 알약을 꺼낸다.

 

 

---

 

 

꺼낸 알약의 수는 1 + 2 + 3 + … + 9 + 10 = 55이며, 55개의 알약을 한꺼번에 저울에 올려 달아보면, 다음과 같이 어느 약병에 무거운 알약이 들어있는지 알 수 있다.

•  55.1g을 가리키면 
첫 번째 병이 잘못된 약병이다. 왜냐하면 첫 번째 병에선 1 알만 꺼냈으니 1.1 × 1 = 1.1g이다. 

•  55.2g을 가리키면 
두 번째 병이 잘못된 약병이다. 왜냐하면 두 번째 병에선 2 알만 꺼냈으니 1.1 × 2 = 2.2g이다. 

•  55.9g을 가리키면 
1.1 × 9 = 9.9g이므로 아홉 번째 병이 잘못된 약병이다. 

•  56.0g을 가리키면 
마지막 약병이 잘못된 약병이다. 왜냐하면 마지막 약병에 선 10알을 꺼냈으므로 총 1.1 × 10 = 11g이 마지막 약병에서 꺼낸 알약의 무게이고, 나머지 병들에서 꺼낸 알약들의 무게는 1 + 2 + … + 9 = 45g이기 때문이다.

 

 

---

 

 

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

다음 주 월요일에도 저와 함께 재미있는 두뇌 운동 함께 해요! ♥

 

 

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

 

4월 넷째 주 : 약병 찾기

4월 마지막 주 : 빠진 숫자

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

5월 둘째 주 : 사이클

5월 셋째 주 : 한붓그리기

 

---

 

 

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