본문 바로가기
Computer Science/자료구조

[자료구조] ep5+++) 시간복잡도를 고려한 스택 설계

by 클레어몬트 2024. 6. 8.

프로그램 요구사항

1)  스택을 배열 또는 연결리스트 가운데 어느 것으로 구현해도 좋다.

2)  주함수(즉, main 함수)는 아래에 보인 사용자의 명령 코드를 입력받을 때마다 해당 부함수를 호출하여 명령을 수행한다.

p e : 스택에 원소 e를 삽입 (push)

P : 스택에 100만개 원소를 삽입 (pushMillion)

o : 스택으로부터 원소를 삭제 (pop)

O : 스택으로부터 100100만 개 원소를 삭제 (popMillion) f : 스택 원소 중 최솟값 출력 (findMin)

q : 수행 종료 (quit)

3)  p, o, f 명령이 입력되면 별도로 작성된 push, pop, findMin 부함수를 각각 호출하여 수행한다.

4)  P 명령이 입력되면 주함수는 부함수 pushMillion을 호출한다. pushMillion 함수는 난수발생함수를 100만번 호출하여 1000 ~ 9999 사이의 난수 정수 100100만 개를 차례로 스택에 삽입한 후 반환한다. 이때 스택 원소 삽입은 반드시 위 3항에서 호출한 push 함수를 100100만 번 호출하여 처리해야 한다.

5)  O 명령이 입력되면 주함수는 부함수 popMillion을 호출한다. popMillion 함수는 100100만 번의 스택삭제를 수행한 후 반환한다. 이때 스택 원소 삭제는 반드시 위 3항에서 호출한 pop 함수를 100100만 번 호출하여 처리해야 한다.

6)  q 명령이 입력되면 주함수가 종료된다 - 현재 스택을 깨끗이 비우고 종료하는 것을 추천!

7)  주함수는 q를 제외한 모든 명령코드에 대한 해당 부함수의 수행시간을 측정하여 출력해야 한다.

 

test case

 

※ 참고:

  1. 위 실행 예에서 보인 출력형식을 준수해야 한다.
  2. 실행 예에서 괄호 속의 수는 해당 명령 수행 직후의 스택 사이즈를 나타낸다.
  3. cputime X.XXXXXXXX는 측정된 cputime in milliseconds이다. 이 실행시간은 각 부함수에 대한 호출과 반환 사이에 소요된 cputime을 표시해야 한다. 이 경우, 상수 시간을 나타내는 cputime은 거의 0초 혹은 아예 0초로 표시되더라도 무방하다.
  4. 위 실행 예 수행에서, 자신의 PC 성능 문제(너무 느림)로 인해 불가피하다면 100만 대신 10만을 사용해서 작성해도 좋다.
  5. 위 실행 예는 예시일 뿐, 다른 실행예를 스스로 만들어 추가로 수행해보는 것을 추천한다.

주의

1)  pushMillion, popMillion 함수는 선형시간에 수행하지만(위 실행예 일련번호 2번과 11번 작업),

push, pop, findMin 세 개의 함수 모두 상수시간에 작동해야 만점을 받을 수 있다(위 2번과 11번을 제외한 모든 작업들) - 만약 p, o, f 명령 수행에 소요된 cputime이 상수시간(즉, 0초 혹은 거의 0초)이라고 볼 수 없는 큰 수로 나타난다면 해당 함수가 상수시간이 아닌, 선형시간에 작동한다는 의미다. 이 경우 해당 함수를 상수시간에 작동하도록 수정해야 할 것이다.

2)  명령 에코, 괄호 속의 현재 스택 사이즈, cputime 등에 대한 계산 및 출력은 모두 (각 부함수가 아닌) 주함수에서 수행해야 한다.

3)  연결스택 구현에서는 스택 사이즈를 유지하는 전역변수(예를 들어 n)를 사용해도 좋다. 참고로 순차스택 구현에서는 top 값을 이용해서 스택 사이즈를 구할 수 있으므로 이런 전역변수가 불필요하다.

