Stack(1) - 스택과 memorization

Stack

물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조를 말하며 선형구조^[각주:1]를 가진다 마지막에 삽입한 자료가 가장 먼저 꺼내지는 후입선출(LIFO, Last-In-First-Out) 형태이다. 스택은 삽입(push), 삭제(pop), 공백확인(isEmpty), 반환(peek) 연산을 수행한다

스택의 연산

먼저 push 연산을 알아보자. 빈 스택에서는 top의 인덱스가 -1을 가리킨다. 이때 A를 push하면 스택의 맨 위에 A가 저장되고 top인덱스가 0이 된다. 이후 B를 push 하면 맨 위에 B가 저장되고 top 인덱스가 1이 증가된다. 스택의 크기를 넘어가면 overflow 가 발생한다.

pop 연산은 push의 반대이다. 스택에 A -> B -> C 순서대로 저장했을 때 pop 연산을 수행하면 C -> B -> A 순으로 반환하며 스택에서 삭제된다. 스택이 삭제될 때 top 인덱스는 1씩 감소한다. 

스택의 구현

 
/**
 * push, pop 구현
 * @author troh
 *
 */
public class Stack구현1 {
    public static void main(String[] args) {
        Stack stack = new Stack(3);
        stack.push('A');
        stack.push('B');
        stack.push('C');
        
        System.out.println(stack.pop()); // C
        System.out.println(stack.pop()); // B
        System.out.println(stack.pop()); // A
    }
}
 
class Stack {
    private int top = -1;
    
    private char[] stack;
    
    public Stack(int size) {
        this.stack = new char[size];
    }
    
    public void push(char c) {
        if(top == stack.length) {
            throw new RuntimeException("Stack Overflow");
        }
        stack[++top] = c;
    }
    
    public char pop() {
        if(top == -1) {
            throw new RuntimeException("Stack Underflow");
        }
        return stack[top--];
    }
}

스택의 활용 - 괄호 유효성

스택을 활용하여 괄호의 쌍이 올바르게 사용되었는지 판단하는 프로그램을 작성해보자. 괄호의 올바른 사용조건은 아래와 같다.

• 여는 괄호와 닫는 괄호의 개수는 같아야한다
• 여는 괄호가 닫는 괄호보다 먼저 나와야한다
• 괄호사이에는 포함 관계만 존재해야한다

import java.util.EmptyStackException;
import java.util.Stack;
 
public class Stack활용_괄호 {
    public static void main(String[] args) {
        String str = "for(int i=0; i++; i<10)";
        boolean result = bracketCheck(str);
        System.out.println(result);
    }
    
    public static boolean bracketCheck(String str) {
        Stack<Character> bracketStack = new Stack<>();
        try {
            for(int i=0; i<str.length(); i++) {
                char c = str.charAt(i);
                if(isOpenBracket(c)) {
                    bracketStack.push(c);
                } else if(isCloseBracket(c)) {
                    bracketStack.pop();
                }
            }
            
            // 괄호의 쌍이 맞는지 확인
            if(!bracketStack.isEmpty()) {
                return false;
            }
            return true;
        } catch (EmptyStackException e) {
            // 여는 괄호보다 닫는 괄호가 먼저 나왔을 때는 유효하지 않는 경우임
            return false;
        }
    }
    
    /**
     * 여는 괄호인지 판단
     * @param c
     * @return
     */
    public static boolean isOpenBracket(char c) {
        return c == '(' ;
    }
    
    /**
     * 닫는 괄호인지 판단
     * @param c
     * @return
     */
    public static boolean isCloseBracket(char c) {
        return c == ')' ;
    }
}
 

Memorization 

컴퓨터 프로그램을 실행하 ㄹ때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. 피보나치 수열의 재귀함수^[각주:2]를 Memorization을 사용하여 효율적으로 처리할 수 있다. 피보나치 수열을 재귀함수로 구현하면 중복 함수 호출이 많기 때문이다. 

다음은 피보나치 수열의 n번째 수를 구하는 일반적인 방법이다. 

 
public class FibonacciNumbers {
    public static void main(String[] args) {
        int num = fibonacciNumber(21);
        System.out.println(num);
    }
    
    public static int fibonacciNumber(int index) {
        if(index <= 2) {
            return 1;
        }
        
        return fibonacciNumber(index-1) + fibonacciNumber(index-2);  
    }
}
 

위의 알고리즘의 동작을 그림으로 살펴보면 많은 중복 호출이 있는것을 알 수 있다. fibonacciNumber 함수를 F로 표현하겠다.

위의 그림을 보면 함수가 중복적으로 많이 호출되는 것을 알 수 있다. 피보나치의 n이 커질수록 중복은 많아질 것이다. 이러한 중복을 해결하는 방법이 Memorization이다. 이를 이용하여 구현한 코드를 살펴보자.

 
public class FibonacciNumbers_Memorization {
    private static Integer[] memories ;
    
    public static void main(String[] args) {
        memories = new Integer[46];
        
        long start = System.currentTimeMillis();
        
        int num = fibonacciNumber(45);
        
        long end = System.currentTimeMillis();
        System.out.println(num);
        System.out.println("실행시간: "+ (end-start));
    }
    
    public static int fibonacciNumber(int index) {
        if(index <= 2) {
            return 1;
        }
        if(memories[index] != null) {
            return memories[index];
        } else {
            memories[index] = fibonacciNumber(index-1) + fibonacciNumber(index-2);
            return memories[index];
        }
    }
}
 

Memorization을 이용하여 45번째 피보나치 숫자를 구한 실행시간은 0 밀리세컨으로 결과값이 나온다. 반면 Memorization을 사용하지 않았을 경우에는 약 3초(2919 밀리세컨)의 실행시간이 소요된다. 이러한 성능 차이는 숫자가 커짐에 따라 더욱 커질 것이다. 

1. 선형구조: 자료 간의 관계가 1대 1의 관계를 가짐. 비선형구조: 자료 간의 관계가 1대 N의 관계를 가짐( 트리 자료구조 ) [본문으로]
2. 자기 자신을 재호출하는 함수 [본문으로]