Simple in Complex with Simple

1. 개요

아인슈타인 퍼즐이라고 불리는 문제가 있다.

이 퍼즐은 아인슈타인이 고안했고, 놀랍게도 전 세계 인구의 2%만이 풀 수 있는 문제라고 소개된다!!!

하지만 잘 살펴보면, 전 세계 인구의 2%만이 못 푸는 문제일 정도로 풀기 쉽다.

그리고 아인슈타인이 고안했다고 알려져있지만, 이는 속설일 뿐 전혀 근거없는 소리라고도 한다.

하지만 이 문제는 아인슈타인의 이름 덕분인지 무척 유명하다.

예전에 처음 봤을 때, 직접 공책에 적어가며 손으로 풀었던 기억이 있다.

하지만 이를 컴퓨터 프로그램으로 풀 생각은 못해봤는데,

프로그래밍하여 푼다는 엄두도 나지 않았는데, 

이번에 순열 알고리즘을 응용하면 이 문제를 풀 수 있다는 것을 처음 알았다.

이 방법은 무척 유용하고 재미있고, 뭔가 사고의 범위가 한 번 확장되는 계기가 되었다.

특히, 순열 알고리즘의 활용법을 제대로 익힐 수 있다.

꼭 풀어보자.

2가지 풀이법이 있는데, 

먼저 첫 번째 풀이법인 모든 경우 조사를 하게 되면 5!의 5제곱의 경우를 검사해야 하기 때문에

24,883,200,000의 경우의 수를 검사해야 한다. 이를 풀 때까지 기다리면, 1초에 100만 경우를 검사하는 컴퓨터의 경우에

약 7시간이 걸린다고 한다. 그렇기에 빠르게 풀 수 있는 2번째 방법이 있다.

두 번째 풀이법은 어떤 의미론 동적 프로그래밍과 비슷하다. 비록 이전에 계산한 결과를 사용하진 않지만 

조금의 조건을 바꾸어 검사해야 할 경우를 확 줄인다.

첫 번째 풀이법의 경우에는 순열 알고리즘을 통해 완성된 2차원 배열을 데이터로 넣어서 검사하지만,

두 번째 풀이법의 경우에는 각각의 카테고리별로 Level이란 특수한 경우를 두어, 현재 단계에서 필요한 검사만을 수행하여

이 단계를 통과해야 다음 Level 단계의 검사를 진행한다. 그리고 최종적으로 Level이 5가 되면 모든 경우를 통과했다고

판단하기에 그 때 비로소 출력한다. 

이 아인슈타인 퍼즐에서 모든 조건 검사를 통과하는 경우는 오직 1가지 경우 뿐이다.

먼저 아래의 문제를 풀어보고, 코드로 변환하자.

무척 재미있다!

2. 문제

문제의 배경

1. 색깔이 다른 5채의 집이 일렬로 지어져있다.

2. 각 집에는 서로 다른 국적의 사람이 살고 있다.

3. 다섯 사람은 서로 다른 음료를 마시고, 서로 다른 담배를 피며, 서로 다른 동물을 기른다.

15개의 정보

1. '영국'인은 '빨간' 집에서 산다.

2. '스웨덴'인은 '개'를 기른다.

3. '덴마크'인은 '차'를 마신다.

4. '초록' 집은 '하얀' 집의 왼쪽 집이다.

5. '초록' 집에 사는 사람은 '커피'를 마신다.

6. '팔몰' 담배를 피는 사람은 '새'를 기른다.

7. '노란' 집에 사는 사람은 '던힐' 담배를 피운다.

8. 한 가운데 집에 사는 사람은 '우유'를 마신다.

9. '노르웨이'인은 첫 번째 집에서 산다.

10. '블렌드' 담배를 피우는 사람은 '고양이'를 기르는 사람 옆 집에 산다.

11. '말'을 기르는 사람은 '던힐' 담배를 피우는 사람 옆 집에 산다.

