📍 16. 스택, 큐, 덱
📘 스택 구현
- 선언 : Stack<Element> stack = new Stack<>();
- Element : 데이터 타입 지정
push(): 스택 추가pop(): 스택 최근 값 제거peek(): 스택 최근 값 출력 (최상위 요소)isEmpty(): 스택 비어있는지 확인 (↔️ isFull)search(): 스택 값 인덱스 출력
- 구현
class Stack { int arr[]; int top; int capacity; // 초기화 Stack (int size) { arr = new int[size]; capacity = size; top = -1; } // push public void push(int x) { if (isFull()) { //overflow System.exit(-1); } arr[++top] = x; } // pop public int pop() { if (isEmpty()) { //underflow System.exit(-1); } return arr[top--]; } // peek public int peek() { if (!isEmpty()) return arr[top]; else System.exit(-1); return -1; } // size public int size() { return top + 1; } // isEmpty public boolean isEmpty() { return top == -1; } // isFull public boolean isFull() { return top == capacity - 1; } }
📕 스택 2
문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
3: 스택에 들어있는 정수의 개수를 출력한다.
4: 스택이 비어있으면 1, 아니면 0을 출력한다.
5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.코드
import java.io.*;
import java.util.*;
public class baek16_1 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<Integer>();
int N = Integer.parseInt(br.readLine());
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
if (cmd.equals("1"))
stack.push(Integer.parseInt(st.nextToken()));
else if (cmd.equals("2"))
{
if (!stack.isEmpty())
{
sb.append(stack.lastElement()).append("\n");
stack.pop();
}
else
sb.append(-1).append("\n");
}
else if (cmd.equals("3"))
sb.append(stack.size()).append("\n");
else if (cmd.equals("4"))
{
if (!stack.isEmpty())
sb.append(0).append("\n");
else
sb.append(1).append("\n");
}
else if (cmd.equals("5"))
{
if (!stack.isEmpty())
sb.append(stack.lastElement()).append("\n");
else
sb.append(-1).append("\n");
}
}
System.out.println(sb);
}
}📕 제로
문제
재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.
재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.
재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!코드
import java.util.*;
import java.io.*;
public class baek16_2 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<Integer>();
int K = Integer.parseInt(br.readLine());
int result = 0;
for (int i = 0; i < K; i++) {
int n = Integer.parseInt(br.readLine());
if (n == 0)
{
if (!stack.isEmpty())
stack.pop();
}
else
stack.push(n);
}
while (!stack.isEmpty())
{
result += stack.peek();
stack.pop();
}
sb.append(result).append("\n");
System.out.println(sb);
}
}📕 괄호
문제
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 코드
import java.util.*;
import java.io.*;
public class baek16_3 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++)
{
sb.append(isPS(br.readLine())).append("\n");
}
System.out.println(sb);
}
public static String isPS(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(')
stack.push(c);
else if (c == ')') {
if (stack.empty())
return ("NO");
else
stack.pop();
}
}
if (stack.empty())
return ("YES");
else
return ("NO");
}
}📕 균형잡힌 세상
문제
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.코드
import java.util.*;
import java.io.*;
public class baek16_4 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String s;
while(true) {
s = br.readLine();
if (s.equals("."))
break;
sb.append(isPS(s)).append('\n');
}
System.out.println(sb);
}
public static String isPS(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[')
stack.push(c);
else if (c == ')')
{
if (stack.isEmpty() || stack.peek() != '(')
return "no";
else
stack.pop();
}
else if (c == ']')
{
if (stack.isEmpty() || stack.peek() != '[')
return "no";
else
stack.pop();
}
}
if (stack.isEmpty())
return "yes";
else
return "no";
}
}📕 도키도키 간식드리미
문제
이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다.
그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.
사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.
현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.
코드
import java.util.*;
import java.io.*;
public class baek16_5 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Queue<Integer> queue = new LinkedList<>();
Stack<Integer> stack = new Stack<>();
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
queue.offer(Integer.parseInt(st.nextToken()));
}
int start = 1;
while (!queue.isEmpty())
{
if (queue.peek() == start)
{
queue.poll();
start++;
}
else if (!stack.isEmpty() && stack.peek() == start)
{
stack.pop();
start++;
}
else
stack.push(queue.poll());
}
while (!stack.isEmpty())
{
if (stack.peek() == start)
{
stack.pop();
start++;
}
else
{
System.out.println("Sad");
return;
}
}
System.out.println("Nice");
}
}📘 큐 구현
- 선언 : Queue<Element> queue = new LinkedList<>();
- Element : 데이터 타입 지정
offer(): 큐 추가poll(): 큐 첫번째 값 반환 (비어있으면 null)peek(): 큐 첫번째 값 출력isEmpty(): 큐 비어있는지 확인remove(): 큐 첫번째 값 제거clear(): 큐 초기화
📕 큐 2
문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.코드
📕
문제
코드
📕
문제
코드
📕
문제
코드
📕
문제
코드
📕
문제
코드
📍 19. 조합론
📕 베라의 패션
문제
베라는 상의 N 벌과 하의 N 벌이 있다. i 번째 상의와 i 번째 하의는 모두 색상 i를 가진다. N 개의 색상은 모두 서로 다르다.
상의와 하의가 서로 다른 색상인 조합은 총 몇 가지일까?코드
import java.util.*;
public class baek17_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
System.out.println(N * (N - 1));
in.close();
}
}📕 녹색거탑
문제
녹색거탑은 위 그림과 같이 규칙적으로 쌓여있다.
그림의 시야에 보이지 않는 블록은 없다.
그림의 시야에 보이는 블록의 윗면만 이용해 녹색거탑을 내려올 수 있다.
녹색거탑이
$N$층이면, 총
$N$개의 블록을 이용한 최단 경로로만 내려온다.
녹색거탑을 내려올 때는 정상에서 시작해 노란색 바닥까지, 항상 인접한 아래층의 블록으로만 내려온다.코드
import java.util.*;
public class baek17_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int result = 1;
for (int i = 1; i <= N; i++) {
result *= 2;
}
System.out.println(result);
in.close();
}
}📕 팩토리얼
문제
0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek17_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int result = 1;
for (int i = N; i >= 2; i--) {
result *= i;
}
System.out.println(result);
in.close();
}
}📕 이항 계수 1
문제
자연수
\(N\)과 정수
\(K\)가 주어졌을 때 이항 계수
\(\binom{N}{K}\)를 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek17_4 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int K = in.nextInt();
System.out.println(factorial(N) / (factorial(K) * factorial(N - K)));
in.close();
}
public static int factorial(int n) {
int result = 1;
for (int i = n; i >= 2; i--) {
result *= i;
}
return (result);
}
}📕 다리 놓기
문제
이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)
재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.
코드
// 다리 놓기
import java.util.*;
public class baek17_5 {
static int[][] dp = new int[30][30];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int T = in.nextInt();
for (int i = 0; i < T; i++) {
int N = in.nextInt();
int M = in.nextInt();
sb.append(combi(M, N)).append('\n');
}
System.out.println(sb);
in.close();
}
public static int combi(int n, int r) {
if (dp[n][r] > 0) {
return (dp[n][r]);
}
if (n == r || r == 0) {
return(dp[n][r] = 1);
}
return (dp[n][r] = combi(n - 1, r - 1) + combi(n - 1, r));
}
}📍 심화2
📕
문제
코드
📕
문제
코드
📕
문제
코드
📕 통계학
문제
수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.
- 산술평균 : N개의 수들의 합을 N으로 나눈 값
- 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
- 최빈값 : N개의 수들 중 가장 많이 나타나는 값
- 범위 : N개의 수들 중 최댓값과 최솟값의 차이
N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.코드
📕
문제
코드
📍
📕
문제
코드
Notion으로 이동 (https://24tngus.notion.site/3a6883f0f47041fe8045ef330a147da3?v=973a0b5ec78a4462bac8010e3b4cd5c0&pvs=4)