Simple in Complex with Simple

지금의 내 팀장님이 기술면접때 내주셨던 문제.

이외에도 많은 게임 기업 필기테스트(판교에서 건물 제일 좋은 기업)에 등장했던 문제이다.

처음 이 문제를 들었을 때는 크게 어렵지 않았다. 

왜냐하면 내 스승님이신 '코딩인터뷰 퀘스쳔' 책에 이에 대해서 짧지만 충분하게 설명해두었기 때문이다.

아주 단순한 비교로는 malloc()은 함수이고 new는 연산자이다.

단순하지만 중요하지 않다는 것은 아니다.

결국 위의 말이 정답이고 본질이기 때문이다.

그리고 이 질문하나로 기술면접에서 수없이 많은 질문들로 뻗어나갈 수 있다.

그 당시의 내 대답은 이랬었던 것 같다. 

음 ... (생각좀 가다듬는 시간) malloc()은 함수이고 new는 연산자입니다.

그래서 발생하는 가장 큰 차이는 생성자의 유무입니다. malloc()은 시스템 함수로서 함수 안에서 메모리를 할당하지만

new는 연산자로 바로 메모리를 할당하는게 아니라 생성자를 호출하여 메모리를 할당합니다. 그러므로 생성자를 통하여

호출하기 때문에 new로 메모리를 할당하면 생성 시 초기화가 가능한 장점이 있습니다.

이렇게 대답하고 굉장히 뿌듯했다. 그리고 추가타로 들어올 질문 역시 조금은 대비되어 있었다.

위에서 언급한 판교에서 건물 제일 좋은 게임 기업에서 들어온 후속 질문으로 그럼 malloc() calloc() realloc()에 대해서

말해보고 realloc()시 발생할 수 있는 문제점에 대해서 언급하라는 질문을 들어봤기 때문이다.

그래서 대답 후 미리 머리속으로 malloc()과 calloc() realloc()에 대한 차이점을 정리중이었다.

그리고 realloc()의 대표적 문제점에 대한 답변도 준비하고 있었다.

realloc()의 대표적 문제는 정말 혹시나 메모리 할당이 실패할 경우 null이 반환되기 때문에 기존의 메모리가 할당되어

있는 포인터를 잃어버리는 것이다.

예를들어 

int * mem = malloc();

mem = realloc(); //실패 시 mem에는 null값 존재

그러므로 기존에 할당했던 mem이 free() 되지 않고 이제는 찾을 수 없는 곳으로 가버린 것이다.

당연히 이런 점은 메모리 누수로 남는다. 그리고 이런 코드가 (물론 그럴 일 없겠지만) 하나의 프로그램에서

화면을 Update하는 GUI쪽 함수라면 순식간에 메모리가 터져버린다.

그래서 realloc()을 할 때는 기존의 메모리 주소를 저장하고 실패 시 복구하는 프로세스가 함께 있어야 한다.

int * mem = malloc();

/* 

... process - realloc 필요

*/

// 기존 메모리 주소 백업

int * mem_temp = mem;

// 메모리 재할당

mem = realloc();

// 복구 과정

if( mem == null ) {

mem = mem_temp;

}

속으로 그러면서 드는 생각.

결국 질문은 다 돌고 도는구나. 

실제 코딩을 하고 지켜보지 않는 이상 기술면접으로 물어볼 수 있는 질문들은 어쩔 수 없이 한정되어 있나?

이런 생각이 찰나간 들었다.

그리고 자신만만하게 질문을 기다리고 있는데 팀장님이 말씀하셨다.

그 ... 생성자에서 생성 시 초기화를 한다고 했는데 그건 어떻게 하는건가?

...

???

우의잉읭???

이게 무슨 소리지. 뭘 어떻게 초기화하는가. 그냥 하면 되는거 아닌가?

순간적으로 혼란스러웠다.

왜냐하면 이때의 나에겐 초기화 리스트와 대입의 차이를 모르고 있었다.

그래서 이렇게 답변드렸던 것 같다.

클래스에 선언한 여러 변수들은 개수가 여러 개일수도 있고 각각의 타입이 다를 수 있기 때문에

생성자 안에서 각각 타입별로 필요한 값으로 초기화 할 수 있습니다. 

예를들어 int형이면 0으로 초기화하고 포인터 타입이면 null로 초기화하듯이 말입니다.

그러고 팀장님 표정을 살폈다.

찌뿌리신다.

차가워지셨다.

망했다.

그런 생각이 들었다.

자신만만해하더니 또 이꼴이냐?

순식간에 자괴감에 빠졌다.

