[코딩 인터뷰]지식 기반 문제 - C와 C++ 문제

 

[ 해시테이블 vs STL map ]

1. 해시테이블과 STL map을 비교하여 장단점을 논하라.
2. 해시테이블은 어떻게 구현되는가?
3. 입력의 개수가 적다면, 해시테이블 대신 어떤 자료구조를 활용할 수 있겠는가?

1.

해시테이블	STL map
키에 대한 해시 함수를 호출하여 저장	키를 기준으로 만든 이진 탐색 트리에 키/값 쌍으로 저장
충돌 처리 필요(보통 체이닝 사용)	충돌 처리 필요 없음
삽입 및 탐색 시간(충돌이 적을 경우) O(1)	삽입 및 탐색 시간 O(log N)

 

2. 해시테이블은 보통 연결리스트 배열로 구현합니다. 키와 값의 쌍을 저장하려면 해시 함수를 사용해서 키 값을 배열의 인덱스 값으로 대응시킨 다음에 해당 위치에 있는 연결리스트에 값을 삽입합니다. 해시테이블은 연결리스트의 배열이며 연결리스트의 각 노드는 키와 값이 함께 저장되어 있습니다.

 

3. STL map이나 이진트리를 사용할 수 있습니다. 입력되는 데이터의 수가 적으므로 성능 저하는 무시할 수 있습니다.

 

 

[ 가상함수 ]

 C++의 가상 함수 동작 원리는?

 가상 함수는 가상 테이블(virtual table)에 의존합니다. virtual로 클래스가 선언되면 해당 클래스의 가상 함수 주소를 보관하는 vtable이 만들어집니다. 컴파일러는 또한 해당 클래스의 vtable을 가리키는 vptr이라는 숨겨진 변수를 해당 클래스에 추가합니다. 하위 클래스가 상위 클래스의 가상 함수를 오버라이드하지 않으면 하위 클래스의 vtable은 상위 클래스의 가상 함수 주소를 보관합니다. 이 vtable을 사용하여 가상 함수가 호출될 때 어느 주소에 있는 함수가 호출되어야 하는지를 결정합니다. C++의 동적바인딩은 이 가상 테이블 메커니즘을 사용하여 실행합니다.

 따라서 하위 클래스 객체에 대한 포인터를 상위 클래스 객체에 대한 포인터에 할당하면, vptr 변수는 하위 클래스의 vtable을 가리킵니다. 이렇게 최하위 클래스의 가상 함수가 호출되는 것입니다.

 

 

[ 얕은 복사 vs 깊은 복사 ]

1. 얕은 복사와 깊은 복사는 어떤 차이가 있는가?
2. 이 각각을 어떻게 사용할 것인지 설명하라.

1. 얕은 복사는 한 객체의 모든 멤버 변수의 값을 다른 객체로 복사합니다. 깊은 복사는 한 객체의 모든 멤버 변수의 값을 다른 객체로 복사하는 것뿐만 아니라 포인터 변수가 가리키는 모든 객체에 대해서도 복사합니다.

struct Test{
    char * ptr;
};
// 얕은 복사
void shallow_copy(Test & s1, Test & s2){
    s2.ptr = s1.ptr;
}
// 깊은 복사
void deep_copy(Test & s1, Test & s2){
    s2.ptr = (char*)malloc(strlen(src.ptr)+1);
    strcpy(s2.ptr, s1.ptr);
}

 

2. 얕은 복사를 사용할 경우 객체 생성과 삭제에 관련된 많은 오류가 발생할 수 있습니다. 따라서 얕은 복사는 주의해서 사용하여야 합니다. 대부분 얕은 복사는 실제 데이터를 복제하지 않고서 복잡한 자료구조에 관한 정보를 전달하고자 할 때 사용합니다. 실제로는 얕은 복사는 거의 사용되지 않습니다. 대부분의 경우에는 깊은 복사를 사용합니다.

 

 

[ volatile ]

 C에서 volatile이라는 키워드는 어떤 중요한 의미를 갖는가?

 volatile는 컴파일러에게 해당 변수의 값이 외부에 의해 바뀔 수 있음을 알려줍니다. 해당 변수를 선언한 코드 내에서 변경하지 않아도 바뀔 수 있습니다. 해당 변수의 값은 운영체제에 의해, 하드웨어에 의해, 아니면 다른 스레드에 의해 변경될 수 있습니다. 그 값이 예상치 않은 순간에 변경될 수 있으므로, 컴파일러는 항상 메모리에서 해당 변수의 값을 다시 읽어옵니다.

// volatile 정수 변수 선언
int volatile x;
volatile int x;

// volatile 정수 변수에 대한 포인터
volatile int * x;
int volatile * x;

// volatile 메모리에 대한 volatile 포인터를 선언할 때
int volatile * volatile x;

// votalie 변수는 다중 스레드 프로그램에 전역 변수가 존재하고
// 아무 스레드나 값을 바꿀 수 있도록 허용하고자 할 때 유용합니다.
volatile int opt=1;
void Fn(void){
  Start:
    if(opt == 1) goto start;
    else break;
}

 

[ 가상 상위 클래스 ]

상위 클래스의 소멸자를 virtual로 선언해야 하는 이유는 무엇인가?

 소멸자는 메모리와 자원을 반환하기 위해서 쓰입니다. 상위 클래스의 소멸자가 가상 소멸자로 선언되어 있지 않으면 하위 클래스에서 소멸자가 호출할 때 상위 클래스의 소멸자가 호출될 것입니다. 포인터가 가리키는 객체의 실제 소멸자가 호출되로고 보장하고 싶으면 상위 클래스의 소멸자를 virtual로 선언해야 합니다.