[컴퓨팅 사고력] 2 * 10 크기의 벽을 채우는 경우의 수를 구해 보자.

다음과 같이 2 * 10 크기의 벽이 있는데 원당이는 1*2 짜리 타일 10개를 벽에 붙여야 합니다.

원당이는 갑자기 이 타일을 동일한 모양이 아니고 세우거나 눕히거나 해서 붙이는 경우의 수가 궁금해 졌습니다.

만약 2 * 1 짜리 벽이라면 다음과 같이 세워서 붙이는 경우 한가지 밖에 없습니다.

하지만 2*2짜리 벽이라면 다음과 같이 2가지 경우의 수가 생깁니다.

두개를 세로로 세우는 경우와 가로로 눕히는 경우

그렇다면 원당이를 도와서 2*10크기의 벽에 1*2짜리 타일 10개를 벽에 붙이는 경우의 수를 여러분이 구해 주세요.

 

 

[문제풀이]

1단계) 2*1짜리 벽이라고 하면 세로로 세울 수 있는 경우의 수 1가지

2단계) 2*2짜리 벽이라고 하면 2*1짜리 벽에 2*1짜리 벽이 더 추가 되는 개념이므로 2*1짜리에 세워서 놓는 경우의 수 1가지 + 2*0 짜리 벽에 두개를 가로로 눕혀서 놓는 경우 1가지 = 2가지

 

3단계) 2*3짜리 벽이라고 하면 2*2짜리 벽에 세로로 세울 수 있는 경우가 있으므로 2*2짜리 놓는 경우의 수 2가지 + 2*1짜리 벽에 두개를 가로로 눕혀서 놓는 경우 1가지 = 3가지

위의 붉은 색은 2개짜리 경우이므로 2가지 아래 붉은색은 1개짜리이므로 1가지

이렇게 작은 단위로 쪼개어서 생각하면 2*4 짜리는 2*3짜리 만드는 경우와 2*2짜리 만드는 경우의 합이라는 것을 알 수 있다.

이것을 표를 그려 보면 다음과 같이 만들 수 있다.

따라서 정답은 89 가지

이 문제를 분석 해 보면 피보나치 수열이 됨을 확인 할 수 있다.

 

컴퓨팅 사고력

수학과 컴퓨터과학에서 동적계획법(Dynamic Algorithm) 또는 점화식이라고 표현하는 풀이 방법이 있습니다.

이러한 동적계획법은 위키백과 설명에 따르면 다음과 같이 정의 되어 있습니다.

동적계획법은 문제를 여러개의 하위문제로 나누어 푼 다음 그것을 결합하여 최종적인 목적에 도달하는 것이다.

 

위의 문제를 예로 들어 보면 가장

최소 단위로 2*0짜리를 만드는 경우의 수 1 ,2*1짜리를 만드는 경우의 수 1

위의 두개를 이용해서 2*2짜리 만드는 규칙이 2*0 에서 1가지가 나오는 것이고 2*1 에서 1가지가 나오는 규칙을 찾아 그 규칙을 이용해서 최종적인 목적에 도달하게 됩니다.

 

위와 같이 어떤 문제를 쪼개어서 더 쪼갤수 없는 단위까지 쪼갠 다음 그 다음 것이 만들어 지는 원리를 파악해서 그것을 부분문제 반복과 최적 반복 구조를 이용하여 풀어 나가는 원리가 동적계획법입니다.

 

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

 

 

 

원당컴퓨터학원에서는?

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

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

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

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

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

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

 

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

 

 

원당컴퓨터학원 커리큘럼

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

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

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

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

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

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