[컴퓨팅 사고력] 투명띠를 반씩 접어서 한개의 사각형 만들기

원당이는 다음과 같이 1 부터 32까지 적힌 투명띠를 가지고 있다.

이 투명띠를 왼쪽으로 절반씩 접어서 한개짜리 사각형으로 만들려고 한다.

즉 한번을 접게 되면 1~16이 아래에 있고 32~17이 위에 있게 된다.

이 투명띠는 고무줄과 같이 탄성이 좋아서 접히는 위치는 접히는 횟수의 높이에 관계 없이 정확히 접힌다고 가정하자.

1) 몇번만 접으면 한개의 사각형으로 만들 수 있겠는가?

2) 맨 위에 적힌 번호는 무엇인가?

 

 

[문제풀이]

맨아래/ 맨위 로 표현을 해 보면 다음과 같은 순서로 나타날 것이다.

1단계) 1~16/32~17

2단계) 1~8/16~9

3단계) 1~4/8~5

4단계) 1~2/4~3

5단계) 1~1/2~2

 

즉 5번이면 한개의 사각형을 만들 수 있고 맨 위에 적힌 번호는 2이다.

 

컴퓨팅 사고력

이 문제는 컴퓨팅 사고력에서 이진탐색의 원리에 대해 고민 할 수 있는 문제이다.

1~32 까지의 데이터가 있다고 하면 순차적으로 검색을 하게 되면 최악의 검색 조건으로 32를 찾는 경우 32번을 검색해야 결과값을 얻을 수 있지만~

우리가 사전에서 단어를 찾을때 절반의 위치를 먼저 찾아 보고 내가 찾으려고 하는 단어가 앞쪽에 있는지 뒷쪽에 있는지 확인 하여 절반씩을 버리면서 찾는 방법이 이진탐색이다.

절반 위치 16번째를 검색해서 16번째가 내가 찾는 값이라면 성공,내가 찾는 값이 앞쪽에 있다고 하면 뒤에 17~32 를 버리고 1~15번째에서 찾는 방법으로 절반씩 버리면서 찾는다면 최악의 조건으로 5번 만에 찾을 수 있다.

 

이렇게 이진탐색을 하게 되면 찾는 횟수는 log₂N 의 횟수만에 검색이 가능한데 이것은 2^N  의 갯수에서 절반씩 나누게 되므로 이 N의 수를 찾는 로그 함수의 횟수가 같아지는 것을 알 수 있다.

따라서 우리나라 전체 인구수 5000만명이라고 하면 5000만명 안에 나라는 사람의 주민번호를 찾기 위해서는 이진탐색을 활용한다고 하면 26번 안에 찾을 수 있다.(2^26 = 67108864)

단. 이진탐색을 활용하기 위해서는 자료가 모두 순서대로 정렬이 되어 있어야 한다는 조건이 필요하다.

 

[인천 서구 원당컴퓨터학원]

원당컴퓨터학원에서는?

1. 4차 산업 시대의 흐름은 컴퓨터를 얼마나 이해하느냐에 따라 삶의 질이 틀려 질 수 있다는 것을 항상 염두에 두고 있습니다.

2. 알고리즘은 프로그래밍의 근원이 되는 문제해결 능력이며, 머신러닝은 IoT등에 의해 모여진 데이터를 활용하는 기법입니다.

3. 이에 따라 초,중,고 학생들이 알기 쉽게 이해하는 인공지능 부터 알고리즘까지 학생들의 실력에 맞춰 수업을 진행중에 있습니다.

4. 현재 초등학생이 고등학생이 되는 때에는 고교학점제 도입에 따라 자신이 전공하고자 하는 특기가 크게 부각 될것입니다.

5. IT 업체중 규모가 큰 곳에서는 코딩테스트(알고리즘테스트)로 블라인드 면접을 수행하는곳이 늘고 있습니다.

6. 미래 IT를 꿈꾸는 학생들의 산실이 되기 위해 항상 최선을 다하는 원당컴퓨터학원이 되겠습니다.

 

※ 정보영재 혹은 인공지능 관련 수업에 관해 궁금하신 분은 문의(032-565-5497) 주세요.

 

 

원당컴퓨터학원 커리큘럼

- OA : 학교 수행 평가에 꼭 필요한 컴퓨터 활용능력 향상

- IT 자격증 과정 : 취업대비,대학생인증제,승진을 위한 국가공인 자격증 취득과정

- 정보영재 : 정보올림피아드 및 알고리즘 대회/소프트웨어특기자전형/디미고 특별전형 대비/코딩테스트 대비를 위한 알고리즘 과정

- 프로젝트반 : 응용프로그래밍/웹프로그래밍/앱프로그래밍 등을 통해 직접 만들어 보면서 컴퓨터 프로그래밍 이해(소프트웨어 학생부종합전형/특성화고(디미고,선린고등) 특별전형대비)

- 인공지능 : 인공지능의 이해 및 실습을 통해 빅데이터 가공(4차 산업 시대의 축이 되는 인공지능 시대를 대비)

- 일반고,과고,영재고,특성화고,컴퓨터학과(SW) 대학생을 위한 내신대비 : python,java,c++,자료구조,알고리즘,이산수학