그리고 팀장님은 더이상 묻지 않으셨다.

이후 면접이 끝나고 나는 굉장히 찝찝했다. 

무난히 흘러간 면접이라고 생각했는데 답변하지 못한 찜찜했다.

하지만 다행히 운이 정말 좋아서 통과되었고 지금은 이렇게 함께 팀장님과 일하고 있지만

회사 들어와서 팀장님과 Effective C++ 시리즈를 함께 공부하면서 그때 면접때 팀장님이 말씀하신 부분을 알게되었다.

간단하게 초기화리스트로 표현하는 이 부분은 두 단어로 표현이 가능하다.

생성 시 초기화와 생성 후 초기화다.

그리고 보통 우리가 배울 때 하는 초기화가 바로 생성 후 초기화다. (물론 잘 배웠으면 아니겠지만)

Car* car = new Car();

했을 때 보통 생성자를 만들면 이렇다.

class car {

private:

int 바퀴;

int 엔진;

int 기름;

public:

// 생성자

Car();

}

란 차의 클래스가 있을 때

Car() {

바퀴 = 4;

엔진 = 1;

기름 = 0;

} 은 생성 후 초기화이고

Car() : 바퀴(4), 엔진(1), 기름(0) {

} 은 생성 시 초기화이다.

뭔 차이일까?

솔직히 지금도 이렇게 초기화하는 것이 그렇게 중요한가? 이런 생각이 많이든다.

생성 후 초기화보다 생성 시 초기화가 당연히 효율은 좋다.

왜냐하면 생성 시 초기화는 한 흐름에 모든 것이 끝나고, 생성 후 초기화는 생성과 초기화 2가지 흐름으로 처리되기 때문이다.

그러니 비용이 당연히 2배이긴 하지만 ... 요즘의 컴퓨팅 파워로는 충분히 감당할 수 있는 수준이 아닌가?

라는 생각이 배우면서 많이 들었다.

하지만 일하다보니 정말 사소한 부분이라고 생각했던 곳에서도 효율의 차이가 많이 난다.

작은 곳에서부터 꼼꼼히 하는 습관이 정말 중요한 것을 느낀다.

그리고 지금의 컴퓨팅 파워로도 너무나 느리다고 생각될 때가 많다.

그러니 코드 한 줄 추가되는 것없이 효율적일 수 있는 부분이 있다면 그렇게 고치고 수정하는 것이 옳다.

어쩌면 팀장님은 그런 부분도 간과하지 않고 기억하고 있는 성격인지 보려고 했을 수도 있다.

- 세 번째 면접 일기 끝

- 객체지향의 3가지 특징인 다형성의 기초의 이해를 묻는 아주 많이 들었던 질문.

왜 다형성을 가진 C++ 클래스의 소멸자에는 virtual 키워드를 붙일까?

(다형성을 가지지 않는다면 별로 상관없다. virtual 자체가 상속과 다형성에 관련된 키워드이므로)

이를 이해하기 위해서는 먼저 다음을 이해해야 한다.

다음과 같은 상속 관계가 있다.

이 관계에서

Base* base = new Derived()는 컴파일 오류가 나지 않지만 

Derived* derived = new Base()는 컴파일 오류가 나는 것을 이해해야 한다.

이 사실을 제대로 알기전에 나는 항상 생각을 반대로 했었다. 

Derived가 Base를 상속받아 더 확장되었으니 Derived가 Base를 포함할 수 있겠지?

하지만 안타깝게도 코딩은 수학이 아니더라.

*가 붙어있기에

*의 의미는 가리킨다는 것이기에

위에서 아래를 가리키듯이

Base에서 Derived를 가리키는 개념이다.

이에 대한 더 정확한 이해는 상속의 3가지 관계 

is-a

has-a

is implemented of 

3가지 관계 중에서 is-a 관계를 깊게 살펴보면 조금 더 잘 알 수 있다.

이 부분만으로도 기술면접이 아닌 필기테스트까지 합치면 정말 많이 본 문제다.

모든 다형성 이해의 기초가 되는 부분.

결론적으로는 위처럼 컴파일 오류가 난다는 것은 C++ 규칙에 어긋났다는 의미이다.

C++이란 형체가 없는 글로 쓴 규칙이다.

C++ 스펙(취업 스펙이 아닌 명세화된 규칙) 문서를 보기 전까지는 나는 C++이 visual studio인 줄 알았다.

하지만 GCC, Visual Studio같은 컴파일러는 스트롭스트룹 할아버지가 규칙을 만들고 

C++ 표준 위원회에서 더 구체화 환 글로 쓴 규칙, 즉 스펙이다.