12. '블루매스터' 담배를 피우는 사람은 '맥주'를 마신다.

13. '독일'인은 '프린스' 담배를 피운다.

14. '노르웨이'인은 '파란' 집 옆 집에 산다.

15. '블렌드' 담배를 피우는 사람을 '물'을 마시는 사람과 이웃이다.

다음의 상황에서 얼룩말을 기르는 사람의 국적은 무엇인가?

3. 코드 및 출력

3-1) 선언

3-2) 메인

3-3) 첫 번째 알고리즘 (mPerm_Einstein(), Check_Einstein_Rule())

3-4) 두 번째 알고리즘 (mPerm_Einstein_Advanced(), Check_Einstein_Rule_Advanced())

3-5) 출력 코드

3-6) 출력

4. 정리

이 문제를 풀면서 이차원 배열을 순열로 바꾸는 법을 알았다. 결국 단계별로 순열을 진행해나가면 되는 건데.

순열이란 하나의 흐름으로만 머리가 인식하니, 역시 사고가 명확히 안 떠오른다. 사고의 범위를 넓히자.

또 하나 enum 열겨형을 통한 코드의 명확함이 가지는 강력함을 알았다.

이런 기법들을 잊지말고 잘 활용해보자.

1. 개요

조합, 중복조합, 순열, 중복순열 알고리즘은 모든 경우를 나열하는 알고리즘이다.

모든 경우를 나열하기에 작은 범위의 문제에 대해서 완전 탐색 알고리즘에 적합하다.

또한 각각의 경우에 해당하는 모든 데이터 Set을 가지고 있기 때문에 조건에 만족하는 모든 경우를 출력할 때 필요하다.

또는 앞서 포스팅한 knapsack problem(배낭 문제)처럼 각각의 가치와 무게에 대한 경우에 따라서

문제가 설정한 최고 효율적인 방법이나 값을 찾는데 도움이 된다.

이 포스팅에서는 현재 각각의 뼈대가 알고리즘이 흩어져있는데, 이를 복습 겸 코드 작성하여 모든 뼈대를 종합해서 정리했다.

재귀 방식으로 움직이기 때문에 큰 문제는 해결하지 못한다.

만약 문제가 작고, 완전 탐색을 한다고 하여도 성능에 크게 문제가 없고, 또한 각각의 경우를 출력해야 한다면 이 

나열하기 알고리즘의 대표인 '조합, 중복조합, 순열, 중복순열' 알고리즘을 잘 고려하자.

조합이나 중복조합 그리고 중복순열 알고리즘은 쉽게 직관적으로 코드를 보면 이해할 수 있지만,

순열 알고리즘만큼은 조금 머릿속에서 쉽게 쉽게 이해가 안갔다.

오직 순열 알고리즘만 미리 초기화한 배열을 사용한다.

또한 Swap 함수나 또는 사전 순으로 출력을 위한 Right_Rotate()와 Left_Rotate()를 사용한다.

즉, 미리 입력해둔 배열 속 데이터를 이리저리 순서만 바꿔서 출력하고 다시 원래 상태로 되돌린다.

순열 알고리즘의 재귀 방법은 이렇다.

현재 단계에서, 배열의 첫 번째 원소, 두 번째 원소, 세 번째 원소 ... 마지막 원소를 맨 처음 원소와 교환한 후(처음만 결정)

다음 단계에서 나머지 뒷 부분의 순열 알고리즘을 작성한다.

예시)

-> 0 결정 - 1, 2의 순열

0, 1 2의 순열      -> 1 결정 - 0, 2의 순열 

                       -> 2 결정 - 0, 1의 순열

2. 문제

조합, 중복조합, 순열, 중복순열 뼈대 알고리즘을 모두 작성하시오.

3. 코드 및 출력

3-1) 조합

3-2) 중복조합

3-3) 순열

3-4) 중복순열

