이글루스 메인페이지는 안 간지가 너무 오래되어서.. 암튼 이런 글이 이오공감에 올라왔단다.

programmer 채용 인터뷰: http://nether.egloos.com/1802229

암울한 현실이 쭉 나오다가 몇몇 잘못된 댓글이 넘쳐나서 바로 잡기 위해 이렇게 쓴다.

1. "구조체와 클레스의 차이점을 물어보는건 어떠십니까.. 이거도 난해합니다 ㅋㅋ"

=> 뭐 어떻게 보면 고교시절 교과서 귀퉁이에 있는 자잘한 내용을 "요건 몰랐지!" 하면서 골탕먹이는 문제 같습니다만, 이건 좋은 문제입니다. 실제 쌀나라 회사에서도 C++ struct와 class 차이는 꽤 묻죠. 난해한 것은 아닙니다. 이걸 모르는 이유는 (1) C++을 오래 써보지 않아서 한번도 C++ struct의 특성을 접할 기회가 없었거나 (2) 아니면 C++ 공부를 깊게 할 기회가 없어서 입니다.

"구조체는 자료의 집합이고, 클레스는 자료만이 아닌 메소드(행동)도 같이 있는게 차이점이려나요?"

=> 아닙니다.

"구조체도 내부에 함수를 가질 수 있는 것으로 알고 있습니다.."

=> 맞습니다.

"구조체와 클래스가 틀린 것은 캡슐화가 가능하고, 상속 가능한 객체라는 점으로 알고 있습니다.."

=> 아닙니다.

설명: C++에서 class/struct는 struct의 기본 접근자가 public, 클래스는 private인 것을 빼고는 100% 동일합니다. C++ struct에 멤버 함수 다 넣을 수 있고 상속 받고 다 할 수 있습니다. 참고로 MFC의 CPoint class 정의를 보면 struct tagPOINT에서 상속 받음을 알 수 있습니다. 제가 이걸 보고 처음으로 C++ struct가 C struct와 다르다는 걸 알았습니다.

"클래스는 레퍼런스 타입이라서 Heap 영역에 자리잡고, 구조체(Struct)는 밸류 타입으로 Stack 영역에 자리잡는 것으로 알고 있습니다."

=> 완전히 아닙니다. 죄송하지만 도대체 누구한테서 이런 말도 안되는 소리를 들었습니까!!! 혹시 C#이나 자바와 헷갈리신건지!! (C#/Java struct/class가 어떤지는 잘 모릅니다.) C#의 struct/class 차이로 이는 C/C++에서는 전혀 적용되지 않습니다.

2. "현역 프로그래머 중 O() 가 무엇인지를 아는 사람은 극소수"

=> O()라고 써본적은 없는데.. 암튼.. Big-Oh 표기법을 모르는 사람이 정말 저렇게 많다는 것은 거짓말로 믿고 싶습니다. Big-Oh는 어떤 알고리즘의 Asymptotic upper bound이고 little-Oh는 정의에서 등호가 하나 빠져서 일종의 loose upper bound를 뜻합니다.

수학으로 표기를 해야하는데 말로 대충 쓰자면: f(n)이 O(g(n))이라는 소리는 충분히 큰 모든 n에 대해, f(n) <= c*g(n)을 만족하는 정수 c가 존재한다... 가 되겠습니다. o 표기는 여기서 <=를 <로 바꾸면 됩니다.

그러니까 O 표기 값은 f(n)보다 적어도 같거나 빠른 속도로 증가하면 되고, 반면 o는 반드시 더 빠른 속도로 증가해야 합니다. 예를 들어, 어떤 알고리즘이 {2n^2 + 3logn}이라면 O(n^2)이 됩니다. 당연히 O(n^3)도 되지만 별로 재미가 없죠. 그래서 tight bound라는 개념이 또 있는데, 대충 이런 경우 O(n^2)가 타이트 바운드가 되겠습니다. 반면, o(n^2)는 정의에 따라 절대 안 됩니다. 최소한 o(n^(2+epsilon)) 아니면 o(n^2 ln) 정도가 되어야겠죠.

"어느 알고리즘을 실행하여 결과를 내는데 최악의 경우를 가정했을 때 (가령 이미 정렬이 완료된 배열을 퀵소팅할 때와 같은)의 시간복잡도입니다."

=> 맞습니다. Upper bound가 바로 그것을 가리키죠.

"반대로 스몰-o는 최고 좋은 효율을 냈을 경우의 시간복잡도 이죠."

=> 아닙니다. 그렇게치면 퀵소트의 o 표기는 o(nlogn)이 되어야겠죠.

사실 Big O 표기가 항상 유용한 것은 아닙니다. 퀵소트, 머지소트 모두 평균 O(nlogn) 이지만 숨어있는 constant factor의 차이로 퀵소트가 대게 훨씬 빠릅니다. 그래도 이건 기본이... Big-Oh도 모르니 Master's theorem을 아는 사람은 더 없을 것 같군요.. 소팅에서 stable이 어떤 의미인지도 모르는 친구들도 태반일 것 같고... 아 잘난체 했는데 혹시 틀린게 있을까봐 겁납니다.