즉, Derived *derived = Base(); 란 애초에 스펙과 어긋났다는 소리이다.

(수학으로 치면 정의를 무시했다로 이해하면 된다.)

그럼 애초에 다음과 같이 쓰면 될 것을 왜 저렇게 꼭 받아야 할까?

왜!! Base *base = new Derived() 와 같은 형태가 다형성의 기초가 되는걸까?

물론 위처럼 써도 된다. 문법으로는 어긋날것이 없다.

하지만 그 객체를 받는 것이 Base* base에서 뻗어나간 모든  유도(자식) 객체를 Base에서 가리킬 수 있다는 것은 

설계에서 거대한 이점이 된다. (객체지향의 위엄 중 하나)

그것을 보기 전에 과연 다음과 같은 결과는 어떻게 될까?

당연하듯이 결과는 다음과 같다. 

하지만 다음과 같은 상황에서는 어떨까?

Derived() 객체를 Base*로 받는다면? 위의 결과와 같을까?

어라? (어라는 무슨 다들 알고있듯이 뻔한 결과이다...)

실제 객체는 Derived() 객체이지만 Base*로 이를 받으니 원하던 Derived 행동이 나타나지 않고 Base 행동이 나타났다.

이와 같은 결과가 된다면 다형성이 이뤄진 것이 아니다.

어떻게 할까?

모두 아시다시피 다음처럼 virtual 키워드를 붙인다. 

다음의 결과는?

출력

원하는대로 똑같이 Base* 타입으로 받고 Do() 함수를 호출했지만 그 결과는 다르다.

virtual 키워드를 이용하니 이렇게 Base* 타입 하나로 서로 다른 객체의 행동을 불러올 수 있었다.

이것이 내가 생각으로는 다형성의 기초같다. 그리고 내가 객체지향을 처음으로 제대로 알고싶게 만든 문제이기도 했고.

그럼 돌아와서 중간에 있었던 

Base 객체는 Base* 타입으로 받고, Derived 객체는 Derived* 타입으로 받으면 될 것을! 왜 하나의 Base* 타입으로 받을까?

내가 생각하는 답은 좋은 설계를 위해서이다.

만약 Base 타입이 그로부터 생성된 상속된 Derived를 받을 수 없다면?

단순한 예를 들어보면, 어느 한 함수(메서드)에 Base에서 상속받은 Derived 객체이지만 어느 객체가 들어올지를 모른다면

이를 판단하기 위해서는 아마 다음과 같은 메서드 형태를 만들 것이다.

void PrintMe(Base* b, Derived* d1, DDerived* d2, DDDerived* d3 ...) {

if( ... ) {

}

else if ( ... ) {

}

...

else {

}

}

왜냐하면 객체를 구분하기 위해서. 

그리고 상속이 단순히 Base, Derived로 끝나는 경우는 대학교에서 배울 때 빼곤 없다고 한다.

끝도없이 타고내려오는 경우가 대부분이라 한다. 그러면 상속의 트리가 깊어질수록 코드 작성은 미궁에 빠질 것이다.

하지만 Base*가 Base에서 파생된 모든 객체를 받을 수 있다면? 

위의 코드는 이렇게 변할 것이다.

void PrintMe(Base* b) {

b->Do();

}

정말 간단하다. 심플하다.

이 말고도 다른 이유가 많겠지만, 

나는 이 예시에서 Base*로 파생된 모든 Derived 객체를 받을 수 있다는 것의 이점을 조금 더 알게되었다.

그럼 이제 마지막 본론이다. 

원래의 주제로 돌아와서, 

그럼 왜 다형성을 가진 관계에서 소멸자에 virtual 키워드를 붙여야할까?!!

그 예시는 다음의 두 코드와 결과를 보시라.

(1) 소멸자에 virtual 키워드가 없는 경우 결과

위의 출력 결과에서 이상함을 눈치채셨듯이 Derived 생성자는 있지만 Derived 소멸자는 없다.

이는 C++의 고질적인 무한 디버깅의 원인이되는 메모리 누수의 원인이 된다. 

(프로그램 안에서 수도없이 생성과 소멸하는 객체라면 바로 죽는다. 그리고 그 프로그램에 상용 제품이라면 손해는 ... 하하하)

(2) 소멸자에 virtual 키워드를 넣은 경우

!!!

Derived 소멸자가 호출되었다.

이처럼 위에서 다형성을 가진 행동을 하기 위해서 상속 관계 안에서 각각의 객체를 구분하기 위해 함수(메서드)에 

