[정보] 천재 교과서 -문제 해결과 프로그래밍 -추상화와 알고리즘

<생각 깨우기> 지하철 노선도 단순화하기

초기 노선도	너무 많은 정보 전달해 복잡해서 알아보기 힘듦
헤리 백(Harry Beck),  현재 지하철 노선도	-시각적으로 단순하게 표현 (선과 기호만으로) -장점 : 한눈에 목적지 𐩐 방향 볼 수 있어 편리하게 사용 -최단 시간 알고리즘, 최소 환승 알고리즘 등 이용해 원하는 지점으로 이동

⇩

 

그래프: 데이터와 데이터의 관계를 선으로 연결하여 표현한 구조.

 

해리 벡(Harry Beck)의 지하철 노선도와 같이 역과 역을 선으로 연결해 표현한 구조를 말함

 

 

 

 

 

 

    문제 이해𐩐분석 및 핵심 요소 추출

 

➊ 용어 정리

문제	➀해답을 요구하는 질문 또는  ➁해결하기 어려운 일
문제 해결	문제들을 해결하기 위한 방법 또는 행동 ➝문제 해결 과정에 따라 서로 다른 결과 얻을 수 있고, 문제 해결 방법 또한 한 가지 혹은 여러 가지 있을 수 있다 ➝어떤 방법의 문제 해결이냐에 따라 시간, 정확도에 차이 발생
추상화	문제 해결 위해 문제 이해 𐩐 분석𐩐 중요한 요소 찾는 과정 필요 ➝ 이런 과정 통해 해결해야 할 문제의 복잡성을 효과적으로 줄이는 과정
알고리즘	문제 해결 절차(과정)를 논리적 순서로 설명하거나 표현(기술하여 표현)하는 문제 해결 절차나 방법

 

 

 

➋ 문제의 이해와 분석

<문제 이해와 분석 > -할 수 있는 질문 : ➀문제에서 해결하고자 하는 것은? ➁문제의 현재 상태와 목표 상태는? ➂문제에서 주어진 데이터나 조건은? ➃문제 해결하기 위해 필요한 정보는?

예시>  모래 시계

<핵심 요소 추출> -위의 ➀➁➂➃를 파악하고, 핵심 요소 추출해야 함 -문제 해결 위해 필요한 요소 찾거나, 불필요한 요소 제거하는 과정

 

 

 

➌ 추상화 기법 -문제의 분해

 

𐩐복잡하고 큰 문제를 작은 문제들로 분해하면 쉽게 문제 해결할 수 있다.

 

➝ 분해하는 문제 사이의 관계나 순서에 유의하여 작은 문제를 먼저 해결하고, 결과를 종합

 

 

예>  (지하철 유실물 보관소에 가서)잃어버린 가방 찾기

 

➝문제 분해 :

탑승했던 지하철은 몇 호선?

가방 두고 내린 역은 어디?

가방 두고 내린 열차의 칸은 어디? /

가방 두고 내린 시간은?

가방의 종류와 모양은? /

가방 속에는 어떤 물건이 들어있나?

 

 

 

➍ 문제 속의 규칙

-주어진 데이터 분석해 규칙 찾아내면 문제를 쉽게 해결할 수 있다.

<우리 주변의 규칙> 국제 상품 번호 -전 세계 사람들이 하나의 코드로 상품 정보 관리 -상품 판매할 때 사용하는 바코드의 한 종류, 미국에서 개발된 세계 상품 코드 시스템의 일부 -일정한 규칙 이용해 13자리 숫자에 ➀국가 코드 ➁제조업체 코드 ➂자체 상품 코드 ➃검증 코드 기록
	➀ 국가 코드 (880은 한국)-3자리 ➁ 제조업체 코드 -4자리 ➂ 자제 상품 코드 -5자리 ➃ 검증 코드 -1자리
<참고> 검증 코드 알아보는 방법 𐩐곱한 수를 모두 더하면 127 ➝127이 10의 배수가 되기 위해서 더해야 하는 수 ➝ 3

 

➝ 최근 바코드는 RFID 칩으로 바뀌어 가고 있다.

 

 

예> 개미 수열의 규칙을 찾아보고, 7번째 개미 수열을 작성해보자.

규칙 1 11 12 1121 122111 112213 ?	➝ 1이 1개 있다 [ 11 ] ➝ 1이 2개 있다 [ 12 ] ➝ 1이 1개, 2가 1개 있다 [1121] ➝ 1이 2개, 2가 1개, 1이 1개 있다 [122111] ➝ 1이 1개, 2가 2개, 1이 3개 있다 [112213] ➝ 1이 2개, 2가 2개 1이 1개, 3이 1개 있다 [12221131] ➝

󰄤 페르마의 밀실 문제 – 교과서 선택 활동