2. 스택(Stack)

Posted on 2020-03-19 Edited on 2020-03-20 In Computer , Algorithm Disqus:
Symbols count in article: 6.5k Reading time ≈ 6 mins.

스택(Stack)

먼저 들어간 데이터가 가장 마지막에 나오는 구조(Last In, First Out : LIFO)
삽입과 삭제가 한쪽 끝에서만 자료를 넣고 뺄 수 있다.
ex) 자동메모리, 네트워크 프로토콜

스택(Stack)의 주요 기능

스택의 초기화

1 2	int stack[100]; //스택 배열 int size = 0; // 스태의 크기

삽입(Push)

스택 위에 새로운 노드를 쌓는 작업

void push(int data) {
	stack[size] = data;
	size = size + 1;
}

데이터 80 삽입

삭제(Pop)

스택에서 최상위 노드를 걷어내는 작업

int pop() {
	if (size < 0)
		return 0;		
	int pop = stack[size];
	size = size - 1;
	return pop;
}

데이터 80 제거

Peek

Top이 가리키는 위치의 데이터를 가져오는 작업

1
2
3

int peek() {
	return stack[size];
}

empty

스택이 비어있는지 비어있지 않은지 알아보는 작업

1
2
3

boolean isEmpty() {
	return (size == 0) ? true : false;
}

size

스택에 저장되어 있는 자료의 개수를 알아보는 작업

1
2
3

int size() {
	return size;
}

배열로 구현하는 스택

동적으로 스택의 용량을 조절하기가 어렵다는 단점이 있다.
구현이 간단하다.

Java version

ArrayStack.java

public class ArrayStack<T> implements Stack<T> {
	private static int DEFAULT_SIZE = 10;
	private static int top;
	private static int capacity;
	private Object[] stack;

	public ArrayStack() {
		top = -1;
		capacity = DEFAULT_SIZE;
		stack = new Object[capacity];
	}
	public ArrayStack(int capacity) {
		top = -1;
		capacity = DEFAULT_SIZE;
		stack = new Object[capacity];
	}
	@Override
	public void push(T data) {
		if (isFull()) {
			throw new IndexOutOfBoundsException("stack overflow");
		}
		stack[++top] = data;
	}
	@Override
	public T pop() {
		if (isEmpty()) {
			throw new IndexOutOfBoundsException("data impty");
		}
		return (T)stack[top--];
	}
	@Override
	public T peek() {
		return (T)stack[top];
	}
	@Override
	public boolean isFull() {
		if (top == capacity-1) {
			return true;
		}
		return false;
	}
	@Override
	public boolean isEmpty() {
		if (top == -1) {
			return true;
		}
		return false;
	}

}

Stack.java

public interface Stack<T> {
	public void push(T data);
	public T pop();
	public T peek();
	public boolean isFull();
	public boolean isEmpty();
}

c language

ArrayList.h

//
// Created by Paik Seung Cheol on 2020. 3. 19..
//

#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H


#include <stdio.h>
#include <stdlib.h>


#define TRUE 1
#define FALSE 0

typedef struct _Node {
    int data;
}Node;

typedef struct _Stack {
    int top;
    int capacity;
    Node* nodes;
}Stack;

void createStack(Stack** stack, int capacity);
int isFull(Stack* stack);
int isEmpty(Stack* stack);
void push(Stack* stack, int data);
int popup(Stack* stack);
int peek(Stack* stack);
#endif //ARRAYSTACK_H

ArrayList.c

//
// Created by Paik Seung Cheol on 2020. 3. 19..
//
#include "ArrayStack.h"

void createStack(Stack** stack, int capacity) {
    (*stack) = (Stack*)malloc(sizeof(Stack));
    (*stack)->capacity = capacity;
    (*stack)->top = -1;
    (*stack)->nodes = (Node*) malloc(sizeof(Node)* capacity);
}

int isFull(Stack* stack) {
    if ((stack)->top == (stack)->capacity-1) {
        return TRUE;
    }
    return FALSE;
}
int isEmpty(Stack* stack) {
    if ((stack)->top == -1) {
        return TRUE;
    }
    return FALSE;
}
void push(Stack* stack, int data) {
    if (isFull(stack)) {
        printf("stack overflow\n");
        exit(1);
    }
    stack->nodes[++stack->top].data = data;
}
int popup(Stack* stack) {
    if (isEmpty(stack)) {
        printf("is empty\n");
        exit(1);
    }
    return stack->nodes[stack->top--].data;
}

int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("is empty\n");
        exit(1);
    }
    return stack->nodes[stack->top].data;
}

연결리스트로 구현하는 스택

스택의 용량에 제한을 두지 않는다.

//
// Created by Paik Seung Cheol on 2020. 3. 19..
//
public class LinkedListStack<T> implements Stack<T> {