virtual 키워드를 붙인 것 처럼!

소멸자도 역시 상속 관계 안에서 정말 자신의 객체를 소멸시키기 위하여 소멸자에 virtual 키워드를 붙인다.

잊지말자.

다형성을 가진 상속관계에서는 반드시 소멸자에 virtual 키워드를 붙여야 한다는 것.

(우리나라 대기업 및 주요 IT 기업 필기테스트와 기술면접에서 거의 다 만나본 객체지향의 기초 핵심 중 하나이다.)

-순전히 내 경험 및 내 생각

끝

오랜만에 블로그를 썼더니 좋다.

휴일에 잠만자기보다 좀 햇빛을 받으면서 글을 쓰러나오자.

먼저 취업한지 4개월이 다가간다. 정신없이 시간을 보내고나니 수습 과정이 끝나있었다.

그동안 테스트 프로젝트를 수행하고 책을 읽고 하루하루 매일 교육과 공부의 일상이었다.

그 속에서 정말 고마운 일상이 불쑥 파고들었다.

훌륭한 팀장님을 만나서하게 된 일로 우리가 빠르게 일에 적응하도록 도움을 주기위해 하루에 한 번 매일같이 하는 일.

이제는 너무 당연하다시피 하는 것.

위 'Effective C++' 책을 한 챕터씩 깊게 읽고 팀장님과 토론하는 것이다.

처음 시작은 굉장히 힘들었다. 객체지향개념이란 것. 

취업을 위해 기초 알고리즘과 컴퓨터 공학 기초 지식 습득에 열을 올린 내겐 굉장히 생소했다.

왜냐하면 학교에서는 뜬구름잡는 것 같은 느낌이었고, 정말 객체지향개념이 들어가도록 설계해 본 일과 프로젝트는 없었으며

또한 이 단어가 가지는 추상적인 관념은 C만 공부해서 언제나 절차지향적인 사고가 중심인 내겐 정말 힘들었다. 

하지만 이런 내 문제를 잡아주고 어떻게보면 알고리즘보다도 훨씬 중요한 설계라는 관점을 지니게 만들어주는 책을 만났다.

고마운 책이다.

서론은 여기까지 쓰고, 본격적인 개요를 작성하자면 우리 팀장님은 내 기술면접때 면접관이셨다.

그리고 나의 취업 기간동안 약 열 다섯번에 달하는 기술면접을 보면서 들었던 질문들과 내가 대답했던 질문들.

대기업, IT기업, 서비스기업 가리지 않고 들었었던 질문들은 신기하게도 꽤나 많이 중복되는 질문들이 많았다.

그 속에서 조금 알게된 것. 

질문의 형은 조금씩 달라도 기업에서 원하는 역량의 본질은 동일하다는 거. 

하지만 그 땐, 그 질문들이 가지는 의미보다 형태에 집착했고 (어떻게든 합격해야 했으니까) 깊게 다시 보기보다 

잘 모아뒀다 면접때마다 다시 답을 외우고 대답하기 일쑤였던 지난 날이었다.

물론 그 속에서 조금씩 더 한 걸음씩 이해가 나가기 시작했고 그 결과 어느 순간부터는 기술면접이 무섭지 않게 되었다.

하지만 언제나 질문을 들을 때마다 그 답에 대해서 깊게 이해한적은 없었던 것 같다. (이제와서 돌이켜보면)

그리고 팀장님과 매일매일 토론 과정을 거치면서 언제나 질문을 듣고 고민하고 찾아보고 해야하는 이 과정속에 조금씩

기술면접관이신 팀장님의 의도가 무엇인지 알게되었고, 과거에 들었던 질문들이 단순히 A = B다 라는 식으로 답이 아닌

왜 그렇게 해야하고, 왜 그 질문이 중요하고, 그 질문과 연결된 일들은 무엇이고, 이를 어떻게 활용하고 프로젝트에 담겼는지

조금씩 머리속에서 구체화되어가고 있다. (지금 생각해보면 기술면접을 자신있어하던 내 모습은 정말 패기로웠다. 이런 면에서는 면접때는 정말 지식보다도 그 면접관에서의 모습이 훨씬 중요한 게 아니었을까)

그래서 블로그에 하나씩 정리해서 올려보기로 한다.

잊어버리지 않도록, 그 기억을 까먹지 않도록.

그리고 혹시나 내 블로그에 찾아와 기술 면접을 어려워하는 이들이 이 글을 통해 조금이나마 도움될 수 있도록.

개요 끝.

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 열겨형을 통한 코드의 명확함이 가지는 강력함을 알았다.

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