좋은 면접관은 여러분이 모르는 언어로 코딩을 해보라 요구하지 않습니다. C++로 코딩해보라는 요구를 받았다면, 여러분 이력서에 여러분이 C++을 안다고 적어놓았기 때문입니다. 모든 API를 기억하지 못한다고 해도, 걱정할 필요 없습니다. 대부분의 면접관들은 거기에 대해서 그다지 신경 쓰지 않습니다. 하지만 관련된 질문들을 쉽게 풀 수 있도록, 기본적인 C++ 문법은 공부해 둘 것을 추천합니다.
1. 해시 테이블과 STL map을 비교하고 장단점을 논하라. 해시 테이블은 어떻게 구현되는가? 입력되는 값의 수가 적다면, 해시 테이블 대신 어떤 자료구조를 활용할 수 있겠는가?
해시 테이블 의 경우, 값은 키에 대해 해시 함수를 호출하여 저장한다. 값은 정렬된 순서로 보관되지 않는다. 또한, 해시 테이블은 값을 저장하는 첨자를 찾기 위해 키 를 사용한다. 삽입 및 탐색 연산은 거의 O(1) 시간에 수행된다(충돌이 적다는 가정하에). 해시 테이블의 경우, 잠재적으로 충돌이 발생할 수 있다는 사실을 고려하여 구현되어야 한다. 보통은 충돌되는 값들을 서로 연결하여 이 문제를 해결하는데, 특정한 첨자에 대응되는 키에 상응하는 모든 값을 연결 리스트로 묶어 관리해야 한다는 것을 의미한다.
STL map 은 키와 값 쌍을 키에 의해 만들어지는 이진 탐색 트리에 보관한다. 충돌을 처리할 필요가 없고, 트리의 균형이 유지되므로 삽입 및 탐색 시간은 O(logN) 이 보장된다.
해시 테이블은 어떻게 구현하나?
해시 테이블은 보통 연결 리스트 배열로 구현한다. 키와 값의 쌍을 저장하려면 키에 해시 함수를 적용하여 특정한 배열 첨자로 대응시킨 다음에 해당 위치에 있는 연결 리스트에 값을 삽입한다.
배열 내 특정 첨자에 해당되는 연결 리스트에 보관되는 값들이 동일한 키를 갖지 않음에 유의하자. 같은 것은 hashFunction(key) 값이다. 따라서 특정 키 값을 가지고 그에 상응하는 값을 추출하기 위해서는 각각의 노드에 값뿐만 아니라 키도 저장하여야 한다.
요약하면, 해시 테이블은 연결 리스트의 배열이며, 연결 리스트의 각 노드에는 키와 값이 저장 된다. 또한, 설계 시에 다음을 유의하여야 한다.
- 키들이 잘 분배되도록 좋은 해시 함수를 사용해야 한다. 키 값이 잘 분배되지 않으면 충돌이 많이 생길 것이고 특정한 원소를 찾는 성능이 떨어지게 된다.
- 아무리 우수한 해시 함수를 쓰더라도 충돌을 피할 수는 없기 때문에, 충돌을 처리하는 방법을 구현해야 한다. 연결 리스트를 통해 충돌된 키의 값들을 연결하는 것이 한 방법인데, 다른 방법도 있다.
- 용량에 따라 해시 테이블의 크기를 동적으로 늘리고 줄일 수 있어야 한다. 가령, 테이블 크기와 저장된 원소 수의 비율이 특정한 임계치(threshold)를 초과하면 해시 테이블 크기를 늘려야 할 수 있다. 그러려면 새로운 해시 테이블을 생성해 이전 테이블에서 새 테이블로 원소들을 옮겨야 할 수 있다. 그에 필요한 비용이 크기 때문에, 그런 일이 너무 자주 발생하지 않도록 신경 써야 한다.
입력되는 항목의 수가 적다면 해시 테이블 대신 무엇을 사용할 수 있겠는가?
STL map이나 이진 트리를 사용할 수 있다. O(logN) 시간이 걸리겠지만, 입력되는 데이터의 수가 적으므로 성능 저하는 무시할 만하다.
2. C++의 가상 함수 동작 원리는?
가상 함수는 vtable, 혹은 가상 테이블(virtual table)에 의존한다. 어떤 클래스의 함수가 virtual로 선언되면, 해당 클래스의 가상 함수 주소를 보관하는 vtable이 만들어진다. 컴파일러는 또한 해당 클래스의 vtable을 가리키는 vptr이라는 숨김 변수(hiddle variable)을 해당 클래스에 추가한다. 하위 클래스가 상위 클래스의 가상 함수를 오버라이드(override)하지 않으면 하위 클래스의 vtable은 상위 클래스의 가상 함수 주소를 보관한다. 이 vtable을 사용하여 가상 함수가 호출될 때 어느 주소에 있는 함수가 호출되어야 하는지를 결정하게 된다. C++의 동적 바인딩(dynamic binding)은 이 가상 테이블 메커니즘을 사용하여 실행된다.
따라서 하위 클래스 객체에 대한 포인터를 상위 클래스 객체에 대한 포인터에 할당하면, vptr 변수는 하위 클래스의 vtable을 가리키게 된다. 이렇게 배정했으므로 최하위 클래스의 가상 함수가 호출되는 것이다.
class Shape {
public:
int edge_length;
virtual int circumference() {
cout << "circumference of Base Class\n";
return 0;
}
};
class Triangle: public Shape {
dest.ptr = (char*)malloc(strlen(src.ptr) + 1);
strcpy(dest.ptr, src.ptr);
cout << "circumference of Triangle Class\n";
return 3 * edge_length;
};
void main() {
Shape *x = new Shape();
x->circumference(); // Shape의 circumference() 호출
Shape *y = new Triangle();
y->circumference(); // Triangle의 circumference() 호출
}
위의 예제에서 circumference는 Shape 클래스의 가상 함수다. 따라서 모든 하위 클래스(Triangle 등)에서도 circumference는 가상 함수가 된다. C++의 비-가상 함수에 대한 호출은 컴파일 시간에 정적 바인딩을 통해 처리되지만, 가상 함수에 대한 호출은 동적 바인딩을 통해 처리된다.
3. 깊은 복사(deep copy)와 얕은 복사(shallow copy)는 어떤 차이가 있는가? 이 각각을 어떻게 사용할 것인지 설명하라.
얕은 복사는 한 객체의 모든 멤버 변수의 값만 다른 객체로 복사한다. 깊은 복사를 시행하면 그뿐 아니라 포인터 변수가 가리키는 모든 객체에도 깊은 복사를 시행하게 된다.
struct Test {
char *ptr;
};
void shallow_copy(Test &src, Test &dest) {
dest.ptr = src.ptr;
}
void deep_copy(Test &src, Test &dest) {
dest.ptr = malloc(strlen(src.ptr) + 1);
strcpy(dest.ptr, src.ptr);
}
shallow_copy를 사용할 경우 프로그램 실행 시간에 객체 생성과 삭제에 관계된 많은 프로그래밍 오류가 발생할 수 있다. 따라서 얕은 복사는 프로그래머 자신이 무엇을 하려고 하는지 잘 이해하고 있다는 가정하에서 아주 주의 깊에 사용해야 한다. 대부분의 경우, 얕은 복사는 복잡한 자료구조에 관한 정보를 실제 데이터를 복제하는 일 없이 전달하고자 할 때 사용한다. 얕은 복사로 만들어진 객체를 삭제할 때에는 조심해야 한다.
실제로는 얕은 복사는 거의 사용하지 않는다. 대부분의 경우에는 깊은 복사를 사용해야 하며, 복사되는 자료구조의 크기가 작을 때에는 더더욱 그러하다.
4. C에서 volatile이라는 키워드는 어떤 중요성을 갖는가?
volatile 키워드는 컴파일러에게 해당 변수 값이 외부 코드에 의해 바뀔 수 있음을 알린다. 해당 변수를 선언한 코드 내부적으로 변경하지 않아도 바뀔 수 있다는 것이다. 해당 변수의 값은 운영체제에 의해, 하드웨어에 의해, 아니면 다른 쓰레드에 의해 변경될 수 있다. 그 값이 예상치 않은 순간에 변경될 수 있으므로, 컴파일러는 항상 메모리에서 해당 변수의 값을 다시 읽는다.
// volatile 정수 변수 선언
int volatile x;
volatile int x;
// volatile 정수 변수에 대한 포인터 선언
volatile int *x;
int volatile *x;
// volatile 변수가 아닌 변수를 가리키는 volatile 포인터 선언
int * volatile x;
// volatile 메모리에 대한 volatile 포인터 선언
int volatile * volatile x;
volatile 변수는 최적화되지 않는데, 그래서 유용할 수도 있다.
int opt = 1;
void Fn(void) {
start:
if (opt == 1) goto start;
else break;
}
척 보면 이 코드는 무한루프에 빠질 것 같다. 컴파일러는 이 코드를 다음과 같이 최적화 할 것이다.
void Fn(void) {
start:
int opt = 1;
if (true)
goto start;
}
무한루프다. 하지만 외부에서 opt의 값을 0으로 변경한다면 무한루프틑 풀릴 것이다. 컴파일러가 이런 최적화를 하는 것을 방지하기 위해, 시스템의 다른 부분이 특정한 변수의 값을 변경할 수 있음을 알리는 것이 가능한데, 이때 volatile을 사용한다.
volatile int opt = 1;
void Fn(void) {
start:
if (opt == 1) goto start;
else break;
}
volatile 변수는 공유 전역 변수의 값을 아무 쓰레드나 바꿀 수 있도록 허용하는 다중 쓰레드 프로그램을 작성할 때도 유용하다. 이런 변수에는 최적화가 적용되면 안 될 것이다.
5. 상위 클래스의 소멸자를 virtual로 선언해야 하는 이유는?
가상 함수라는 것이 왜 필요한 것인지부터 따져보자.
class Foo {
public:
void f();
};
class Bar : public Foo {
public:
void f();
};
Foo *p = new Bar();
p->f();
p->f()와 같이 호출하면 Foo::f()가 호출된다. p가 Foo에 대한 포인터이며, f()가 virtual로 선언되어 있지 않기 때문이다. p->f()가 Bar::f()를 호출하도록 하기 위해서는 f()를 가상 함수로 선언해야 한다.
이제 소멸자 문제로 되돌아가보자. 소멸자는 메모리와 자원을 반환하기 위해 쓰인다. Foo의 소멸자가 가상 소멸자로 선언되어 있지 않으면 Foo의 소멸자가 호출될 것이다. p가 Bar 객체를 가리킨다고 하더라도 말이다. 소멸자를 가상 함수로 선언해야 하는 것은 그래서이다. 포인터가 가리키는 객체의 실제 소멸자가 호출되도록 보장하고 싶은 것이다.
6. my2DAlloc이라는 함수를 C로 작성하라. 이 함수는 2차원 배열을 할당한다. malloc 호출 횟수는 최소화하고, 반환된 메모리를 arr[i][j]와 같은 형식으로 사용할 수 있도록 하라.
아시겠지만 이차원 배열은 결국 배열의 배열이다. 배열에 포인터를 사용하므로, 이차원 배열을 생성하려면 포인터의 포인터가 필요하다.
기본 아이디어는 포인터의 일차원 배열을 만드는 것이다. 그리고 그 포인터 각각에 새로운 일차원 배열을 생성하여 할당하는 것이다. 이렇게 하면 배열 첨자를 통해 접근 가능한 이차원 배열을 얻는다.
int** my2DAlloc(int rows, int cols) {
int** rowptr;
int i;
rowptr = (int**) malloc(rows * sizeof(int*));
for (i = 0; i < rows; ++i) {
rowptr[i] = (int*) malloc(cols * sizeof(int));
}
return rowptr;
}
이 메모리를 반환하려면 그냥 rowptr에 free를 호출해서는 안 된다. 첫 배열에 연결된 다른 배열도 반환해 주어야 하기 때문이다.
void y2DDealloc(int** rowptr, int row) {
for (i = 0; i < rows; ++i) {
free(rowptr[i]);
}
free(rowptr);
}
메모리를 여러 블록으로 나누어 할당하는 대신(행별로 한 블록을 할당하고, 그 각 행의 위치를 보관하는 브록 하나를 추가로 할당) 이를 연속된 메모리상에 배열하는 방법을 사용할 수도 있다. 개념적으로 보면, 다섯 개 행과 여섯 개 열로 구성된 이차원 배열은 다음과 같이 구성할 수 있다.
이차원 배열을 이런 식으로 표현해 놓고 보면 얼핏 이상하게 보이기도 하겠지만, 기본적으로 아까 살펴본 다이어그램과 차이가 없다는 데 유의하기 바란다. 유일한 차이점이라면 메모리가 하나의 연속된 블록으로 구성되어 있다는 것이다. 따라서 처음 다섯 원소는 같은 블록 내의 어딘가를 가리키게 된다.
int** my2DAlloc(int rows, int cols) {
int i;
int header = rows * sizeof(int*);
int data = rows * cols * sizeof(int);
int** rowptr = (int**)malloc(header + data);
if (rowptr == NULL) {
return NULL;
}
int *buf = (int*) (rowptr + rows);
for (i = 0; i < rows; ++i) {
rowptr[i] = buf + i * cols;
}
return rowptr;
}
위의 코드에서 for문을 주의 깊게 보기 바란다. 5x6 이차원 배열이라면, array[0]은 array[5]를 가리키고, array[1]은 array[11]을 가리킨다. 따라서 array[1][3]을 호출하면 컴퓨터는 array[1]을 뒤지는데, 사실 array[1]은 메모리 내의 다른 위치, 즉 5개 원소로 구성된 또 다른 배열을 가리키는 포인터다. 따라서 해당 배열의 3번째 원소(0부터 시작해서)를 취하면 된다.
이차원 배열을 이렇게 malloc을 한 번만 사용해서 구성하게 되면, 메모리를 반환할 때도 free를 단 한 번만 호출하여 반환할 수 있으므로 좋다.