Stack(스택)
STACK 이라는 자료구조는 규칙이 다음과 같다.
1.
저장 : 항상 위에만 저장한다.
2.
읽기 : 항상 제일 위에 있는 데이터만 읽을 수 있다.
3.
삭제 : 항상 제일 위에 있는 데이터만 삭제 할 수 있다.
STACK은 위 규칙을 가진 전용 자료구조 이고 배열을 이용해서 구현해도 좋고
또는 LIST 를 이용해서 구현해도 좋다. 구현 방법은 개발자의 자유다.
리스트 기반 스택
#pragma once
#include <iostream>
#include <string>
#include <vector>
struct Node
{
int data;
Node* next;
};
Node* top = nullptr;
Node* bottom = nullptr;
//Stack
void push(int value)
{
Node* buff = new Node();
buff->data = value;
buff->next = top;
top = buff;
}
void pop()
{
Node* backup = top;
top = top->next;
delete backup;
}
int Top()
{
return top->data;
}
int main()
{
push(1);
push(3);
push(2);
push(5);
int topvalue = Top();
pop();
return 0;
}
C++
복사
배열기반 스택
#pragma once
#include <iostream>
#include <string>
#include <vector>
int mArr[256] = {};
int top = -1;
//Stack
void push(int value)
{
mArr[++top] = value;
}
void pop()
{
if (top == -1)
{
}
else
{
top--;
}
}
int Top()
{
if (top == -1)
{
std::cout << "Stack is empty" << std::endl;
return -1;
}
else
{
std::cout << "Top value : " << mArr[top] << std::endl;
return mArr[top];
}
}
int main()
{
push(1);
push(3);
push(2);
push(5);
int top = Top();
pop();
return 0;
}
Python
복사
Queue (큐)
스택과 비슷한 자료구조이며 현업에서 굉장히 많이 사용된다.
여러 함수에서 신호들이 한꺼번에 들어오면, 순차 처리를 위한 대기열 용도로 사용된다.
큐와 스택의 차이
스택은 pop할때, 가장 마지막에 들어온 값을 가장 먼저 제거한다.
큐는 pop할때, 가장 처음에 들어온 값을 가장 먼저 제거한다.
#include <iostream>
#include <string>
#include <string.h>
#include <list>
#include <assert.h>
#include <vector>
#include <stack>
#include <queue>
struct Node
{
int data;
Node* next;
};
Node* head = nullptr;
Node* tail = nullptr;
//Queue
void push(int value)
{
if (head == nullptr)
{
Node* buff = new Node();
buff->data = value;
head = buff;
tail = buff;
}
else
{
tail->next = new Node();
tail = tail->next;
tail->data = value;
}
}
void pop()
{
Node* backup = head;
head = head->next;
delete backup;
}
int top()
{
return head->data;
}
int main()
{
push(1);
push(3);
push(2);
push(5);
int Top = top();
pop();
return 0;
}
C++
복사
문제 1번
아래 소스코드는 힙에 노드를 4개 생성한 코드입니다.
3을 입력하면 3의 배수로 4개 노드를 생성해 주세요.
이제 while문을 이용해서 만들어진 모든 노드를 출력 해 주세요.
[힌트]
cin >> input;
for (int i = 1; i<=4; i++) {
addNode(i * input);
}
입력 예제
3
출력 결과
3 6 9 12
문제 2번
숫자 하나를 입력으세요 (11 ~ 36 까지 숫자)
입력받은 번호에 해당하는 문자 부터 노드 4개만 연결시켜주세요.
11 : A
12 : B
13 : C
14 : D
...
36 : Z
만약 11을 입력받았다면, 아래와 같이 구성하면 됩니다.
그리고 for문을 돌려 모든 노드를 출력 해 주세요.
입력 예제
11
출력 결과
ABCD
문제 3번
네 종류의 카드가 있습니다. (A,B,C,D)
몇 장을 뽑을지 입력받아주세요
n장을 뽑으려고 하는데 중복 없이 뽑는 경우를 출력 해주세요.
만약 2를 입력했다면
AB
AC
AD
BA
BC
...
DC
만약 3을 입력했다면
ABC
ABD
ACB
...
DCB
가지치기 힌트
via 전역배열을 이용해서 중복 판단 가능
입력 예제
2
출력 결과
AB
AC
AD
BA
BC
BD
CA
CB
CD
DA
DB
DC
문제 4번
숫자 n을 입력 받고, n개만큼 노드를 만들고 연결 해주세요.
들어가는 값은 순차적으로 A, B, C, D... / 1, 2, 3, 4... 입니다.
노드를 구성한 후
대문자는 for문으로 출력하고
숫자들은 while로 모두 출력 해 주세요.
ex1)
입력: 4
출력: A B C D
1 2 3 4
ex2)
입력: 3
출력: A B C
1 2 3
입력 예제
4
출력 결과
A B C D
1 2 3 4
문제 5번
링크드리스트로 Queue를 만들어주세요.
입력의 첫번째 숫자는 Queue에 넣을 문자 갯수(Enqueue)
두번째 숫자는 Dequeue 할 갯수 입니다.
그 다음 문자들은 Queue에 넣을 문자들 입니다.
입력 예제
3 1
A B C
출력 결과
B C
문제 6번
숫자와 문자가 섞인 문장을 입력 받습니다.
이때 문장 속에서 숫자는 하나만 존재합니다.(최대 15글자)
ex1) ATP1326TTA
ex2) PPPT756
이런 숫자와 문자가 섞인 한문장에서 숫자만 파싱하여 5를 더한 숫자를 출력하세요.
아래 예제를 참고하세요.
[Tip]
parsing(파싱) : 문장에서 내가 원하는 값을 뽑아내는 처리를 뜻합니다.
입력 예제
1999POW
출력 결과
2004
문제 7번
한 노드가 다음과 같은 구조체로 된 큐를 배열로 구현해 주세요.
Node queue[10];
이제 입력 개수에 따라 입력이 주어 집니다.
이렇게 입력을 받았다면 큐에 아래와 같이 채워집니다.
모두 채운 후, 모든 값을 pop 해주세요.
이제 pop을 할때마다 나오는 값을 출력 해주세요.
입력 예제
4
1 A
2 B
3 C
4 D
출력 결과
1 A
2 B
3 C
4 D
문제 8번
10칸짜리 큐를 만들어주세요.
숫자 하나를 입력받고, Enqueue 3회 / Dequeue 3회 반복하는 소스코드를 작성 해 주세요.
Dequeue할때마다 숫자를 출력하면 됩니다.
만약 n이 5라면 아래와 같은 main 함수가 동작되도록 구현 하시면 됩니다.
입력 예제
5
출력 결과
123123123123123
문제 9번
다음 2차배열을 하드코딩 해주세요.
문자로 된 숫자1개 또는 문자 1개를 입력 받으세요.
해당되는 한줄을 출력 하면 됩니다.
ex)
1을 입력 받으면 2211 출력
0을 입력 받으면 3514 출력
A를 입력 받으면 3203 출력
입력 예제
1
출력 결과
2211
문제 10번
꺽쇠 < 와 >, 숫자로 이루어진 한 문장을 입력 받으세요.
꺽쇠가 열리면 ('<') 이후에 꺽쇠가 닫혀야 합니다.('>')
정상적으로 꺽쇠가 열리고 닫혔는지 판단하는 프로그램을 작성하세요.
정상이면 "정상", 비정상이면 "비정상" 출력. (최대 20글자)
1.
ex) <35<6<912>>10> => 정상
2.
ex) 56<7>>65 => 비정상
3.
ex) >>15<< => 비정상
4.
ex) 612<>7<>91 => 정상
입력 예제
<35<6<912>>10>
출력 결과
정상
문제 11번
Text 한문장을 입력 받으세요.
그리고 커서 위치를 입력 받으세요.
예를 들어 ABCDEF와 커서위치 2를 입력 받았다면
CMD는 세가지 입니다.
L: Left Cursor
R: Right Cursor
D: Delete Cursor
이제 CMD 4개를 입력받고 CMD에 따라 처리를 해주세요.
만약 RRLD를 입력 받았다면
오른쪽 2칸, 왼쪽 1칸 커서를 이동시키고, Delete를 한번 수행하면 되므로
와 같은 상태가 됩니다.
커서 위치는 3번 index 글자 앞에 있습니다.
명령어를 수행하고 커서가 있는 위치를 출력 해주세요.
입력 예제
ABCDEF
2
RRLD
출력 결과
3
문제 12번
큐를 이용해서 풀어보세요.
척척박사님은 B, I, A, H 슈퍼영웅들 중 출동할 사람을 순서대로 뽑아야 합니다.
척척박사님은 항상 영웅B를 시작으로 다섯번째 사람을 선택합니다.
반복적으로 다섯번째 사람을 선택했을 때, 출동하는 영웅들의 순서를 출력 하세요.
출동순서 결과: B A H I
출력 결과
B A H I
문제 13번
A, B, C 배열에 있는 정예멤버를 선정하여 후보배열에 넣으려 합니다.(A, B, C 배열은 하드코딩)
•
A배열에서 MAX 3명 선출.(가장 큰수 3개)
•
B배열에서 MIN 3명 선출.(가장 작은수 3개)
•
C배열에서 MIN 2명, MAX 1명 선출.(가장 작은수 2개, 가장 큰 수 1개)
출력 결과
7 6 4
1 1 2
1 2 9
