[자료구조] 덱

덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 그렇지만 여전히 중간에 삽입하거나 삭제하는 것은 허용하지 않는다. 덱의 추상자료형 객체 : n개의 element형의 요소들의 순서 있는 모임 연산 : create() ::= 덱을 생성한다. init(dq) ::= 덱을 초기화한다. is_empty(dq) ::= 덱이 공백 상태인지를 검사한다. is_full(dq) ::= 덱이 포화 상태인지를 검사한다. add_front(dq, e) ::= 덱의 앞에 요소를 추가한다. add_rear(dq, e) ::= 덱의 뒤에 요소를 추가한다. delete_front(dq) ::= 덱의 앞에 있는 요소를 반환한 다음 삭..

[자료구조] 큐

스택의경우, 나중에 들어온 데이터가 먼저 나가는 구조인데 반하여 큐(queue)는 먼저 들어온 데이터가 먼저 나가는 구조로 이러한 특성을 선입선출(FIFO: First-In First-Out)이라고 한다. 큐의 예로는 매표소에서 표를 사기 위해 늘어선 줄을 들 수 있겠다. 줄에 있는 사람들 중 가장 앞에 있는 사람(즉 가장 먼저 온 사람)이 가장 먼저 표를 사게 될 것이다. 나중에 온 사람들은 줄의 맨 뒤에 서야 할 것이다. 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다. 구조상으로 큐가 스택과 다른 점은 스택의 경우, 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다는 것이다. 위의 그림과 같이, 큐에서 삽입이 일어나는 곳을 후..

[자료구조] 스택

1. 스택이란? 책상에 쌓여있는 책, 창고에 쌓여있는 상자등이 스택의 전형적인 예이다. 새로운 상자를 쌓을 때는 상자더미의 맨 윗부분에 놓을 것이고, 상자가 필요하면 상자더미의 맨 위에 있는 상자를 꺼낼 것이다. 만약 중간에서 상자를 꺼내면 전체 상자 더미가 붕괴될 것이다. 따라서 가장 최근에 들어온 상자가 가장 위에 있게 되고, 또 먼저 나가게 된다. 이런 입출력 형태를 후입선출(LIFO : Last-In First-Out)이라고 한다. 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 위 그림처럼 스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고 반대쪽인 바닥부분을 스택 하단(stack bottom)이라고 한다. 스택에 저장되는 것을 요소(..

[자료구조] 배열

배열 배열의 개념 배열은 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용된다. 예를 들어서 6개의 정수를 저장할 공간이 필요한 경우, 배열이 없다면 다음과 같이 6개의 정수형의 변수를 선언하여야 할 것이다. int list1, list2, list3, list4, list5, list6 그러나 배열이 지원된다면 아주 간단하게 다음과 같이 선언하면 된다. int list[6] 배열을 사용하면 "연속적인 메모리 공간"이 할당되고 인덱스(index) 번호를 사용하여 쉽게 접근이 가능하기 때문에 반복 루프를 이용하여 여러가지 작업을 손쉽게 할 수 있다. 배열 ADT(추상 자료형) 배열을 추상 자료형으로 정의하여 보자. 즉 배열을 단순히 "연속적인 메모리 공간"으로만 보지 말고 배열의 핵심적인 내용을 추상..

[C] 4가지의 메모리 저장소 (스택, 힙, 데이터, 코드 영역)

프로그램을 수행하기 위해서는 메모리 공간이 운영체제(Operating system)에 의해 코드 영역, 데이터 영역, 힙 영역, 스택 영역 이렇게 4개의 영역으로 구분되어 사용된다. 이렇게 변수의 특성에 따라 4개로 구분된 메모리 공간 안에서 한 영역에 변수가 선언되고, 문자열 등이 선언되어 사용된다. 코드 영역 : 프로그램의 코드가 저장되는 메모리 공간이다. 컴퓨터는 코드 영역에 저장된 명령문을 하나씩 가져가서 실행한다. 데이터 영역 : 데이터 영역에는 전역 변수와 스택 변수가 할당된다. 프로그램의 시작과 동시에 메모리 공간에 할당되어 프로그램이 종료될 때까지 남아 있다. 힙 영역 : 데이터 영역과 스택 영역에 할당되는 변수는 생성과 소멸 시점이 결정되어 있다. 개발자가 원하는 시점에 변수를 할당하고 ..

[C] C언어에서 음수를 표현하는 방법

1. -10은 메모리 비트에 어떻게 저장될까? 먼저, 10진수 10을 저장하려면 2진수 1010으로 변경한 다음 비트에 저장된다고 알고 있다. 그런데 음수는 어떻게 표현해야 할까? 2. 양수와 음수를 구분하기 위한 부호와 절대치 법칙 다른 말로 MSB(Most Significant Bit) 방법이라고도 하는데, 이는 최상위 비트를 사용하여 숫자가 양수인지 음수인지를 구분하는 방법이다. 1 0 0 0 1 0 1 0 최상위비트 MSB가 1이므로 음수 0 0 0 0 1 0 1 0 최상위비트 MSB가 0이므로 양수 비트 연산자 ~는 '1의 보수'이다. 1의 보수는 2진수로 된 숫자의 비트를 모두 반전시키는 것이다. 예를 들어 ~(1010)은 (0101)이 된다. 다시 말해 (1010)의 1의 보수 값은 (010..

컴파일(Compile) 과정

전처리(Precompile) 컴파일의 전체 과정은 네 단계로 나누어볼 수 있습니다. 그 중 첫 번째 단계는 전처리인데, 전처리기에 의해 수행됩니다. # 으로 시작되는 C 소스 코드는 전처리기에게 실질적인 컴파일이 이루어지기 전에 무언가를 실행하라고 알려줍니다. 예를 들어, #include는 전처리기에게 다른 파일의 내용을 포함시키라고 알려줍니다. 프로그램의 소스 코드에 #include 와 같은 줄을 포함하면, 전처리기는 새로운 파일을 생성하는데 이 파일은 여전히 C 소스 코드 형태이며 stdio.h 파일의 내용이 #include 부분에 포함됩니다. 컴파일(Compile) 전처리기가 전처리한 소스 코드를 생성하고 나면 그 다음 단계는 컴파일입니다. 컴파일러라고 불리는 프로그램은 C 코드를 어셈블리어라는 저..

[C] 모두의 C언어 복습&정리 (2)

1. 변수의 저장 범위 int는 정수를 저장하는 데 필요한 메모리 공간을 4바이트 사용한다. 컴퓨터는 모든 정보를 0과 1, 즉 2진수로 처리한다. 이때 0 또는 1을 저장할 수 있는 메모리 공간을 비트(bit)라고 한다. 비트는 컴퓨터가 정보를 저장하는 최소 공간으로, 8개의 비트가 모인 공간을 바이트(byte)라고 한다. 그러므로 4바이트는 32비트와 같다. 1비트로 표현 가능한 숫자는 0과 1 두 개 뿐이다. 2비트로 표현 가능한 숫자는 2진수 00, 01, 10, 11, 즉 10진수로 0, 1, 2, 3을 표현하고 저장할 수 있다. 그러므로 n비트로 저장 가능한 숫자의 범위는 0 ~ 2ⁿ(n은 비트의 개수) - 1까지 이다. 4바이트는 32비트이므로 양의 정수로만 표현할 수 있는 숫자는 4,294..