	private Node stack;
	private Node top;
	private static int length;

	public class Node {
		private T data;
		private Node top;

		public Node() {
			this.data = null;
			this.top = null;
		}

		public Node(T data) {
			this.data = data;
			this.top = null;
		}
	}

	public LinkedListStack() {
		stack = new Node();
		top = new Node();
		length = 0;
	}

	@Override
	public void push(T data) {
		Node newNode = new Node(data);
		if (stack.top == null) {
			stack.top = newNode;
		} else {
			Node oldStack = stack;
			do {
				oldStack = oldStack.top;
			} while (oldStack.top != null);
			oldStack.top = newNode;
		}
		top = newNode;
		length++;
	}

	@Override
	public T pop() {
		if (isEmpty()) {
			throw new IndexOutOfBoundsException("Stack is Empty ");
		}
		Node remove = top;
		if (stack.top == top) {
			stack.top = null;
			top = null;
		} else {
			Node curTop = stack;
			do {
				curTop = curTop.top;
			} while (curTop.top != top);
			curTop.top = null;
			top = curTop;

		}
		length--;
		return remove.data;
	}

	@Override
	public T peek() {
		if (isEmpty()) {
			throw new IndexOutOfBoundsException("stack is empty");
		}
		return top.data;
	}

	@Override
	public boolean isFull() {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean isEmpty() {
		if (length == 0 && stack.top == null) {
			return true;
		}
		return false;
	}

	@Override
	public String toString() {
		Node temp = stack.top;
		if (temp == null) {
			return "[ ]";
		} else {
			// StringBuilder 클래스를 이용하여 데이터를 출력
			StringBuilder sb = new StringBuilder("[");
			sb.append(temp.data);
			temp = temp.top;
			while (temp != null) {
				sb.append(", ");
				sb.append(temp.data);
				temp = temp.top;
			}
			sb.append("]");
			return sb.toString();
		}
	}
}

Ex) 후위표기 사칙연산 계산

//
// Created by Paik Seung Cheol on 2020. 3. 19..
//
public class Calculator {
	public static void main(String[] args) {
		double result = postFixCalc("132**");
		System.out.println(result);
	}

	public static double postFixCalc(String data) {
		Stack<Double> stack = new ArrayStack<>();

		for (int i = 0; i < data.length(); i++) {
			switch (data.charAt(i)) {
			case '*':
			case '-':
			case '+':
			case '/':
				double op1 = new BigDecimal(stack.pop()).doubleValue();
				double op2 = new BigDecimal(stack.pop()).doubleValue();
				double result = calculate(data.charAt(i), op1, op2);
				stack.push(result);
				break;
			default:
				int num = Character.digit(data.charAt(i),10);
				stack.push(new BigDecimal(num).doubleValue());
			}
		}
		double result = 0;
		while(!stack.isEmpty()) {
			result = stack.pop();
		}
		return result;
	}

	private static double calculate(char postfixExp, double op1, double op2) {
		double result =0;

		switch (postfixExp) {
		case '*':
			result = new BigDecimal(op1).multiply(new BigDecimal(op2)).doubleValue();
			break;
		case '-':
			result = new BigDecimal(op1).subtract(new BigDecimal(op2)).doubleValue();
			break;
		case '+':
			result = new BigDecimal(op1).add(new BigDecimal(op2)).doubleValue();
			break;
		case '/':
			result = new BigDecimal(op1).divide(new BigDecimal(op2)).doubleValue();
			break;
			default :
				break;
		}
		return result;
	}
}

소스코드

github 이동 (Click)

[BaekJoon-9012]-괄호(Parentheses)

Posted on 2020-03-18 Edited on 2020-03-19 In Computer , CodingTest Disqus:
Symbols count in article: 1.9k Reading time ≈ 2 mins.

[BaekJoon-9012] 괄호

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

예제 입력 1