4)  메모리 사용이 과다할 경우 효율적인 프로그램이 아니므로, 불필요한 메모리 사용을 줄이도록 설계하라. 참고로, 할당 크기 100만 정도의 정수 원소 스택 1개를 사용하는 것까지는 필수적이겠으나 만약 이 정도 크기의 메모리를 추가로 사용(즉, 결과적으로 필수 스택 크기의 약 2 배수의 총메모리를 사용)하여 이 문제를 풀어낸다면 메모리 과다 사용으로 판정된다. 따라서 이보다는 현저히 적은 추가 메모리를 사용해서 풀어낼 방안을 생각해내야 한다.

5)  데이터구조 및 알고리즘 면에서 간결하게 해결할 수 있는 것을 불필요하게 복잡하게 해결하면 (입출력이 정확하더라도) 안된다.

6) 프로그램 작성 시에 모듈화를 고려하여 설계할 것. 모듈화란 각 부함수가 논리적, 기능적인 면에서 역할이 분명하며 독립적임을 의미한다.

 

 

n배열과 min값을 담는 리스트

 

 

 

(전체코드) - Windows에서만 실행 가능

// 시간복잡도를 고려한 스택설계
// 스택내의 최솟값을 담을 연결리스트 이용
// 최솟값이 나올 때마다 노드를 생성하고 최솟값이 pop될 때마다 노드를 삭제

// (함수 요구조건) 
// push, pop, findMin 함수: 상수시간(0초 혹은 거의 0초)
// pushMillion, popMillion 함수: 선형시간

// cputime은 ms단위
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#pragma warning (disable:4996)

#define MAX_SIZE 1000100

typedef struct STACK {
    int n[MAX_SIZE];
    int top;
} STACK;

typedef struct NODE { // 최솟값을 담을 노드
    int min;
    struct NODE* next;
} NODE;

NODE* g_pHeader = NULL; // 리스트의 헤더 노드를 고정으로 가리키는 전역 노드 포인터

void push(STACK* stack, int e);
void pushMillion(STACK* stack);
int pop(STACK* stack);
void popMillion(STACK* stack);
int findMin();
void quit(STACK* stack);

NODE* moveToLastNode();
NODE* moveToLastBeforeNode();
void addLastNode(int e);
void deleteLastNode();

