[3] 패턴 인식 예제

[SW예비학교] 인공지능과 컴퓨팅사고

2023-01-16 

 

컴퓨팅 사고의 문제 해결 기법 중 하나인 패턴 인식을 적용한 에제에 대해서 학습한다.

 

 

 

수학에서의 패턴

- 등차수열: 각항의 수가 그 앞항의 수보다 일정치씩 큰 차이가 나는 수열.

* 1,4,7,10,13,16,19,22,25...

*  a_(n) = a_(n+1) +3

 

- 피보나치수열: 이전의 두 항을 더한 값으로 이루어지는 수열.

 

* 1, 1, 2, 3, 5, 8, 13, 21, 34...

* a_(n) = a_(n-1) + a_(n-2)

 

 

 

 

숫자 패턴 찾기

-패턴 인식은 예측을 하거나 해결책으로 인도하는 지름길

 

- 숫자들의 시퀀스에서 패턴을 찾아보기

* 3, 6, 9, 12, 15, ? -> 패턴: 3의 배수의 리스트 -> 18

* 1, 2, 4, 8, 16, 32, ? -> 패턴: 등비수열 -> 64

 

 

 

 

패턴을 찾아서 문제 해결하기

Q. 영희는 학교 가기 전에 항상 학교 앞의 편의점에서 과자 1 봉지 씩 산다.

이 때문에 학교에 지각을 하고 선생님께 야단을 맞는다.

 

- 영희의 패턴

매일 학교 가기 전에 과자 1봉지 씩 구매

-> 과자 구매하는 시간으로 인해 지각

 

A. 영희에게 1주일에 한 번씩 편의점에서 과자 5 봉지를 사라고 권고

-> 아침마다 과자를 사지 않아도 되어 지각하지 않게 됨

 

 

---

문제의 해결책 사이의 유사성

* 다른 문제의 해결책 사이에 유사성이 존재 -> 이를 이용하여 해결책을 찾을 수 있음

 

- 김치찌개 끓이기 vs 된장찌개 끓이기  *둘 사이에는 유사성이 있음.

 

김치찌개 레시피

1. 냄비에 멸치와 물을 넣고 끓여 체에 걸러 멸치 국물을 만든다.

2. 양파, 고추, 대파, 두부, 김치를 썬다.

3. 멸치 국물과 앞에서 준비한 재료를 넣고 끓인다.

4. 김치가 푹 무를 때까지 끓인 후 참치를 넣고 끓인다.

5. 두부, 양파를 넣고 더 끓인다.

6. 대파, 고추, 고춧가루, 설탕, 후춧가루를 넣고 끓인다.

 

된장찌개 레시피

1. 냄비에 멸치와 물을 넣고 끓여 체에 걸러 멸치 국물을 만든다.

2. 무, 두부, 호박, 고추, 대파, 버섯을 썬다.

3. 냄비에 멸치 국물을 붓고 된장을 풀어서 끓인다.

4. 호박, 두부, 대파, 고추, 팽이버섯, 고춧가루를 넣고 끓인다.

 

 

*유사한 패턴

1. 멸치국물을 만든다.

2. 각종 재료를 미리 썬다.

3. 여러 가지 양념과 재료를 넣고 끓인다.

 

 

 

 

된장찌개를 끓여보지 않은 사람이더라도 김치찌개와 된장찌개의 유사한 패턴을 파악한다면 쉽게 끓일 수 있다.

또한, 두 개의 유사성이 있기 때문에 멸치 국물을 많이 만들어서 병렬로 김치찌개와 된장찌개에 모두 끓일 수 있다.

같은 예시로 두부, 양파, 대파도 가능

 

즉, 서로 다른 두 문제의 유사성을 파악한다면 한 문제의 해결책을 이용해서 다른 문제의 문제를 쉽게 해결할 수 있다.

---

콜레라의 발병 원인 찾기

1800년대 후반 런던의 콜레라 발병 원인 찾는데 패턴 인식이 이용됨

-1. 당시에는 콜레라 발병 원인을 찾기 어려움

-2. 존 스노라는 의사가 오염된 물을 통해 콜레라가 퍼졌다고 가정

-3. 콜레라가 발병한 시기와 발병한 곳 사이의 패턴을 조사 (데이터 수집)

-4. 패턴 조사 후 발병원이 오염된 도시 수도 펌프임을 발견

---

하노이 탑 문제

하노이 탑 게임:  3개의 막대기 중 왼쪽 막대기에 쌓인 디스크를 가장 오른쪽 막대기에 옮기는 게임

게임 규칙

-1. 한 번에 하나의 디스크만 이동 가능

-2. 각 이동은 스택 중 하나에서 상위 디스크를 가져와서 다른 스택 맨 위에만 놓을 수 있음.

-3. 작은 디스크 위에는 큰 디스크를 놓을 수 없음.

참고 사이트 https://vidkidz.tistory.com/649

하노이의 탑 (Tower of Hanoi)

 

 

원반이 한 개일 때

원반 1개

- 1번 기둥에 있는 원반을 3번 기둥으로 옮기면 끝 (1 -> 3)

---

 

원반이 두 개일 때

원반 2개 -1

-1번 기둥의 맨 위에 있는 원반을 2번 기둥으로 옮김 (1->2)

원반 2개 -2

-1번 기둥에 남아 있는 큰 원반을 3번 기둥으로 옮김 (1->3)

원반 2개 -3

-2번 기둥에 남아 잇는 원반을 3번 기둥으로 옮김 (2->3)

---

문제 해결 과정에서의 패턴

1. 비어 있는 막대기에 작은 디스크를 이동

2. 남아 있는 막대기에 큰 디스크를 이동

3. 작은 디스크를 그 위에 놓음