힙과 스택

내가 면접 때 많이 들어봤던 질문 중의 하나였다.

“힙과 스택에 대하여 설명해보세요.”

C/C++을 공부하면서 당연히 배우는 과정 중의 하나인데 문제는 이런 내용은 C 처음 배울 때 나온 내용이라 기억의 저편으로 멀리 가버렸다는 점. 기억을 되살리기 위해 다시 정리해본다.

스택의 특징은…

  • 프로그램이 자동적으로 할당한 메모리 영역이다.
  • 자동변수와 파라미터들이 생성되고 스코프가 끝나면 사라지는 메모리 영역.
  • 함수가 실행된 뒤 원래 실행위치로 돌아오는 리턴값 역시도 스택에 저장된다.
  • 함수 안에서 선언된 변수는 모두 스택으로 들어간다.
  • 함수를 호출했을 때 현재 상태에 대한 값도 스택으로 들어간다.
  • LIFO 구조를 가진다. 먼저 들어간 자료가 가장 나중에 나오게 되며, 가장 나중에 들어간 자료가 가장 처음에 나오게 된다.
  • 윈도우 프로그램의 경우 기본 스택메모리의 크기는 1MByte이다.
  • 스택의 크기를 넘어가게 되면 Page Fault 인터럽트(즉, 스택오버플로우)가 발생하게 된다.
  • 모든 포인터 역시도 스택에 올라간다. 포인터 역시도 하나의 변수라는 것을 잊지말 것.
  • 사용할 스택의 크기는 컴파일 하는 순간 모두 정해진다. 따라서 실행 도중 메모리의 크기를 변경할 수 없다.
  • 스레드가 여러개라면 각 스레드마다 고유한 스택영역이 준비된다.
  • 하나의 메소드를 실행하기 위한 스택메모리의 묶음을 스택프레임이라고 부른다.
  • 어떤 변수를 선언했다면 변수명 자체는 스택에 변수 내용은 힙에 저장된다.

힙의 특징은…

  • 프로그래머가 스스로 할당한 메모리 영역이다.
  • 힙은 프로그램이 동적으로 할당받아 사용되는 메모리 영역. C에서의 malloc을 통해 생성하고 free를 통해 해제하며 C++에서는 new를 통해 생성하고 delete를 통해 메모리를 해제한다.
  • 힙 메모리가 부족하게 되면 메모리 이상현상으로 프로그램은 종료되게 된다.
  • 사용할 힙의 크기는 프로그램 실행 중 정해진다.
  • 동적 메모리할당은 프로그램 사용자들이 얼마나 데이터를 입력할지 예측할 수 없는 경우에 사용한다.
  • 여러 스레드가 있는 경우 힙 영역은 각 스레드가 공통으로 사용할 수도 있다.

이외에도 데이터영역과 텍스트영역(코드영역)이 있다.

데이터영역의 특징은…

  • 프로그램이 실행되고 난 후 종료될 때 까지 지워지지 않을 메모리 공간이다.
  • 따라서, 전역변수, Static 변수 등이 저장된다.
  • 프로그램당 한개의 영역이 할당된다.

텍스트영역(코드영역)의 특징은…

  • 프로그램의 실행코드를 저장한다. 프로그래머가 만든 코드, 함수는 모두 여기에 저장된다.
  • 역시 프로그램당 한개의 영역이 할당된다.

 

위의 내용들을 찾을 수 있었다. 다시금 찾아보니 생각보다 내용도 많고 차이점도 여러가지인 것 같다. 앞으로 더 찾아보며 여기에 추가해야겠다.

 

<참고자료>

  • http://blog.naver.com/brosvaby?Redirect=Log&logNo=165225008
  • http://panic.kldp.org/node/199
  • http://blog.naver.com/ysjin1212?Redirect=Log&logNo=110128934379
  • http://blog.naver.com/0bloodwind0?Redirect=Log&logNo=20127908176
  • http://blog.naver.com/zelet7?Redirect=Log&logNo=140015294688

랜덤확수의 확률 변경과 분포에 대한 문제

이 질문 역시 내가 면접에서 질문 받았던 문제이다. 틀렸던 문제를 다시 한번 살펴보고 공부하는 차원에서 오답노트에 적어둔다. (Q는 면접관님, A는 내가 답변한 것이다. 존칭은 생략한다.)

