패턴 인식과 공통점 찾기(경우의 수)

* 다음 자료에서 대교협 제공 문제 이외의 것을 변형하여 상업적 목적으로 사용하는 것을 금한다.

다음은 대교협 자료에서 발췌한 문제이다.

 

[문제] 2009학년도 6월 4일 평가원 모의고사문제

좌표평면 위의 점들의 집합 S={(x,y)|x, y는 정수}가 있다. 집합 S에 속하는 한 점에서 S에

속하는 다른 점으로 이동하는 ‘점프’는 다음과 같은 규칙을 만족시킨다.

 

* 점 P에서 한 번의 '점프'로 점 Q로 이동할 때 선분 PQ의 길이는 1 또는 √2이다.

 

점 A(-2,0)에서 점 B(2,0)까지 4만 ‘점프’하여 이동하는 경우의 수를 구하시오.(단, 이동하는 과정에서 지나는 점이 다르면 다른 경우이다.) [4점]

 

주어진 조건에 따라 점 A에서 점 B까지 4번만 점프하는 경우의 최단 거리와 최장 거리를 고려하여 다ㅣ음의 그림을 얻을 수 있다.

  

1. 위 그림을 바탕으로 주어진 조건에 따른 경우의 수들을 가지치기 방식으로 표현하는 경우는 어떻게 해야 할까? 이를 대충 말로 설명해 본다면?

 

 

2. 주어진 조건에 따른 A에서 B까지의 점프 경로는 ‘→→→→’, ‘→↗↘→’ 등의 패턴으로 나타낼 수 있다. 그밖에 어떤 패턴들이 있는가?

 

 

3. 위 물음에서 찾아낸 패턴들에서 발견할 수 있는 공통점은?

 

 

4. 위 물음에서 발견한 공통점을 바탕으로 주어진 문제를 풀어 본다면?