크리스핀

수학문제를 풀다가 이런 문제를 본적이 있을 것이다.

4명을 두명씩 짝지으려고 한다 그런데 서로 친한친구가 아니면 짝지어서 다니지 않기 때문에 친한친구끼리 짝을 지어주려고 한다 이때 짝을 짓는 경우의 수는 ?

이걸 코드로 구현한다면 어떻게 구현해야 할까?

완전탐색을 이용하면 가볍게 풀 수 있다.

일단 학생 수 * 학생 수 만큼 배열을 만들어서 0과 1이 친구라면 [0][1]에 True를 넣는다 물론 [1][0]도 True가 된다.

그리고 짝을 표시하는 배열을 학생수만큼 만들고 짝이 없는 두 친구를 골라 짝이 될 수 있다면 그 자리에 True를 채워넣는다 그리고 모두 짝이 되면 종료하도록 한다. 그 후 돌아와서 다시 False로 넣는다 ( 이미 이 둘이 짝이 되는 모든 경우의 수를 훑어봤기 때문에 )

그렇게 제귀함수를 돌다보면 모든 경우의 수를 셀 수 있다.

코드를 확인해 보자

보글게임에 대해 아는가?

보글게임은 게임판에서 문자가 랜덤하게 있고 그걸 이어서 문자열을 만드는 게임이다

예를 들어 

a l c d e

e o v e i

z z z z z

이런식으로 게임판이 되어있다면 (0,1), (1,1) (1, 2) (1, 3)을 이어서 love 라는 문자열을 만들 수 있다.

그렇다면 이 게임을 코드로 한번 짜보자

일단 완전탐색으로 구현한 보글게임이다.

일단 완전탐색으로 구현했기 때문에 느리다... 알고리즘 공부를 계속하면서 이 코드는 개선시켜 나가도록 하겠다.

0번부터 차례대로 번호가 매겨진 n개의 원소중 3개를 골라 모든 경우를 출력하는 코드이다.

그럼 이코드를 재귀함수로 고친 코드를 살펴보자