[컴퓨팅사고력] 길동 형사를 도와 주세요.

길동이는 어려서 부터 꿈이 나쁜사람을 잡는 형사였습니다. 어른이 되어서 이제 막 형사가 된 길동이는 잠복 수사를 하게 되었습니다. 범인의 인상착의와 비슷한 사람이 길동형사 앞을 지나가서 길동형사는 그 사람을 불러 세우고 불심검문을 하였습니다. 하지만 그 사람이 불러준 주민번호를 전산시스템에 입력하여 조회를 하는데 아무리 기다려도 조회가 되지 않습니다. 현재 길동형사가 조회하는 시스템은 다음과 같이 구성이 되어 있습니다. 1) 우리나라 인구 5000만명의 주민등록 번호가 모두 등록이 되어 있습니다. 2) 등록된 정보는 주민번호가 빠른 순서 부터 순서대로 정렬이 되어 등록이 되어 있습니다. 3) 시스템에서 조회되는 속도는 1초에 100건씩을 조회하여 처리 됩니다. 4) 조회되는 순서는 앞에서 부터 순차적으로 검색합니다. 따라서 길동형사가 불심검문을 위해 세운 사람의 주민번호가 5000만번째 위치에 존재한다고 하면 최대 소요시간은 50만초 가 걸릴 것입니다. 이것을 시간으로 계산하면 최대 약 138시간 정도가 걸립니다. 우리가 처리 되는 프로세스를 바꿔서 길동형사를 도와 줄 수는 없을까요?

 

해법알아보기

1) 주민번호가 순서대로 정렬이 되어 있다는 것에 착안을 합니다.
2) 순차적으로 조회 하지 않고 절반 위치를 조회해 봅니다.
3) 만약 절반 위치가 주민번호라면 결과를 출력합니다. 아니라면 그 사람의 주민번호가 중간 위치보다 작다고 하면 해당 위치보다 앞쪽에서 검색을 하면 되고 아니라면 해당 위치보다 뒤쪽에서 검색을 합니다.
4) 이렇게 반복을 하게 된다면 다음과 같은 시간 안에 해결이 가능합니다.

1회 - 5000만개 중에서 검색
2회 - 2500만개 중에서 검색
3회 - 1250만개 중에서 검색
...
25회 - 2개 중에서 검색
26회 - 1개 중에서 검색

26회 만에 검색이 완료 됩니다. 늦어도 3초 안에 해결이 되겠네요.^^

 

컴퓨팅 사고력

컴퓨터 과학에서는 대용량의 가공된 대용량의 데이터를 찾는 방식으로 이진 탐색의 기법을 사용하고 있습니다.

달까지의 거리가 384400km 라고 하면 0.1mm의 신문을 몇번 접으면 달까지 도착 할것인가 라는 문제에서 이진 탐색의 속도를 찾을 수 있습니다.

달까지 신문을 몇번 접으면 될지 한번 계산해 볼까요?

0.1mm 를 한번 접으면 0.2 mm 가 됩니다.

0.2mm 를 한번 접으면 0.4 mm 가 됩니다.

0.4 mm 를 한번 접으면 0.8 mm 가 됩니다.

이렇게 접다 보면 언제 달에 도착하지? 라고 의아해 할 수도 있는데요~

실제로 계속 접다 보면 2배씩 증가 되는 규칙이 되기 때문에 다음과 같은 규칙이 있음을 알 수 있습니다.

0.1 mm 가 3번 접으면 0.8 mm 가 되는 원리는 0.1 * 2^3 = 0.8 이 되는 원리입니다.

즉 2의 거듭제곱 횟수가 접은 횟수가 되는 것입니다.

그렇다면 384400km 를 mm 로 변환을 하면 384400000m = 384400000000cm = 3844000000000 mm 인것을 알 수 있습니다.

따라서 0.1mm * 2^x >= 3844000000000 인 x 를 찾아 주면 되므로 

2^x >= 38440000000000 의 값이 됩니다.

2^45 = 35,184,372,088,832 이므로 46번만 접으면 됩니다.

이렇게 두배씩 증가될때 처음에는 증가되는 속도가 얼마 안되네 라고 생각할 수 있지만 숫자가 커질 수록 기하급수라는 말을 실감하게 될 수 있습니다.

 

컴퓨터 과학에서는 이러한 원리를 활용하여 데이터 탐색 기법으로 활용을 하고 있습니다.

이러한 기법을 이진 탐색이라고 하는데 이러한 기법 외에 삼진탐색 기법도 있지만 실제로 사용하는 기법으로는 삼진탐색보다 이진탐색을 더욱 많이 활용하고 있습니다.

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.

 

인천 서구 검단신도시 원당컴퓨터학원