기록보관소

카드 2 문제는 큐를 활용하는 문제이다. 카드 덱의 위쪽은 head, 카드 덱의 아래쪽을 tail로 생각하면 간단하게 해결할 수 있다. 카드를 바닥에 버리는 것은 pop을 하는 것으로, 위쪽의 카드를 아래쪽으로 넣는 것을 pop 후 push로 생각할 수 있다. 이러한 과정을 카드가 1장이 남을 때까지 반복하여 마지막에 큐에 남은 원소를 출력하면 된다. 작성한 코드는 다음과 같다. #include #define size 1000000 //http://ark-hive.tistory.com int N; int queue[size]; int head, tail; int pop() { head += 1; head %= size; return queue[(head+size- 1)%size]; } void push(..

이 문제는 스택을 활용하는 문제이다. 0이 입력으로 들어왔을 때 stack을 pop하는 조건을 가진 문제로 조건에 따라 stack을 채우고, 마지막에 스택에 있는 모든 원소를 더하여 출력함으로써 풀 수 있다. 작성한 코드는 다음과 같다. #include //https://ark-hive.tistory.com/ int k; int temp; int stack[100020]; int top; int sum; void pop() { if (top == 0) { printf("%s\n", "underflow"); } else { top -= 1; } } void push(int num) { top = top + 1; stack[top] = num; } int main(void) { scanf("%d",&k); ..

이 문제는 스택에 대한 개념에 관한 문제이다. 스택 이론에 대해 제대로 숙지하고 있다면 크게 어려운 부분이 없다. 다만 입력을 받는 부분이 약간 까다로울 수 있다. getchar()를 통해 입력버퍼의 문자를 1개씩 개행문자가 등장할 때까지 읽고 실행해야 할 함수를 판단한다. 주의할 점은 입력버퍼의 가장 마지막에 getchar 함수는 EOF를 출력한다는 점이다. N을 scanf로 받는다면 scanf는 개행문자를 입력받지 않으므로 &*c를 통해 개행문자를 제거하거나 잉여 getchar를 통해 개행문자를 삭제해야 정상적으로 동작하게 된다. 작성한 코드는 다음과 같다. #include //https://ark-hive.tistory.com/ char num; int N; char str[100]; int sta..

가장 최근에 삽입된 원소부터 삭제되는 동적 집합 자료 구조(후입선출, LIFO, Last in First out) 원소를 삽입하는 연산은 push, 원소를 추출하는 연산을 pop이라고 한다. 스택의 top은 가장 최근에 삽입된 원소를 가리킨다. top = 0 이면 스택을 비어있다는 것이며 이때 pop을 실행하면 스택 부족(underflow) 오류가 발생한다. 반대로 스택이 가득찬 상태에서 원소를 삽입하면 스택 포화(overflow) 오류가 발생한다. push, pop의 수행시간 모두 O(1)의 수행시간이 걸린다.