[천재 교과서] 정보 - 문제의 구조화 (핵심 정리)

   문제의 구조화

 

 

 

 

➊ 문제의 구조화

구조화 (모델링)	문제 해결하기 위해 필요한 내용 요소들을 정리 및 배열하여 통일된 조직으로 만드는 과정 (표와 그림 등으로)
문제 구조화 장점	-문제 요소들을 체계적으로 분석할 수 있다. -내용 요소 간의 관계를 쉽게 이해할 수 있으므로 문제를 효율적으로 해결할 수 있다. 예)  쓰레기 버리는 문제

 

 

 

1.  표를 이용한 구조화

- 중복되는 내용을 정리하여 효율적으로 정보를 표현하고 관리할 수 있다.

 

예> 시간표, 공연 좌석 배치 문제, 좋아하는 간식 선택하기

	사탕	아이스크림	케이크	과자
선우	o		o	o
태영		o	o
민철	o		o

 

 

 

2.  그림을 이용한 구조화

-복잡한 문제를 도형, 기호, 그래프, 트리 등의 그림으로 간단하게 표현한다.

‘트리’란?	한 지점에서 상하 관계에 의해 여러 갈래로 나뉘어 연결되는 형태의 비선형 구조
‘그래프’란?	틀로 표현하기 어려운 자료들의 복잡한 관계를 선으로 연결하여 표현한 형태의 구조

트리 구조	그래프 구조
-나무처럼 뿌리에서 가지가 뻗어 나가는 모습 -데이터와 데이터 사이의 관계를 계층으로 표현 -트리 구조에서 가장 중심이 되는 시작(최상위) 노드를  ‘뿌리 노드 (root node)’라 함 -노드 A가 노드 B를 가리킬 때: A는 B의 부모 노드,  B는 A의 자식 노드 예>  학생회나 회사의 조직도, 우리 집 가계도,       책의 목자, 폴더 구조 등	-데이터와 데이터 관계를 선으로 연결한 구조 (자료를 나타내는 정점(vertex)과 자료 연결하는 간선의 집합) -데이터 간의 순서나 계층적 의미 포함하지 않지만, 화살표 이용해 데이터의 방향성 표현할 수 있음 -트리 구조와 달리 노드 A에서 출발한 관계가  다시 노드 A로 돌아올 수 있음 ♻ 예> 지하철 노선도, 버스 경로, 길찾기, 별자리, 화학 분자 구조,           전자 회로 등
트리 구조와 그래프 구조에서는 ➝ 데이터(자료)를 노드(node)라 하고, 그 사이의 데이터 흐림이나 관계를 선으로 나타낸 것을 간선(edge)라 함

 

 

<문제> 지도에는 각 위치와 각각을 이어주는 도로의 길이가 적혀 있다. A에서 E까지 갈 수 있는 모든 경로를 그래프 구조로 정리하고, 가장 긴 경로를 찾아보자 (각 경로는 두 번 이상 지날 수 없다.)
		< A에서 E까지 경로 > 𐩐 A➝B➝E 8 𐩐 A➝B➝C➝E 14 (가장 긴 경로) 𐩐 A➝C➝E 5 𐩐 A➝D➝E 7 𐩐 A➝C➝B➝E 13

 

 

<문제> 인접한 영역에 서로 다른 색을 칠하면, 영역을 구분할 수 있다. 단 꼭짓점에 맞닿아 있는 것은 인접된 영역이 아니다.
<구조화>
	➀각 영역을 점으로 표현 ➁영역과 영역이 경계선 두고 인접해 있으면, 경계선을 통과하는 선을 그려준다.		➂모든 점을 연결한 선의 개수 ➃가장 많은 연결선 가진 D. D와 연결된 A,C,E는 D와 다른 색 칠함

 

 

<문제> 지도를 그래프로 구조화하여 최소한의 색으로 칠하기 -우리나라는 최소한 몇 개의 색으로 칠할 수 있는가? 4색