gnuykob_sw

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

1. 다차원 배열

- 2차원 이상의 배열을 다차원 배열이라고 한다.

- 논리적으로는 m차원이지만, 물리적으로는 1차원으로 메모리 상에 표현됟나.

- m차원 배열 A : int A[n₀][n₁] ··· [nₘ₋₁];

- 배열 A에 저장되는 원소의 총 개수 : n₀ x n₁ x ··· nₘ₋₁

   예를 들어 A[10][9][8]로 선언된 배열 원소의 총 개수는 10 x 9 x 8 = 720개이다.

1-1. 행 우선 순서 (Row-major order)

- 기본 주소에서부터 행을 기준으로 원소가 저장된다. 

- 배열 원소의 오른쪽 차원의 인덱스가 먼저 증가되고, 상한 경계에 도달하면 바로 왼쪽 옆자리가 1씩 증가된다.

- 이런식으로 인덱스 값이 오른쪽에서 왼쪽 방향으로 증가하면서 메모리에 저장된다.

- (ex) A[0][0] → A[0][1] → A[1][0] → A[1][1] → A[2][0] → A[2][1]

1-2.  열 우선 순서

- 열을 우선적으로 채워가는 형식이다.

- 배열 원소의 왼쪽 차원의 인덱스가 먼저 증가되고, 상한 경계에 도달하면 바로 오른쪽 옆자리가 1씩 증가된다.

- (ex) A[0][0] → A[1][0] → A[2][0] → A[0][1] → A[1][1] → A[2][1]

2. 원소의 주소

2-1. 1차원 배열

- 원소의 위치는 시작주소(α) + 오프셋(offset) 값으로 계산된다.

- n개의 원소를 가지고 있는 1차원 배열 A의 시작 주소가 α이고, 각 원소에 s바이트가 할당된다고 할 때,

 &A[0] = α + 0 * s

 &A[1] = α + 1 * s

 ...

 &A[n-1] = α + (n-1) * s

→ &A[i] = α + i * s

2-2. 2차원 배열

- A[u₀][u₁]으로 선언된 2차원 배열에서 A[i][j] 주소는 α + (i * u₁ + j) * s 이다.  // 행 우선 순서일 때

- 열 우선 순서일 때의 주소는  α + (i + u₀ * j) * s 이다.

2-3. 3차원 배열

- A[u₀][u₁][u₂] 으로 행 우선 순서로 선언된 2차원 배열에서 A[i][j][k]의 주소는 α + (i * u₁ * u₂ + j * u₂ + k) * s이다.

- 열 우선 순서로 저장된 배열의 주소는 α + (i * u₁ * u₂ + j + u₁ * k) * s이다.

3. Stack 스택

- 선형 리스트의 특별한 형태로, 한 방향으로 쌓아둔 것을 의미한다.

- 후입 선출 구조이다. (LIFO : Last-In, First-Out)

- 함수 호출 관리, 문법 검사, 연산식 평가 등에 활용된다.

- S = [a₀, a₁, ..., aₙ₋₁] 형식으로 원소들의 리스트로 정의할 수 있다.

- aₙ₋₁ 이 가장 나중에 삽입된 원소이다.

- 스택에 원소를 추가하는 연산을 "push"라고 하고, 원소를 삭제하는 연산을 "pop"이라고 한다.

- top 포인터는 가장 나중에 삽입된 원소를 가리키며, 그 위치에 해당하는 배열 인덱스 값을 갖는다.

- 빈 스택에서 top 포인터는 -1 값을 갖는다.

- 1차원 배열로 구성된 스택에 최초로 들어오는 원소는 stack[0]에 저장된다.

- (ex) Function Call

    - A()가 실행 중일 때 B를 호출하면, B()가 끝날 때까지 A()는 멈춰있다.

    - 새로운 함수가 실행될 때마다 현재 실행 중인 함수의 환경 변수를 시스템 스택에 Stack Frame 형태로 저장해야 한다.

    - Stack Frame (Activation record)

        - 지역 변수

        - 재개할 때 다음에 실행될 명령어의 주소

        - 이전 stack frame의 포인터

#define STACK_SIZE 100
int stack[STACK_SIZE];
int top = -1;

