マサキ君의 용어 블로그

어제 갑자기 왠 바람이 불으서 C++ 자료 구조론(Data structure in C++)을 봤습니다. 이 책이 왜 있는지도 잘 모르겠지만, 여튼 있으면 봐 줘야죠 ;;;

1장 기본 개념 읽다보니 연습 문제 2번이 꽤 재미있어 보여서 대충 디벼봤습니다.

저는 몇번을 다시 해 봐도 recursion은 엄청난 벽이군요. 넘을수가 없어요. 종료조건은 어떻게 줘야하는지, 호출은 어느 시점에 하면 좋은지...

여튼 2번 문제는 아래와 같습니다.

연습문제 2. n개의 불리언 변수 x1, ...xn이 주어졌을 때, 이 변수들이 가질 수 있는 가능한 모든 진리값을 조합을 구하고자 한다. 예를 들어 n=2이면 true,true; true,false; false,true; false,false;와 같은 네 가지 경우가 존재한다. 이를 구하는 C++ 프로그램을 작성하고 몇 번을 수행하는지 계산하라.

예, 말 그대로 n개의 논리 변수가 있을 때 가질 수 있는 모든 값의 조합을 만들어내는 프로그램이었습니다.

책을 앞에서부터 차근차근히 보면서 푸니까 어찌저찌 풀리던데 대충 저는 이런 식으로 풀었습니다.

1. n=3일 경우의 진리표를 생각해보면
   {true, true, true;
   true, true, false;
   true, false, true;
   true, false, false;
   false, true, true;
   false, true, false;
   false, false, true;
   false, false, false}
   의 8가지(2^n)가 존재한다.
2. 진리표를 자세히 보면, x1이 true인 경우의 진리표는
   {true, true;
   true, false;
   false, true;
   false, false}
   의 형태의 진리표가 나오는데, 이것은 n=2일 경우(즉, 불리언 변수가 n-1개 있을때)의 진리표이다.
3. 위의 진리표도 마찬가지로 x1이 true일 경우의 진리표를 떼어놓고 보면 {true; false}의 형태임을 알 수 있다. 이것은 n=1일 경우(즉, 불리언 변수가 n-2개 있을때)의 진리표임을 알 수 있다.
4. 그러므로 n개의 불리언 변수가 가질 수 있는 모든 값을 조합을 만들어내기 위해서는 불리언 변수가 (n-1)개일 경우일 때의 진리표를 만들어내어, 해당 결과에 다시 true와 false을 조합해주면 된다.

...의 순으로 풀었습니다.

해당 코드는 여기로.