3-5) 메인

3-6) m: 3, n: 2 출력

3-7) m: 3, n: 3 출력

4. 정리

모든 경우를 다 나열하여 알고싶을 때나 또는 작은 부분에 대한 완전 탐색을 위할 때 이 알고리즘을 사용한다.

완전 탐색 알고리즘은 모든 알고리즘의 기본이니까 언제나 시작은 이 나열 알고리즘을 적용할 수 있는지 검사부터 하자.

계속 공부!

그토록 간절했던 '최종 합격'이라는 단어.

정말 기쁘다.

원래는 이 소식을 받자마자 바로 작성하고 싶었지만, 

아무래도 내게 정말 은사님이 되주신 교수님과의 면담 후에 작성하고 싶어서 뒤로 미루었는데,

교수님이 일본 출장가시고 돌아오실 기미가 보이지 않는다.

흑

정말

'교수님 덕분에 제가 이렇게 합격할 수 있었습니다.'

라고 간절히 외치고 싶었는데.

너무 감사하다.

부모님이 좋아하시는 모습도 너무 좋다.

그 내색없으신 아버지의 은연중에 풍기는 기쁨의 분위기와 울어버리신 어머니.

이렇게 내색않고 기다리셨구나를 다시 한번 알게 된다.

항상 마지막에 떨어져서 힘들어했던 내 모습을 보면서 묵묵히 기다려주셔서 정말 감사하다.

출근까지 이제 일주일남았다.

원래의 목표는 조금 시간이 있다면 해외여행을 진득히 돌아다니고 싶었다.

특히 유럽여행.

많이 기다린 시간이었지만

비록 그럴 수 있는 시간은 없지만 뭐 상관없다.

혼자보는 여행도 좋지만, 역시 나는

혼자하는 여행보다 나중에 사랑하는 사람하고 같이 하고 싶다.

돈 많이 모아야지.

이제 드디어 부모님에게 의지하던 시간은 모두 끝났다.

이젠 내가 내 스스로 몸을 챙기고, 아파도 버티고, 보살핌받는 입장에서 보살펴주는 사람이 된다.

이것이 가장 무섭지만 이젠 무섭다고 피할 수가 없다.

더욱 좋게 변하는 수 밖에.

학점 1.6에서 판교까지.

푸흐흐 진짜 힘들었다.

학창시절 내내, 학업보다 내 꿈이 무엇인지 찾아나갔던 시간들.

어떻게보면 조금만 더 유도리있었다면 조금 더 높은 학점을 받았을지도 모른다.

수업도 학점을 못받더라도 정말 듣고 싶은 과목을 듣고 싶어서, 영어가 안되도 영어 수업을 들었고.

과제도 내가 한게 아니면 내키지 않아서, 도움을 받으면 제출하지 않았다.

바보 멍청이다.

나는 진짜 고집쟁이였다.

학점이 조금만 더 높았다면 이렇게 돌고 돌아서 안왔을까?

이제야 알게된 거지만 전혀 그렇지 않다.

오히려 저 고집이 날 여기까지 이끌었던 것 같다.

왜냐면

저 고집이 정말 포기하고 싶고, 타협하고 싶고, '되는대로'라는 생각을 가지게 만들때에도

나를 지탱해주게 만든 것.

포기하지 않도록 만든 것.

계속 진취적으로 나아갈 수 있게 해준 것.

그것이 바로 내 스스로 고집이었으니까.

이 고집이 나의 신념이 될 수 있을까.

그래도 이 고집을 남에게 부리진 말자. 오직 내 스스로에게만.

여전히 합격 여부에 관계없이 아침에 도서관에 온다.

이제는 이 공간이 너무 좋다.

자신들의 꿈을 이루기위해서 쉴새없이 불태우는 노력의 잔재들.

그 흔적속에 있는게 좋다.

오늘 마지막 출석스터디를 참석했다.

