SZ-F-R-005(Rev.3)                                                                                                      호기심의 시작 사이언스존                                                                                                     A4(210mm ×297mm)

◎ 미리생각해보기

여러 명의 친구와 약속을 정해본 적이 있나요? 가장 힘든 점은 무엇이었나요?

여러 명의 사람과 약속을 정하기 위해서는 사람들의 일정을 파악한 다음 모두가 만족할 수 있는 시간을 정해야합니다. 친구A의 학원시간, 친구B의 병원시간 등 다른 일정과 겹치지 않고 공통적인 여유시간을 찾아야하기 때문입니다.

이렇듯 여러 명이서 약속정하기, 시간표 정하기, 특정 교실을 여러 팀이 사용하기 등 어떤 일을 수행할 때 중복되지 않도록 결정하는 문제를 최적화 문제라고 합니다. ‘지도색칠하기’문제는 최적화 문제 중 대표적인 문제로, 국경을 맞닿고 있는 나라끼리 색깔이 겹치지 않도록 지도를 색칠하는 문제입니다. 최소한의 색깔로 지도를 완성하기 위해 필요한 색깔은 몇 가지일까요?

사실 이미 아무리 복잡한 지도라도 4가지의 색깔만 있으면 지도를 완성할 수 있다는 것이 수학자들에 의해 증명되었습니다. 덕분에 우리는 수많은 테스트를 해보지 않아도 4가지 색으로만 지도를 완성할 수 있게 되었답니다.

◎ 실험 전 주의사항

1. 실험에 포함된 작은 부품이나 시약 등은 삼키지 않도록 주의합니다.

2. 실험에 포함된 준비물은 실험 외 다른 용도로 절대 사용하지 않도록 합니다.3. 실험용 도구와 시약으로 절대 장난치지 않도록 합니다.

4. 날카로운 도구를 사용할 때는 다치지 않도록 주의합니다.

5. 실험 후에는 주변을 정리하고 손을 깨끗이 씻습니다.

◎ 실험 전 반드시 확인하기

도안이 찢어지지 않도록 조심해주세요.

구슬을 잘못 붙였을 경우 최대한 도안이 손상되지 않도록 조심해서 뜯어주세요.

물고기 도안과 꾸미기 도안을 뜯은 다음, 그림과 같이 물고기 도안에 양면테이프를 붙입니다.	이웃하는 구슬끼리 색이 겹치지 않도록 구슬을 붙입니다.

◎ 실험방법

SZ-F-R-005(Rev.3)                                                                                                      호기심의 시작 사이언스존                                                                                                     A4(210mm ×297mm)

그림과 같이 물고기의 입부분을 만들고 인형눈을 붙여 물고기를 완성합니다.	종이끈에 종을 묶은 다음 투명테이프를 이용해 그림과 같이 도안 뒷면에 붙입니다.

종이끈의 끝부분에 그림과 같이 큐방을 묶어 연결합니다.	투명테이프를 이용해 꾸미기도안을 종이끈에 붙여 물고기풍경을 완성합니다.

◎ 실험결과 및 생각해보기

일상생활에서 마주하는 최적화 문제에는 어떤 것들이 있을까요?

⇒ 시간표 정하기, 2대의 차에 8명이 나누어 타기, 약속 정하기 등 한정된 자원으로 문제를 해결해야하는 모든 일들

2. 세계지도를 완성하기 위해 필요한 최소한의 색깔은 몇 가지인가요?

⇒ 4가지

◎ 원리이해

(1) 최적화 문제

일상생활에서 발생하는 많은 문제들은 제한된 조건을 고려하여 최선의 방법으로 해결됩니다. 그래서 합리적인 문제해결 방법은 최소한의 자원으로 문제를 해결할 수 있는 최적화 과정이라 할 수 있습니다. 컴퓨터 과학에서도 물리적인 제한, 즉 저장 용량의 제한, 시간의 제한 등으로 최적화를 위한 노력이 필요합니다. 이러한 최적화 문제들의 상당부분은 ‘그래프 색칠하기’로 실마리를 풀 수 있었습니다. 그래프 색칠하기 문제는 특정 그래프 채색에 필요한 최소한의 색깔 수를 찾아 최소한의 비용으로 최대의 효과를 찾는 것 입니다. 컴퓨터 과학적 문제해결방법인 ‘그래프 색칠하기’를 실생활에 있을 법 한 문제에 적용하여 문제를 해결할 수 있습니다.