int main() {
    char cmd;
    int e;
    int min;
    LARGE_INTEGER ticksPerSec;
    LARGE_INTEGER start, end, diff;
    srand(time(NULL));
    STACK* stack = (STACK*)malloc(1 * sizeof(STACK));
    stack->top = -1;
    NODE* g_pHeader = (NODE*)malloc(1 * sizeof(NODE));
    g_pHeader->next = NULL;

    while (1) {
        scanf("%c", &cmd);
        if (cmd == 'p') { // push
            scanf(" %d", &e);

            QueryPerformanceFrequency(&ticksPerSec);
            QueryPerformanceCounter(&start);
            push(stack, e);
            QueryPerformanceCounter(&end);

            diff.QuadPart = end.QuadPart - start.QuadPart;
            printf("push %d (%d), cputime = %.10f\n", e, stack->top + 1, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
        }
        else if (cmd == 'P') { // pushMillion
            QueryPerformanceFrequency(&ticksPerSec);
            QueryPerformanceCounter(&start);
            pushMillion(stack);
            QueryPerformanceCounter(&end);

            diff.QuadPart = end.QuadPart - start.QuadPart;
            printf("pushMillion (%d), cputime = %.10f\n", stack->top + 1, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
        }
        else if (cmd == 'o') { // pop
            QueryPerformanceFrequency(&ticksPerSec);
            QueryPerformanceCounter(&start);
            e = pop(stack);
            QueryPerformanceCounter(&end);

            diff.QuadPart = end.QuadPart - start.QuadPart;
            printf("pop %d (%d), cputime = %.10f\n", e, stack->top + 1, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
        }
        else if (cmd == 'O') { // popMillion
            QueryPerformanceFrequency(&ticksPerSec);
            QueryPerformanceCounter(&start);
            popMillion(stack);
            QueryPerformanceCounter(&end);

            diff.QuadPart = end.QuadPart - start.QuadPart;
            printf("popMillion (%d), cputime = %.10f\n", stack->top + 1, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
        }
        else if (cmd == 'f') { // findMin
            QueryPerformanceFrequency(&ticksPerSec);
            QueryPerformanceCounter(&start);
            min = findMin();
            QueryPerformanceCounter(&end);

            diff.QuadPart = end.QuadPart - start.QuadPart;
            printf("min %d (%d), cputime = %.10f\n", min, stack->top + 1, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
        }
        else if (cmd == 'q') { // quit
            quit(stack);
            printf("(프로그램 종료)\n");
            return 0;
        }
    }
}

void push(STACK* stack, int e) {
    if (stack->top == -1) {
        addLastNode(e);
        stack->n[++(stack->top)] = e;
        return;
    }

    NODE* lastNode = moveToLastNode();
    if (lastNode->min >= e) { // 최솟값 갱신
        addLastNode(e);
    }

    stack->n[++(stack->top)] = e;
}

void pushMillion(STACK* stack) {
    for (int i = 0; i < 1000000; i++) {
        push(stack, rand() % 9000 + 1000);
    }
}

int pop(STACK* stack) {
    if (stack->n[stack->top] == findMin()) { // 최솟값이 pop될 경우
        deleteLastNode();
    }

    return stack->n[(stack->top)--];
}

void popMillion(STACK* stack) {
    for (int i = 0; i < 1000000; i++) {
        pop(stack);
    }
}

int findMin() {
    NODE* lastNode = moveToLastNode();
    return lastNode->min;
}

void quit(STACK* stack) {
    free(stack);

    while (g_pHeader != NULL) {
        NODE* temp = g_pHeader;
        g_pHeader = g_pHeader->next;
        free(temp);
    }

    g_pHeader = NULL;
}

NODE* moveToLastNode() {
    NODE* temp = g_pHeader;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    return temp;
}

NODE* moveToLastBeforeNode() {
    if (g_pHeader == NULL || g_pHeader->next == NULL) {
        return g_pHeader;
    }

    NODE* temp = g_pHeader;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    return temp;
}

void addLastNode(int e) {
    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
    newNode->min = e;
    newNode->next = NULL;

    if (g_pHeader == NULL) {
        g_pHeader = newNode;
        return;
    }
    else {
        NODE* lastNode = moveToLastNode();
        lastNode->next = newNode;
    }
}

void deleteLastNode() {
    if (g_pHeader == NULL) {
        return;
    }
    else if (g_pHeader->next == NULL) {
        free(g_pHeader);
        g_pHeader = NULL;
        return;
    }

    NODE* lastBeforeNode = moveToLastBeforeNode();
    free(moveToLastNode());
    lastBeforeNode->next = NULL;
}

/*
p 119
P
f
p 33
p 119
f
p 33
o
f
o
O
f
q
*/

 

 

 

 

 

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님)

저작자표시 비영리 변경금지

'Computer Science > 자료구조' 카테고리의 다른 글

[자료구조] ep6-2) 원형 큐(Circular Queue)  (0) 2024.06.08
[자료구조] ep6-1) 큐(Queue)  (0) 2024.06.08
[자료구조] ep5++) 수식표기법(스택을 이용한 후위수식)  (0) 2024.06.08
[자료구조] ep5+) 심볼 균형(스택을 이용한 괄호 쌍의 대칭성 검사)  (0) 2024.06.08
[자료구조] ep5) 스택(Stack)  (0) 2024.06.07

관련글

티스토리툴바