그 암담했던 순간, 정말 다 포기하고 싶었던 그 때 지푸라기 겸 신청했던 것.

이제 많이 지난 줄 알았는데 아직 2달도 안됐네.

도저히 혼자로는 못버틸 것 같아서 신청했던 이 모임에서 이제는 1기 졸업생이다.

마지막 아침 송별회겸으로 만나 인사를 나눈다.

좋다.

어떤 모임을 시작해서 이렇게 깔끔하게 나가게 된 적은 없었는데 처음이다.

그래서 마음에는 조금 더 뭔가 유익한 무언가가 단단해지는 느낌이다.

이번 주 목요일 날, 영화스터디도 마지막으로 보고나서 인사를 나누면 정말 실감이 될 듯하다.

작은 마무리

다음 주엔 어떤 삶을 살고있을까.

재밌겠다.

그리고

끝 아니고 쉴 때 아니란 거 알자.

이제는 능력만 죽도록 키워야할 때.

신입에서의 3년을 어떻게 보내는 지에 따라 평생이 바뀐다고 했지.

이제 시작이니까 방심하지마.

반드시 미래를 여는 세대가 되자.

앞으로 SW를 중학교때부터 배우고 오는 얘들과 경쟁해야 하는 시대.

끝없이 발전하자.

대가가 될 때까지.

운좋게도 오늘 교수님과 전화 통화가 되어서 교수님을 뵜다.

5년이 지났는데 여전히 활력이 넘치신다.

고집있으시고 완고한 모습.

후후후.

진짜 내 졸업식 개인 축사를 해주셨다.

그래 내 행복이 우선이지.

정말 취직하고 달려와서 얘기해드리고 싶었는데, 좋다.

감사합니다. 교수님.

교수님 덕분에 프로그래머의 꿈을 꿀 수 있게 되었습니다.

종종 안부 메일 보내겠습니다.

마지막으로 방금 이 글을 작성하다 친구가 와서 잠깐 밖을 거닐었다.

항상 도서관에 있다가

오늘만큼은 학교 이곳 저곳을 돌아다녔다.

이제 이 풍경을 이 감성으로 바라보는 것이 마지막이 되겠지?

학교 정원 아래에서 발견한 빨간 단풍.

뭔가 가려보이는 것처럼 느껴지는 저 모습 너무 이쁘다.

지금의 추억을 모두 담아서 사진을 찍었다.

내 학창 시절을 추억할 때면 항상 떠올라라.

그럼 이제 다시 시작.

!

클래스에 대한 얘기를 하면 빠지지 않고 등장하는 것이 바로 상속이다.

이 상속 관계는 객체지향 프로그래밍에서 무척 중요하다.

객체지향 프로그래밍은 절차형 프로그래밍의 한계점에 의해 탄생한 프로그래밍 기법이다.

객체를 통해서 현 실세계를 표현하는 프로그래밍으로 현재 대부분 모든 프로그래밍 기법이다.

물론 객체지향 프로그래밍이라고 해서 모든 것을 표현하진 못한다고 한다. 특히 최근에 객체지향 프로그래밍의 한계점으로

새로운 프로그래밍 기법이 연구되고 있고 속속 등장하고 있다고는 하지만 이 얘기는 여기서 마무리하고 다시 본 이야기로

돌아가서 이런 객체지향 프로그래밍에서 클래스란 모두가 알다시피 어떤 실체의 틀을 말한다. 그리고 그 실체의 틀에 

필요한 정보를 넣어서 완성시킨 형상이 바로 객체다.

하지만 이 객체들은 진화한다. 현실 세계에도 계속 새로운 물건이 등장하고 그 물건을 개선하여 다시 새롭게 탄생한다.

이러한 현실 세계를 나타내기 위하여 컴퓨터로 나타내는 객체지향 세계에서도 진화라는 개념이 등장해야 했다.

그래서 나온 것이 상속이다.