Q. 랜덤함수에서 0과 1이 나올 확률이 같은가?
A. 같다. 내가 알기로는 0~1까지의 소수가 나오는 것으로 알고 있다. (여기서 대답을 잘못했다. 플래시의 랜덤함수와 C에서의 랜덤함수를 헷갈렸던 것이다.)
Q. 정말? 그렇다면 0~10까지 나오게 하려면 어떻게 해야하는가?
A. r이 그 랜덤함수값이라고 한다면 (int)(r * 10)으로 구할 수 있다.
Q. 그렇게 한 경우에는 0~10까지 모든 수가 나올 확률은 같은가?
A. 같다고 알고 있다.
Q. 만약 1~5까지의 어떤 수를 뽑는 랜덤함수가 있다면 확률을 바꾸고 싶다. 1,5는 가장 적게 나오도록, 2,4는 그다음으로 많이 나오도록 3은 제일 많이 나오도록 결과적으로는 확률분포가 삼각형 모양이 되게 하고 싶다. 어떻게 하면 되겠는가?

여기까지가 질문이었는데 확률을 바꾸라는 말에 제대로 대답을 못했다.

일단 첫번째는 랜덤함수는 0~1까지의 소수가 나오는 것이 아니었다. 그리고 랜덤함수의 확률 분포는 생각보다 그렇게 고르지 않다고 한다. (이에 대한 자료는 http://agebreak.tistory.com/49 와 http://ljh131.tistory.com/131 에 있다.) 내 생각에는 랜덤을 반복할 수록 점점 확률이 고르게 분포하지 않을까 싶다.

위 면접관분이 질문했던 내용을 찾아보니 정확하게는 균등분포를 정규분포로 바꾸는 문제였다. 이에 대한 자료는 http://tadis.tistory.com/14 를 참조하면 될것 같다. 그런데 이 코드를 봐도 sqrt는 알겠지만 log 등을 사용하는 구간에서 잘 이해가 안된다. 더군다나 이 코드는 내가 확률을 조정하기보다는 정규분포에 맞추어 바꿔주는 역할을 하는 코드인 것 같다.

다음은 간단히 1부터 5까지 랜덤한 수를 100000개 뽑아보는 코드다.

#include <iostream>
#include <time.h>

using namespace std;
#define MAX_TEST 100000
int main()
 {
 int count[5] = {0};
 int percent[5] = {10, 20, 40, 20, 10};
srand((unsigned)time(NULL));
 for (int i = 0; i < MAX_TEST; i++)
 {
 int r = rand() % 5 + 1;
 count[r - 1]++;
 }
float total = 0.0;
 for (int i = 0; i < 5; i++)
 {
 cout << i + 1 << "의 갯수 :: " << count[i] << " - " << count[i] / (float)(MAX_TEST / 100) << "%" << endl;
 total += (count[i] / (float)(MAX_TEST / 100));
 }
return 0;
 }

여기서 알 수 있는건 분포가 정확하게 20%씩은 아니라는 점이었다.

이 코드를 1부터 5까지 랜덤한 수를 정해진 비율에 맞도록 100000개 뽑아내는 코드로 변경한 것이다.

#include <iostream>
#include <time.h>
using namespace std;
#define MAX_TEST 100000
int main()
 {
 int count[5] = {0};
 int percent[5] = {10, 20, 40, 20, 10};
srand((unsigned)time(NULL));
 for (int i = 0; i < MAX_TEST; i++)
 {
 int r = rand() % 100;
if (r < 10)
 {
 count[0]++;
 }
 else if (r < 30)
 {
 count[1]++;
 }
 else if (r < 70)
 {
 count[2]++;
 }
 else if (r < 90)
 {
 count[3]++;
 }
 else if (r < 100)
 {
 count[4]++;
 }
 }
 for (int i = 0; i < 5; i++)
 {
 cout << i + 1 << "의 갯수 :: " << count[i] << " - " << count[i] / (float)(MAX_TEST / 100) << "%" << endl;
 }
return 0;
 }

단순히는 이렇게 하면 정해진 비율에 유사하게 값이 나온다.

추가로 난수발생에 대한 좋은 글들은 http://oops.kldp.org/node/103420 , http://agebreak.tistory.com/49 , http://terzeron.net/wp/?p=1006 에서 찾을 수 있었다.

비율이 유사하게가 아니라 정확한 비율대로 나오려면 배열에 미리 가능한 수를 넣어놓고 랜덤하게 위치를 변경시키는 방법 밖에는 아직 생각나지 않는다. 조금 더 생각하고 공부해봐야 할 문제인 것 같다.

데드락 현상이란?

이 질문은 내가 여기저기 입사지원을 하고 면접을 보고 시험을 볼 때마다 매번 나왔던 질문과 문제들이다. 처음 한번은 이 문제에 대답을 못했고 그다음 다시 공부한 다음 다음번부터는 잘 대답했다.

신기한건 이 질문은 내가 면접을 본 몇군데 회사의 기술면접, 실기, 필기시험 때마다 매번 나온 문제였다. 프로그래머라면 반드시 알아야할 문제라고 생각해두자.

데드락 현상은 교착 상대라고도 하는데 예를 들어, A와 B라는 두개의 스레드가 있을 때 A 스레드는 B의 실행결과를 받아야만 종료할 수 있고 B 스레드는 A 스레드의 실행결과를 받아야만 종료할 수 있다면 두개의 스레드는 영원히 종료될 수 없고 죽지 않는 스레드로 영원히 남게 된다. 이런 현상을 데드락 현상이라고 한다.

한줄로 대답하자면 두 스레드가 서로의 실행결과를 무한히 기다리는 현상이라고 답할 수 있을 것 같다.

특히 모 게임회사에서 네트워크 게임을 만들 때 데드락 현상에 빠지지 않았느냐고 물어봤는데 아직까지는 그런적이 없다고 말했더니 면접관분이 갸우뚱하셨다. 이 문제에 대해 선생님께 질문 해본 결과 윈도우소켓이 알아서 처리하기 때문에 그런 현상이 안 생겼던 것이라고 답해주셨는데 아직 잘 이해가 가지 않는다. 검색해봐도 이런 내용에 대한 답은 찾을 수 없는데 계속 더 공부해봐야 할만한 내용인 것 같다.

오버로딩과 오버라이딩의 차이

이 질문도 내가 면접을 보며 나왔던 문제인데 막연히 알고 있던 내용이라 더 정확히 알고 나중에 다시 공부하기 위해 적어놓는다.

오버로딩과 오버라이딩의 차이에 대해 설명하여 쓰라는 질문이었다.

사실은 플래시와 자바를 쓸 때 인터페이스 구현 때문에 오버라이딩만 계속 써왔고 C++를 할 때는 연산자 오버로딩 외에는 오버로딩에 대해 아는게 없기도 하고 용어가 헷갈려서 정확하게 답변하지 못했었다. 두개를 비교설명하자면 복잡하지만 다음의 두 문장으로 정리할 수 있을 것 같다.

  • 오버로딩은 클래스 안에서 파라미터가 다른 여러개의 같은 이름을 가진 함수를 정의하는 것.
  • 오버라이딩은 어떤 클래스를 상속 받은 경우, 부모클래스의 함수를 다른 내용으로 재정의 하는 것.

이렇게 짧게 정리할 수 있을 것 같다.

참고한 자료는 http://blog.naver.com/jwlee0208?Redirect=Log&logNo=10136772809 , http://zzing8300.tistory.com/127 에서 볼 수 있다. 이 두 페이지만 봐도 도움이 많이 될 것 같다.

클래스와 구조체의 차이

이 질문은 내가 면접을 보러다니던 당시 받았던 질문들이며 내가 제대로 답하지 못했다고 생각하는 것이다. 이 문제에 대해 더 공부하고 잊지 않기 위해 여기에 써둔다.

Q. 클래스가 무엇인가?
A. 같은 성질을 같은 데이터와 함수들의 집합체이다.
Q. 그럼 구조체 역시도 데이터와 함수를 가질 수 있다. 클래스와 동일하게 구조체로도 만들 수 있는데 왜 클래스를 사용하는가?
A. 클래스는 상속이 가능하지만 구조체는 불가능하다.
Q. 구조체 안에 구조체를 넣을 수 있지 않는가?
A. 그렇다.

이 질문에 난 대답을 제대로 못했다. 생각해보니 구조체와 클래스는 비슷한 점이 많은 것 같은데 정확히 차이점을 찾아본 적이 없었다.

검색엔진 등을 통해 구조체와 클래스의 차이점을 찾아본 결과는 다음과 같다.

  1. 클래스와 구조체는 데이터타입을 생성한다는 점에서 유사하다.
  2. 구조체는 기본접근자가 public인데 클래스의 기본접근자는 private이다.
  3. 구조체는 데이터의 초기화가 불가능하지만 클래스는 데이터의 초기화가 가능하다.
  4. 구조체는 데이터의 value가 복사되지만 클래스는 데이터의 reference가 복사된다. 따라서 클래스는 얕은 복사가 일어나고 구조체는 깊은 복사가 일어난다.
  5. 구조체는 상속해줄 수도 상속 받을 수도 없다.
  6. 구조체를 그럼에도 사용하는 이유는 참조의 낭비를 막을 수 있으며 데이터에 직접 접근하기 때문에 속도가 더 빠르다.
  7. 구조체는 함수의 재정의가 안된다.

제일 중요한 점은 reference/value 복사의 차이가 아닌가 싶다. 이에 대한 설명은 http://rintiantta.blog.me/40114721626 에 가장 잘 나와있다. 이 코드를 보면 이해가 한번에 되는 것 같다.

클래스의 경우에는 어떤 클래스의 타입을 가지는 A객체를 만들고 B라는 객체가 A객체와 동일하게 복사한 다음, A객체의 값을 변경하면 B객체의 값도 변경된다. (reference 즉, 메모리주소가 복사되므로)

구조체의 경우에는 어떤 구조체의 타입을 가지는 A객체를 만들고 B라는 객체가 A객체와 동일하게 복사한 다음, A객체의 값을 변경하면 B객체의 값은 변경되지 않는다. (value, 즉, 값 자체가 복사되므로 B객체의 값은 변경되지 않는다.)

<참고자료>

http://blog.naver.com/fsclub2307?Redirect=Log&logNo=130113830445
http://rintiantta.blog.me/40114721626
http://cafe.naver.com/mbcasp/181

지하철에 개찰구는 왜 들어가는 곳보다 나오는 곳이 더 많을까?

이 질문은 내가 N모 게임회사의 기술면접 때 받았던 질문이다. 당시에는 제대로 대답하지 못했지만 내가 몰랐던 부분을 다시 생각해보고 기억해놓기 위해 오답노트에 써둔다.

Q는 면접관님이 나에게 했던 질문이고 A는 내가 대답한 것이다. (존칭은 생략)

Q. 올 때 지하철을 타고 왔나?
A. 그렇다.
Q. 지하철에 개찰구는 왜 들어가는 곳보다 나오는 곳이 많을까?
A. 원래는 수가 같은게 정상이고 현재는 출퇴근시간, 역특성에 따라 유동적으로 조정한다. 최근에는 하나의 개찰구로 나올 수도 들어갈 수도 있게 되어있다.
Q. 만약 그렇지 않고 일반적인 경우(그러니까 이건 예전 지하철 개찰구를 말한다. 나오는 곳과 들어가는 곳이 고정되어있는 경우)에는 들어가는 곳이 많을까 나오는 곳이 많을까?
A. 지금까지 관찰해본 결과, 나오는 곳이 많았다.
Q. 왜 그럴까?

여기까지였고 더이상 대답하기 어려웠다. 몇가지 힌트를 면접관분이 해주셔서 결국에는 답을 말했지만 어찌됐던 좋은 대답은 하지 못했던 것 같다.

집에 오며 관찰해본 결과 강남역의 경우에도 나오는 개찰구가 들어가는 개찰구보다 더 많았다. 다른 지하철역 몇군데도 그러했고 아마 다른 지하철역의 경우에도 마찬가지일 것이다.

집에 돌아오면서 곰곰히 생각해보고 경제학, 수학에 능한 누나와 대화해본 내가 내린 결론은 이렇다.

현재는 내가 대답한대로 최근에는 하나의 개찰구로 들어가는 것과 나오는 것이 가능하고 인구의 변화, 역특성에 따라 조정하는게 맞다. 그렇게 되어있지 않은 옛날 개찰구 방식이라면 나가는 개찰구가 더 많은데 그 이유는 지하철의 특성 때문이다.

지하철의 경우에는 승객이 타러 들어갈 때에는 입구가 하나이고 승객이 한명씩 들어가도 플랫폼에서 기다리게 되므로 상관이 없지만, 지하철이 역에 도착하여 승객이 내리는 경우에는 한번에 많이 내리게 된다. 그렇기 때문에 나오는 개찰구의 수가 더 적다면 승객은 나오지 못하고 개찰구 앞에서 밀리게 된다. 여기서 중요한 것은 승객이 들어가는 경우에는 한명씩 들어가도 상관이 없지만 내리는 경우에는 ‘한번에 많이’ 내리게 된다는 점이다.

더 생각해보니 이걸 프로그래밍과 연관지어보면 입력과 출력이 동시에 일어날 때 출력은 기다리다가 폭발적으로 일어나고 입력은 천천히 지속적으로 일어나는 경우라고 생각된다. 이런 경우 지하철 플랫폼이 일종의 버퍼 역할을 해준다고 볼 수 있을 것 같다.

위 질문을 받았을 때 이렇게 생각했다면 좋았겠지만 그떈 너무 당황하고 긴장해서 제대로 답하질 못했다. 승객이 내릴 때와 승객이 승차하러 들어갈 때의 차이점마저 설명하지 못했고, 그러니 프로그래밍과 연관지어 생각해볼 수도 없었다.

상당히 재미있는 질문이었다. 일상생활에서 일어나는 일을 별 생각해보지 않고 지냈는데 이 일을 계기로 모든 일을 논리적으로 생각해봐야겠다는 생각이 든다. N사의 면접관님께 감사드리며.