void push(int item);
int pop;
void print_stack();

void main() 
{
    push(3);
    push(4);
    push(5);
    pop();
    print_stack();
    pop();
    print_stack();
    pop();
    print_stack();
    pop();
    print_stack();
}

void print_stack()
{
    int i;
    for(i = 0; i <= top; i++)
        printf("%d", stack[i]);
    
    printf("\n");
}

void push(int item)
{
    if (top >= STACK_SIZE - 1){
        printf("stack full");
        return;
    }
    
    stack[++top] = item;
    print_stack();
}

int pop()
{
    if (top < 0) {
        printf("stack empty");
        return -999;
    }
    return stack[top--];
}

- 실행 결과

3

3 4

3 4 5

3 4

3

stack empty

4. Queue 큐

- 처리를 기다리고 있는 원소들의 리스트라고 볼 수 있다.

- 스택과 같은 선형 리스트 구조이다.

- 스택과 다른 점은 "선입 선출" 방식이라는 것이다. (FIFO : First-In, First-Out)

- 새로운 원소는 큐의 맨 뒤(rear)에 삽입되고, 큐의 맨 앞(front)원소가 가장 먼저 삭제된다.

- Q = [a₀, a₁, ..., aₙ₋₁] 형식으로 정의할 수 있으며, a₀가 가장 먼저 삽입된 원소이고, aₙ₋₁가 가장 나중에 삽입된 원소이다.

- 큐의 맨 앞과 맨 뒤를 가리키기 위한 두 개의 포인터 (front, rear) 가 필요하다.

- 원소가 삽입될 때에는 rear 포인터가, 삭제될 때에는 front 포인터가 각각 사용된다.

- rear 포인터 값이 큐의 상한 경계와 같으면 full queue로 판단하고, rear와 front 포인터의 값이 같으면 empty queue로 간주한다.

#define QUEUE_SIZE 100
int queue[QUEUE_SIZE];
int rear = -1;
int front = -1;
void print_queue();
void addq(int item);
int deleteq();

void main()
{
    int temp;
    
    addq(3);
    addq(5);
    addq(7);
    temp = deleteq();
    print_queue;
}

void print_queue()
{
    int i;
    
    for (i = front + 1; i <= rearl i ++)
        printf("%d", queue[i]);
    
    printf("\n");
}

void addq(int item)
{
    if(rear == QUEUE_SIZE - 1) {
        printf("Queue Full. item not added");
        return;
    }
    queue[++rear] = item;
    print_queue;
}

int deleteq()
{
    if (front == rear) {
        printf("Queue empty.");
        return -999;
    }
    return queue[++front];
}

- 실행 결과

3

3 5

3 5 7

5 7

4-1. 일반 큐

- 원소의 삽입, 삭제 시 rear와 front 포인터 값이 모두 증가된다.

- 삽입 삭제 빈도가 증가할수록 큐에서 원소들의 저장 위치가 점점 오른쪽으로 이동하게 되고, 왼쪽에 빈공간이 생기게 된다.

- 따라서 원소가 다 차지 않았음에도 queue full 신호가 발생할 수 있다.

- 큐의 빈공간을 재사용하기 위해서는 원소들을 왼쪽으로 이동시키는 작업을 주기적으로 해주어야 한다. 이를 해결한 자료구조가 "순환 큐"이다.

4-2. 순환 큐

- 큐의 오른쪽 끝을 반대편 끝과 연결하여 원소가 이동할 필요 없이 전체 공간을 모두 사용할 수 있다.

- 일반 큐와 마찬가지로 front와 rear 포인터 값이 같을 때를 empty queue로 정의한다.

- front와 rear의 초기값은 각각 0이다. 

- 순환 큐의 모든 공간에 원소가 삽입되면 front와 rear 값이 또 같아지게 된다.

- 이런 상황을 피하기 위해 rear = front - 1인 시점, 즉 원소가 n-1개 삽입된 상태를 full queue로 간주한다.

#include <stdio.h>
#define QUEUE_SIZE 100
int front, rear;
int cqueue[QUEUE_SIZE];
void addcq(int item);
int deletecq;
void print_queue();

void main()
{
    int temp;
    front = rear = 0;
    
    addcq(11);
    addcq(13);
    addcq(17);
    addcq(19);
    
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
}