글이 길어졌다. 이제부턴 짧게 작성해야겠다.

상속은 기존 것을 받아서 프로그래머 입맛대로 바꾸는 것을 말한다.

슈퍼 주전자를 만들고 싶다. 이 때, 슈퍼 주전자를 완전히 무에서 만들어내는 것보다 기존의 주전자에서 만들어내는게

훨씬 더 비용적으로 편하고 좋다. 그렇기에 기존 주전자를 받아서 바꾸고 싶거나 버리거나 추가할 부분을 추가하여 변형한다.

만약 주전자의 뚜껑을 열 때, 기존의 주전자는 사람의 손으로 직접 열지만 슈퍼 주전자는 스위치를 통해 연다고 하자.

이렇게 새롭게 변형이 일어나는 부분을 프로그래밍 코드로 표현하는 방법을 '오버라이딩'이라고 한다.

한 마디로 부모 클래스 메서드를 자식이 필요에 맞게 조정하는 것이다.

단!! 반환 타입, 이름, 매개변수 타입과 개수까지 모두 같아야 한다.

오버라이딩과 오버로딩은 엄연히 구분되어 있다.

아래 코드의 Move()가 바로 오버라이딩 대상이다.

만약 위의 클래스에서 다음과 같은 코드를 수행한다면 그 결과는 어떻게 될까?

다음은 위 코드의 결과화면이다.

정상적으로 상속되어서 오버라이딩된 것을 볼 수 있다. 하지만 !!!

하지만 이 방법은 큰 문제가 있다.

단순히 저 객체만을 사용하려 한다면 발생되지 않을 문제이지만, Shape 클래스에서 상속받은 자식 클래스들이 둘 이상일

경우에 발생하는 문제로 다음과 같은 함수를 호출하는데 발생한다.

이 함수는 Shape 클래스 타입을 파라메터로 받기에 Shape 클래스를 상속받은 모든 자식 클래스는 이 함수에 접근 가능하다. 

하지만, 

다음과 같은 코드를 보자.

이 코드의 결과는 무엇일까?

Triangle 객체를 생성해서 넣었기에 출력 결과는 Triange Move()가 나올 것 같지만, 결과는 다음과 같다.

실제 객체는 Triangle이지만 함수의 파라미터 타입으로 인해 함수는 Triangle의 부모 클래스인 Shape 객체로 인식하게 된다.

그럼 어떻게하면 Shape 타입이지만 Triange 객체에 의도대로 접근할 수 있을까?

바로 클래스 Upcasting을 활용하면 된다.

Upcasting을 활용하면 Shape 클래스를 상속받은 모든 클래스들은 이 함수를 사용할 수 있는 인터페이스 함수로 바꿀 수 있다.

그 방법은 Triangle 객체를 다음과 같이 생성한다.

다음은 위 코드의 출력 결과이다.

???

이게 무슨일이람? 

무언가 이상하다.

첫 번째로 Shape Move()가 아닌 Triangle Move()가 출력됐어야 했고, 그리고 부모 클래스인 Shape의 소멸자가 수행되기 전에

Triangle의 소멸자가 수행되어야 했는데 그러지 않는다. 이와같은 현상으로 인해 자식 클래스인 Triangle 객체가 해제되지

않고 남아있기에 메모리 누수 현상까지 발생한다.

바로 이 부분이 이번 포스팅의 핵심이다. 잘 기억하자. 또 그렇게 벌벌 거리지 않게.

위 문제는 만약 언어가 Java라면 큰 문제가 없겠지만, 언어가 C++이기에 발생하는 문제점이다.

가상테이블과 객체간의 연결 관계에 대해 깊은 이해를 위한다면 정확히 찾아보는 것이 좋다. 여긴 그냥 관념적인 내용이다.

컴파일 과정에서 현재 생성된 객체의 메서드가 부모 클래스의 메서드인지 자식 클래스의 메서드인지 판단하게 되는데,