6  
(())())  
(((()())()  
(()())((()))  
((()()(()))(((())))()  
()()()()(()()())()  
(()((())()(

예제 출력 1

NO
NO
YES
NO
YES
NO

예제 입력 2

3  
(  
)  
())(()

예제 출력 2

1
2
3

NO  
NO  
NO

풀이

스택을 이용하여 문제를 풀수 있으며, ‘(‘를 만나면 stack에 push를 하고 ‘)’일 경우 pop을 하여 처리하였다. 만약 ‘)’일 경우 stack에 ‘(‘가 없다면 NO를 출력하고, 문자열을 다 검색 후 스택에 ‘(‘가 남아 있다면 NO를 처리했다.

코드


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws Exception {
        parenthesis();
    }

    public static void parenthesis() throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));


        int t = parseInt(in.readLine());
        while (0 < t--) {
            Stack<Character> stack = new Stack<>();
            String ps = in.readLine();
            String result = "YES";
            for (int i = 0; i <ps.length(); i++) {
                char ch = ps.charAt(i);
                if (ch == '(') {
                    stack.push(ch);
                    continue;
                }
                if (stack.empty()) {
                    result = "NO";
                    break;
                }
                stack.pop();
            }
            if (result.equals("YES") && !stack.empty()) {
                result = "NO";
            }
            out.write(result);
            out.write('\n');
            out.flush();;
        }
        out.close();
        in.close();
    }

    public static int parseInt(String arg) {
        return Integer.parseInt(arg);
    }
}

문제 사이트 : https://www.acmicpc.net/problem/9012

[BaekJoon-9093] 단어 뒤집기

Posted on 2020-03-18 Edited on 2020-03-26 In Computer , CodingTest Disqus:
Symbols count in article: 1.4k Reading time ≈ 1 mins.

[BaekJoon-9093] 단어 뒤집기

문제

문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 공백이 하나 있다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 문장의 단어를 모두 뒤집어 출력한다.

예제 입력 1

2
I am happy today
We want to win the first prize

예제 출력 1

I ma yppah yadot
eW tnaw ot niw eht tsrif ezirp

풀이

스택을 이용하면 N개의 문자를 스택에 넣었다 빼면 역순으로 출력할 수 있다.

스택에 알파벳을 넣는다.
공백이나 문자열의 끝이면 스택에서 모두 빼낸다.
역순으로 만들도록 출력

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws Exception {
        flipWord();
    }

    public static void flipWord() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = parseInt(in.readLine());

        while (0 < t--) {
            Stack<Character> stack = new Stack<>();
            String word = in.readLine() + "\n";
            for (int i  = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if (ch != ' ' && ch != '\n') {
                    stack.push(ch);
                    continue;
                }
                while(!stack.isEmpty()) {
                    out.write(stack.pop());
                }
                out.write(ch);
            }
            out.flush();
        }
        out.close();;
        in.close();;
    }
    

    public static int parseInt(String arg) {
        return Integer.parseInt(arg);
    }
}

문제 사이트 : https://www.acmicpc.net/problem/9093

[BackJoon-10828] 스택

Posted on 2020-03-18 Edited on 2020-03-19 In Computer , CodingTest Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

[BackJoon-10828] 스택

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

push X: 정수 X를 스택에 넣는 연산이다.
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 스택에 들어있는 정수의 개수를 출력한다.
empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1

14  
push 1  
push 2  
top  
size  
empty  
pop  
pop  
pop  
size  
empty  
pop  
push 3  
empty  
top

예제 출력 1

예제 입력 2

7
pop
top
push 123
top
pop
top
pop

예제 출력 2

-1
-1
123
123
-1
-1

[코드]


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws Exception {
        stack();
    }
    public static void stack() throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = parseInt(in.readLine());
        String stack[] = new String[n];
        int size = -1;

        for (int i = 1; i <= n; i++) {
            String input = in.readLine();
            if (input.contains("push")) {
                stack[++size] = input.split(" ")[1];
            } else if (input.equals("pop")) {
                out.write(size == -1 ? size + "\n" : stack[size--] + "\n");
            } else if (input.equals("size")) {
                out.write((size + 1) + "\n");
            } else if (input.equals("empty")) {
                out.write((size == -1 ? 1 : 0) + "\n");
            } else if (input.equals("top")) {
                out.write((size == -1 ? size : stack[size]) + "\n");
            }
            out.flush();
        }
        in.close();
        out.close();
    }

    public static int parseInt(String arg) {
        return Integer.parseInt(arg);
    }
}

문제 사이트 : https://www.acmicpc.net/problem/10828

1. 알고리즘 개요(Algorithm Overview)

Posted on 2020-03-17 Edited on 2020-03-19 In Computer , Algorithm Disqus:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

알고리즘(Algorithm)

알고리즘은 수학, 컴퓨터과학, 언어학 또는 관련분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.

계산 또는 작업을 처리하기 위한 순서
요리의 레시피(요리의 재료를 이용하여 레시피 대로 요리한 다음 요리를 완성)
특정문제를 컴퓨터로 해결하기 위한 순서
어떤 문제를 해결하는 방법을 모두 알고리즘이라 한다.


입력	0개 이상의 입력이 존재햐아한다
출력	1개 이상의 출력이 존재해야한다
명백성	각 명령어의 의미는 모호하지 않고 명확해야한다
유한성	한정된 수의 단계 후에는 반드시 종료되어야한다
유효성	각 명령어들은 실행 가능한 연산이어야 한다

코딩 테스트나 인터뷰에서 알고리즘을 보는 이유는 문제를 모델링하고 해결하는 능력을 알아보기 위해서이다.

알고리즘의 효율성(Efficiency)

알고리즘 문제를 해결하는 어떤 코드를 작성했을 때, 이 프로그램의 효율성을 알고싶을 때

