문제 링크

• http://icpc.me/8983

제 4장 메모리

가. 메모리 영역의 구성 요소
메모리에는 여러 가지 영역이 있다. 그 중, 프로그램이 OS로부터 할당 받는 대표적인 메모리 영역은 크게 4가지 가 있다.
메모리의 낮은 주소(low memory)부터 높은 주소(high memory)까지 차례로
코드(Code) 영역, 데이터(Data) 영역, 스택(Stack) 영역, 힙(Heap) 영역이 존재한다.


나. 코드(Code) 영역
코드 영역에는 여러 데이터가 들어간다. 대표적인 것 들을 살펴보자면,
우리가 작성한 소스코드가 코드 영역에 저장이 된다. 물론 컴파일 된 기계어 형태로 저장이 된다. 또한, 상수 도 코드 영역에 저장이 된다.

다. 데이터(Data) 영역
데이터 영역은 프로그램 시작과 함께 메모리에 적재되며, 프로그램 종료 시 메모리에서 해제가 된다. 이러한 특성을 가지고 있는 전역 변수와 정적 변수가 데이터 영역에 저장이 된다. 또한, 구조체도 데이터 영역에 저장이 된다.
참고로, 초기화 되지 않은 데이터는 BSS(Block Stated Symbol) 영역에 저장이 되고, 초기화 된 데이터만 데이터 영역에 저장된다.

라. BSS 영역
앞에서 서술한 대로 BSS(Block Stated Symbol) 영역에는 초기화가 되지 않은 데이터 들이 저장이 된다.
BSS영역에는 실제 변수가 차치할 공간이 할당되지 않아 그 만큼 binary size가 작아진다.

마. 스택(Stack) 영역
스택 영역은 함수 호출과 관계가 있는 각종 변수 가 저장되는 영역이다. 함수가 호출될 때 스택에 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소 값, 해당 함수에서 선언이 된 지역 변수가 저장이 된다. 이렇게 스택 영역에 저장되는 함수의 호출 정보를 스택 프레임이라 한다.

```cpp void f () { //something }

저자

• 선린인터넷고등학교 소프트웨어과, Unifox 10기 나정휘

지난 글에서는 이진트리의 간단한 구현 방법을 다뤘습니다.
이번 글에서는 이진트리의 전위, 중위, 후위 순회에 대해 알아봅시다.

구조체 포인터를 활용한 구현

전에 Left-Child Right-Sibling 방식을 다룬 적이 있습니다.
이 방법은 각 노드의 차수가 다양할 때 생기는 문제를 해결해주었습니다.
하지만, 이진트리는 차수가 0, 1, 2 중 하나이기 때문에 LCRS 방식을 쓰지 않아도 비교적 간단하게 나타낼 수 있습니다.

이진트리란?

지난 글에서는 차수가 N인 트리의 대하여 설명했습니다. 이 글을 포함해서 앞으로 몇 개의 글에서는 트리 중에서도 차수가 2 인 이진트리만을 다루겠습니다.
이진 트리는 차수가 2 인 트리입니다. 영어로는 Binary Tree입니다.

트리는 꽤 다양한 방법으로 표현할 수 있습니다.

트리란?

트리(tree)는 이름을 보면 아시겠지만, 나무를 닮은 구조를 가진 자료구조입니다. 나무는 뿌리, 가지, 잎 등으로 구성이 되어 있습니다. 트리 구조도 실제 나무처럼 뿌리, 가지, 잎을 가지고 있습니다.

교착상태

• 두 개 이상의 작업이 다음에 진행되어야 할 작업과 맞물려 서로가 끝나기만을 기다리기 때문에 아무것도 완료하지 못하는 상태
• 다중프로그래밍 시스템에서, 한 프로세스가 자원을 요청할 때 그 자원을 사용할 수 없으면 프로세스가 대기상태로 들어감
  

가상 기억 장치

• 가상기억장치 : 현재 사용중인 프로그램의 일부를 주기억장치에 유지하고 나머지는 보조기억장치에 유지
• 사용자가 보조기억장치의 용량만큼 기억장소를 갖고 있는 것처럼 프로그램 작성 가능
• 사용자 프로그램이 물리 메모리보다 커져도 됨