만약 Java라면 모든 연결을 동적 바인딩 방식으로 진행하기에 사용자의 의도대로 Triangle 객체를 생성하고 Move() 메서드를

수행하면 그 결과는 "Triangle Move()" 결과나 나온다.

하지만 C++언어는 virtual 키워드를 통해 객체와 메서드간의 연결을 동적 바인딩을 명시해주지 않으면 위의 코드에서는

Triangle 객체를 생성했지만 실제로 Move() 메서드의 결과는 "Shape Move()"이다. 

그 이유는 virtual 키워드를 입력하지 않았기 때문에 컴파일러가 부모와 자식의 오버라이딩 관계를 정적으로 바인딩했기

때문에 발생한다. 그래서 동적 생성인 new 연산자로 생성했다고 해서 동적 바인딩이 이루어지지 않고, 이미 정적 바인딩이

진행되었기에 함수 호출 시 원하는 출력이 나타나지 않는다.

만약 정상적인 출력을 원한다면 virtual 키워드를 부모 클래스의 오버라이딩 함수 앞에 넣어주면 된다.

수정된 클래스이다.

수정된 클래스의 출력 화면이다.

의도대로 Shape Move()가 아닌 Triangle Move()가 출력되었다.

하지만 여전히 Triangle 객체가 해제되진 않고 있어 메모리 누수 현상이 계속된다.

이를 어떻게 해결해야할까?

정답은 똑같이 부모의 소멸자 앞에 virtual 키워드를 삽입하면된다.

그러면 소멸자도 똑같이 동적 바인딩이 이루어지면서 원하는 의도대로 프로그램이 진행된다.

다음은 최종적으로 수정된 클래스이다.

위 코드의 출력 결과이다.

정상적으로 함수 실행이 완료되었고, 객체의 소멸까지 메모리 누수 현상없이 잘 해결되었다.

이처럼 Upcasting을 활용하면 파라미터로 부모 클래스 타입을 가지지만, 자식 객체들이 접근하여 그 함수를 활용할 수 있다.

말이 어려우니까 한 마디로,

만약 Upcasting을 하면 객체지향의 다형성을 제대로 활용할 수 있다. 아래의 코드를 보면 명확히 이해 가능하다.

마지막 코드

출력

play() 함수를 각각의 객체 타입에 맞게 파라미터를 오버로딩 할 필요없이, 상속 관계라면 하나의 함수로 접근 가능하다.

이것이 Upcasting을 사용하는 가장 대표적인 이유다.

아주 미약한 이유로는 Upcasting된 코드를 보면, 상속 관계를 한 눈에 알아볼 수 있어 가독성에 아~~~~주 조금 도움된다.

그리고 Downcasting이란 Upcasting의 반대의 의미이며 절대로 생성할 때 사용하면 안된다. 

애초에 visual studio라면 오류를 내보낸다.

왜냐하면 다음과 같은 코드가 있다.

Triangle* t = new Shape();

기본적으로 Triangle 클래스가 Shape 클래스의 자식 클래스이기에 필요로 하는 정보량이 훨씬 많기에 그만큼 생성해야 한다.

하지만 Shape() 객체로 생성하면 Triangle 클래스가 필요로 하는 정보량을 모두 생성할 수 없다.

그렇기에 Downcasting은 생성할 때, 쓸 수 없다.

단지 Upcating한 객체를 원래대로 되돌릴 때 사용할 뿐이다.

마지막으로 이와같은 Upcasting, Downcasting의 존재는 편리하지만 잘못사용하면 정보의 손실이 발생하는 위험한 방법이다.

그렇기에 이를 보완하기 위한 Dynamic Casting이 존재하지만, 이에 대한 내용은 다음에 알아볼 것.

다시는 이 내용몰라서 당황하지 않게 정말 평생의 미련이 될 뻔했다. 바보야.

솔직하지 않았더라면.