(2) 그래프 색칠 문제

① 지도 색칠하기 – 4색 정리

지도 색칠 문제는 그래프 색칠 문제 중 하나로, 세계지도를 그릴 때 인접한 두 나라에는 서로 다른 색을 칠해야 하는데 이때 최소 몇 가지 색으로 지도를 완성할 수 있는지에 대한 문제입니다.

이 문제는 1850년도에 4가지 색만 있으면 충분하다는 4색정리가 등장한 이후로 거의 1세기 동안 증명되지 못하다가 1976년에 컴퓨터를 이용한 아펠과 하켄 교수의 연구에 의해 증명되었습니다.

② 그래프

그래프 색칠하기에서 그래프는 우리가 흔히 알고 있는 숫자 데이터를 표현하기 위한 막대그래프와 같은 차트를 의미하는 그래프와는 다른 의미입니다. 여기서 말하는 그래프란 컴퓨터 과학에서 쓰이는 용어로, 객체를 나타내는 노드(node)라 불리는 원을 사용해서 표현합니다. 객체와 객체 사이에 선을 그어서 객체 사이에 상관관계가 있다는 것을 추상적으로 나타내게 됩니다.

예를 들어, 지도를 그래프로 표현하면 다음과 같은 형태가 됩니다.

각각의 나라는 노드로 표현되고 국경을 접하고 있는 나라의 경우 선을 그어 관계가 있음을 표현합니다.

③ 그래프 색칠 문제

그래프색칠하기

그래프 색칠 문제는 그래프의 꼭짓점이나 변 등에 색을 칠하는 문제로, 이때 색을 칠하는 방법에 여러 제약이 생기게 됩니다. 예를 들어, 그래프의 꼭짓점에 색을 칠하면 인접한 두 꼭짓점에는 다른 색깔을 칠해야만 합니다. 현실의 여러 대상들은 그래프로 추상화 할 수 있습니다. 그래프를 색칠하는 것은, 서로 인접한 두 정점이 같은 색을 같지 않도록 색칠 하는 것 입니다.

이 그래프를 색칠하는 문제는, 다양한 스케쥴링 문제 혹은 컴파일러의 레지스터 배치, 패턴 매칭, 시험/수업 시간표 작성 등 다양한 문제를 해결할 수 있습니다.

④ 활용

본 실험에서는 물고기 비늘을 꾸미는 방법에 4색 정리를 적용해 그래프 색칠 문제를 활용하였습니다. 서로 이웃한 물고기 비늘의 색이 겹치지 않도록 꾸미기 위해서는 4가지 색만 있으면 충분하다는 것을 알 수 있습니다.

학습목표

최적화 문제에 대해 알아보고, 문제를 해결하는 방법 중 하나인 그래프색칠하기를 활용해 물고기 풍경을 완성해봅시다.

실험날짜          년      월      일

학년   반    이름 :

여러 명의 친구와 약속을 정해본 적이 있나요? 가장 힘든 점은 무엇이었나요?

◎ 미리생각해보기

A5 도안(1장), 검정 반구슬(11개), 분홍 반구슬(11개), 초록 반구슬(11개), 파랑 반구슬(11개), 금은종(1개), 인형눈(2개), 면끈(1개), 큐방(1개), 투명테이프(1장), 양면테이프(단체)

◎ 실험준비물

1. 일상생활에서 마주하는 최적화 문제에는 어떤 것들이 있을까요?

2. 세계지도를 완성하기 위해 필요한 최소한의 색깔은 몇 가지인가요?

◎ 실험결과 및 생각해보기

◎ 새롭게 알게 된 사실

◎ 느낀점