void addcq(int item)
{
    if (front == ((rear + 1) % QUEUE_SIZE) {
        printf("queue full");
        return;
    }
    rear = (rear + 1) % QUEUE_SIZE;
    cqueue[rear] = item;
    print_queue();
}

int deletecq()
{
    if (front == rear) {
        printf("queue empty");
        return -999;
    }
    front = (front + 1) % QUEUE_SIZE;
    return cqueue[front];
}

void print_queue()
{
    int i = front;
    while (i != rear) {
        i = (i + 1) % QUEUE_SIZE;
        printf("%d", cqueue[i]);
    }
    printf("\n");
}

- 일반 큐와는 달리 순환 큐이기 때문에 if (front == ((rear + 1) % QUEUE_SIZE) 와 같이 "%" 연산자를 사용해야 한다.

- (ex) QUEUE_SIZE = 6이면 인덱스는 0 ~ 5가 존재한다. 이번에 마지막 칸인 인덱스가 5인 칸에 값을 넣었다면 그 다음칸은 6 % 6 인 0이 되어야 한다. 그리고 그것이 front 값과 같기 때문에 full queue가 되었음을 알 수 있다.

5. Deque 

- Double ended queue

- 양방향으로 삽입과 삭제가 모두 가능한 자료구조이다.

6. 수식 평가

- 수식은 연산자와 피연산자로 구성된 문장이다.

- 연산자는 산술 연산자, 논리 연산자, 대입 연산자 등이 있다.

- 피연산자는 변수 또는 상수가 될 수 있다.

- 표기법

    - 중위 표기법

        - a / b - c + d * e - a * c

    - 후위 표기법

        - ab / c - d e * + a c *

    - 전위 표기법

        - - + - / a b c * d e * a c

6.1 후위 수식 계산 알고리즘

    - 수식을 왼쪽에서 오른쪽으로 스캔한다.

    - 수식에서 들어온 입력이 피연산자이면 스택에 넣는다.

    - 입력이 연산자이면 스택에서 피연산자를 2개 꺼내서 계산한 후 결과 값을 다시 스택에 넣는다. 

- 수식 평가 스택

#include <stdio.h>
#include <string.h>
#define STACK_SIZE 100
#define EXPR_SIZE 100

typedef enum
{
    open_b, close_b, plus, minus, times, divide, mod, eos, operand
} priority;        // 열거형 -> 0, 1, 2, ..., 8

int stack[STACK_SIZE];    // 수식 평가 스택
char expr[EXPR_SIZE];     // 수식 문자열
int pos = 0;              // 문자열 현재 위치
char sym;
int sym_type;
int top = -1;

- 후위 수식 평가

int eval_postfix();
void push(int item);
int pop();

void main()
{
    // strcpy(expr, "57 * 9 + 34 / -");        // 5 * 7 + 9 - 3 / 4
    strcpy(expr, "936 + 5 - / 7 * 64 - *");    // 9 / (3 + 6 - 5) * 7 * (6 - 4)
    eval_postfix();
}

int eval_postifx()
{
    char sym;
    int op1, op2;
    sym = read_item();
    while (sym_type != eos) {
        if (sym_type == operand)
            push(sym - '0');
        else {
            op2 = pop();
            op1 = pop();
            switch (sym_type) {
                case plus : push(op1 + op2);
                case minus : push(op1 - op2);
                case times : push(op1 * op2);
                case divide : push(op1 / op2);
                case mod : push(op1 % op2);
            }
        }
        sym = read_item();
    }
    return pop();
}
 
void push (int item) 
{
    if (top >= STACK_SIZE - 1) {
        printf("stack full");
        return;
    } 
    stack[++top] = item;
    print_stack;
}

int pop() 
{
    if (top < 0) {
        printf("empty stack");
        return -999;
    }
    return stack[top--];
}

- 심볼 입력

char read_item()
{
    char sym;
    sym = expr[pos++];
    
    switch (sym)
    { 
        case '(' : sym_type = open_b;
            break;
        case ')' : sym_type = close_b;
            break;
        case '+' : sym_type = plus;
            break;
        case '-' : sym_type = minus;
            break;
        case '*' : sym_type = times;
            break;
        case '/' : sym_type = divide;
            break;
        case '%' : sym_type = mod;
            break;
        case '\0' : sym_type = eos;
            break;
        default : sym_type = operand;    // 피연산자
    }
    
    return sym;
}

- 실행 결과

9 3 6 + 5 - / 7 * 6 4 - *

9

9 3

9 3 6

9 9

9 9 5

9 4

2

2 7

14

14 6

14 6 4

14 2

28

6-2. 중위 수식 → 후위 수식

    - 입력이 피연산자이면 그대로 출력한다.

    - 입력의 우선 순위가 스택 top의 연산자보다 높거나, 스택이 비어있으면 입력을 스택에 넣는다.

    - 스택의 연산자 우선 순위가 입력보다 크거나 같으면 스택 연산자를 pop하고 입력을 스택에 넣는다.

    - 입력이 '(' 이면, ')'이 들어올 때까지 다음 연산자를 위의 규칙을 따라서 스택에 넣는다.

    - 입력이 ')' 이면, '('이 나올 때까지 스택에서 계속 연산자를 pop해서 출력하고 '(' 은 출력하지 않고 버린다.

    - 입력이 문자열의 끝(eos)이면, 스택의 모든 연산자를 꺼내서 출력한다.

- (ex)

a + (b * c + d) * e

#include <stdio.h>
#include <ctype.h>
#define STACK_SIZE 100

char token_stack[STACK_SIZE];
int token_top = -1;
void infix_to_postfix();
int precedence(char op);
void push_token(char sym);
char pop_token();

void main()
{
    infix_to_postfix();
}

void infix_to_postfix()
{
    char expr[50], sym, token;
    int pos = 0;
    
    printf("Enter the expression :: ");
    scanf("%s", expr);
    
    while ((token = expr[pos++]) != '\0') {
        if (isalnum(token))          // 알파벳 또는 숫자
            printf("%c", token);
        else if (token == '(')
            push_token(token);
        else if (token == ')') {
            while ((sym = pop_token()) != '(')
                pirntf("%c", sym);
        }
        else {
            while(precedence(token_stack[token_top]) >= precedence(token) && 
                  token_top != -1) {
                  printf("%c", pop_token());
            }
            push_token(token);
        }
    }
    while (token_top != -1) 
        printf("%c", pop_token());
}

int precedence (char op)
{
    if (op == '(')
        return 0;
    else if (op == '+' || op == '-')
        return 1;
    else if (op == '*' || op == '/' || op == '%')
        return 2;
}

void push_token(char sym)
{
    if (token_top < STACK_SIZE -1)
        token_stack[++token_top] = sym;
    else
        printf("token stack full\n");
}

char pop_token()
{
    if (token_top >= 0)
        return token_stack[token_top--];
        
    printf("token stack empty\n");
    return ' ';
}
            

- 실행 결과

Enter the expression :: a + (b * c + d) * e

a b c * d + e * +

Enter the expression :: 5 * 7 + (4 - 3) / 6 % 9

5 7 * 4 3 - 6 / 9 % +

www.acmicpc.net/problem/10828

문제

코드

#include <stdio.h>
#include <string.h>

int stack[100001];
int count = 0;

void push(int x);
void pop();
void size();
void empty();
void top();

int main() {
    int n, x;
    char order[6];

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%s", &order);

        if (!strcmp(order, "push")) {
            scanf("%d", &x);
            push(x);
        }

        else if (!strcmp(order, "pop")) pop();
        else if (!strcmp(order, "size")) size();
        else if (!strcmp(order, "empty")) empty();
        else if (!strcmp(order, "top")) top();
        else break;
    }
    return 0;
}

void push(int x) {
    stack[count] = x;
    count++;
}

void pop() {
    if (count != 0) {
        count--;
        printf("%d\n", stack[count]);
        stack[count] = 0;
    }
    else printf("%d\n", -1);
}

void size() {
    printf("%d\n", count);
}

void empty() {
    if (count == 0) printf("%d\n", 1);
    else printf("%d\n", 0);
}

void top() {
    if (count > 0) 
        printf("%d\n", stack[count-1]);
    else printf("%d\n", -1);
}