수행시간
사용한 메모리
코드의 길이

중 수행시간이 중요하다.

예를들어 어떤 프로그램을 작성했는데, 시간이 10일 걸리면 10일동안 실행해야하고, 메모리가 64GB가 필요할 경우 메모리가 부족하면 램을 구매하면 된다.
이런 문제를 해결할 때는 시간이 중요.

문제의 크기(Scale Of Problem)

개발중 접하게 되는 문제를 해결하는 과정에는 항상 문제의 크기가 발생한다.

‘게임 동시 접속자 수’, ‘쇼핑몰 장바구니 물건의 수’ 등 이런 문제의 크기를 보통 N이라 하고, N에 따라 걸리는 시간이 다르다.
웹 사이트를 만드는 경우 100명이 동시에 접속하는 것과 10만명이 동시에 접속하는 사이트를 만드는 방법은 큰차이가 있으며 접속자가 많을 경우 사이트를 만드는 방법은 더 어렵다. 이럴 때도 문제의 크기에 따라 최적은 방법을 선택해야한다.

문제를 해결할 때는 문제의 크기를 먼저 보고 방법을 생각해야 한다.

알고리즘의 복잡도 분석(Complexity Analysis)

알고리즘 복잡도 분석은 직접 구현하지 않고 모든 입력을 고려하는 방법으로 하드웨어나 소프트웨어어 환경과 관계없이 알고리즘의 수행시간 및 효율성을 평가할 수 있다.

알고리즘이 수행하는 연산의 횟수를 측정
연산의 횟수는 N함수로 표현된다.

알고리즘의 분석 방법에는 기억 공간을 분석하는 공간 복잡도(Space Complexity)와 실행 시간을 분석하는 시간복잡도(Time Complexity)가 있다.

공간복잡도(Space Complexity)

알고리즘의 메모리 사용량에 대한 분석결과로 대략적으로 얼마나 공간을 사용할지 예상할 수 있다.

시간복잡도(Time Complexity)

알고리즘의 수행시간 분석결과로 시간 복잡도를 이용하면 작성한 코드의 수행 시간이 얼마나 걸릴지 예상할 수 있다.

시간복잡도에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게할 목적으로 빅-오 표기법(Big-O Notation)을 이용하여 복잡도를 표시한다.

빅오 표기법의 수학적 정의

두 개의 함수 $f(n)$ 과 $g(n)$이 주어졌을 때 모든 $n \geqq n_0$ 에 대하여 $|f(n) \leqq c|g(n)|$을 만족하는 2개의 상수 $c$와 $n_0$가 존재하면 $f(n) = O(g(n))$이다

즉 입력크기 N에 대하여 얼마나 시간이 걸릴지 나타내고, 최악의 경우 시간이 얼마나 걸리지 알 수 있다.

빅오 표기법은 연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차 항만을 남기고 다른 항들과 상수항을 버리는 것이다. 궁극적으로 최고차 항의 계수도 버리고 단지 최고차 항의 차수만을 사용한다.

상수는 버린다.
- $O(3N^2) = O(N^2)$
- $O({1 \over 2} N^2) = O(N^2)$
- $O(5) = O(1)$
두 개 이상 항이 있을 때 최고차의 항의 차수만 사용한다.
- $O(N^2 + N) = O(N^2)$
- $O(N^2 + N\log N) = O(N^2)$
두 가지 항이 있는데 다른 변수가 있으면 둔다
- $O(N^2 + M)$

대표적인 시간복잡도

$O(1)$ : 상수
$O(\log N)$ : 로그
$O(N)$ : 선형
$O(N\log N)$ : 선형로그
$O(N^2)$ : 2차
$O(N^3)$ :3차
$O(2^N)$ : 지수
$O(N!)$ : 팩토리얼

실행시간

$O(1) < O(\log N) < O(N) < O(N\log N) < O(N^2) < O(N^3) < O(2^N) < O(N!)$

Ex1) 1부터 N까지의 합

i 는 1부터 N번을 수행하므로 시간복잡도 : $O(N)$

int sum = 0;
for (int i = 1; i<=N; i++) {
    sum+= i;
}

Ex2) 1부터 N까지의 합

N번을 2번 수행하므로 시간복잡도 : $O(N^2)$

int sum = 0;
for (int i = 1; i<=N; i++) {
    for (int j = 1; j<=N; j++) {
       sum+= j;
    }
}

Ex3) 1부터 N까지의 합을 계산

1번의 연산만 수행하므로 시간복잡도 : $O(1)$
1
2
int sum = 0;
sum = N * (N + 1) / 2;

참조

code.Plus : https://code.plus/course/41
C언어로 쉽게 풀어쓴 자료구조
위키피디아 : https://ko.wikipedia.org/wiki/알고리즘