안녕하세요. 무사히 2학기를 시작하셨나요?
8월 중순이면 개학이라 지금은 본격적으로 진도를 나가실 때가 아닐까 싶습니다.
이번 호는 컴퓨팅 사고력과 반복문, 배열을 익힐 수 있는 방법에 관해 이야기해 보겠습니다.
컴퓨팅 사고력 기르기
프로그래밍은 읽고, 쓰고, 말하기처럼 학생들이 살아가는 데 필요한 필수 능력이 되었습니다.
그러 왜? 프로그래밍을 배워야 할까요?
정보 교육에서 무엇을 길러 주어야 할까요?
저는 컴퓨팅 사고력이 핵심이라고 생각합니다.
코딩 교육, 프로그래밍 교육, SW-AI 교육, 정보 교육…
이전부터 교육해 오고 있었는데 관심이 쏠리면서 갑자기 많은 이름이 붙었지만, 어쨌든…
교육 현장에서 어떤 역량을 길러줄지와 교육 목적을 분명히 하고
학생들을 잘 파악하는 교육 현장의 선생님들이 정보 교육을 해 나가면 된다고 생각합니다.
프로그래밍을 하려면 알고리즘을 잘 생각해야 합니다.
알고리즘이라고 하면 이름이 붙은 알고리즘들이 생각나기도 하지만 알고리즘의 본질적인 뜻은 ‘논리적, 절차적으로 문제를 해결해 나가기 위한 절차’이고 이러한 알고리즘을 생각하다 보면 컴퓨팅 사고력이 키워지는 것이지요.
이 생각의 연장선에서 저는 동적 계획법이 학생들에게 컴퓨팅 사고력을 키워주기에 효과적인 프로그래밍 기법이라고 생각합니다.
반복문과 조건문, 배열을 수업하실 때 생각할 문제를 제시한 후 구조화시키고 프로그래밍 하게끔 하면 생각하는 힘을 길러줄 수 있을거예요. ~^^
동적 계획법(DP; Dynamic Programming)
동적 계획법은 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식으로 간단히 말해 부분에서 구했던 답을 다음 단계에서 다시 이용하는 문제 해결 방법이라고 할 수 있습니다.
답을 구하기 위해서 했던 계산을 또 하고, 또 하고, 반복해야 하는 문제의 구조를 최적 부분 구조(Optimal Substructure)라고 하는데요. 이런 구조로 되어 있는 문제를 프로그래밍할 때 동적계획법이 효과적입니다. 동적계획법을 이용하여 작은 부분 구조를 잘 찾아내면 배열과 반복문으로 코드를 구현할 수 있습니다.
배열, 반복문으로 피보나치수 구하기
피보나치 수열에 대한 정의는 아래 그림과 같습니다.
반복문과 배열을 이용한 코드
#include <stdio.h>
int dp[100];
int fibo(int n)
{
dp[0] = 0;
dp[1] = 1; // 피보나치 수열 초기 시작 값
for (int i = 2; i <= n; i++) // 2부터 시작해서 n까지 반복
{
dp[i] = dp[i - 1] + dp[i - 2];
// i 번째 수는 이전(i-1)과 그 이전(i-2_)의 두 수의 합
}
return dp[n];
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", fibo(n));
return 0;
}
C
복사
재밌게 생각하며 풀어볼 수 있는 타일 채우기
동적계획법의 매력과 신기함을 알 수 있는 타일 채우기 문제를 추천합니다. ^^
단계별로 생각해 나가면 어렵지 않습니다.
문제
세로는 2행으로 고정되어 있고 옆으로 열이 늘어나는 빈 타일을 1X2, 2X1, 2X2 모양의 블록을 이용해서 채울 수 있는 경우의 수를 구해보자.
기저 상태 : dp[1] = 1, dp[2] = 3
#include <stdio.h>
int dp[1000], n;
int main()
{
scanf("%d", &n); // 6
dp[1] = 1;
dp[2] = 3;
for( int i = 3; i <= n; i++)
dp[i] = (dp[i-1] + dp[i-2] * 2) % 10007;
// 백준 문제에서는 출력의 조건으로 아래 조건이 있으므로 %10007를 붙인다.
// 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를
// 10,007로 나눈 나머지를 출력.
// dp[i] = dp[i-1] + dp[i-2] * 2
printf("%d", dp[n]);
return 0;
}
C
복사
코딩, 프로그래밍 교육이 문법 교육이 아닌 컴퓨팅 사고력을 길러주기 위한 교육이 되도록 하기 위해
‘생각’해 보도록 하는 기회를 학생들에게 많이 주면 좋겠습니다.
“왜 그러지? 어떻게 해야 하지? “
그걸 찾아내는 경험을 많이 할수록 생각하는 힘이 길러질 수 있지 않을까 합니다.
** 더 알아보기
n-보나치수 구하기
#include <stdio.h>
int f(int x, int y)
{
int i, j, t = 0;
if (x >= y)
return 1;
else
{
for (i = y - 1; i >= y - x; i--) {
j = f(x, i);
t += j;
}
return t;
}
}
int main()
{
int x, y;
scanf("%d %d", &x, &y);
printf("%d\n", f(x, y)); // x-보나치수열, y번째 항
return 0;
}
C
복사