Algorithm Study #2 (Data Structure-1)

jakeseo_me·2019년 2월 13일
1

java algorithm study

목록 보기
6/18

스택

  • 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조

  • 마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out (LIFO)라고도 한다.

  • push: 스택의 가장 위에 자료를 넣는 연산

  • pop: 스택의 가장 위의 자료를 빼는 연산

  • top: 스택의 가장 위의 자료를 보는 연산

  • empty: 스택이 비어있는지 아닌지를 알아보는 연산

  • size: 스택에 저장되어 있는 자료의 개수를 알아보는 연산

  • 스택의 구현
    - 배열을 이용하여 구현
    - push의 구현
    - stack의 size번째의 배열에 값을 넣고 size를 1 증가시키면 된다.
    - pop의 구현
    - stack의 size-1번째를 지워버리고 size를 -1하는 것

  • 스택의 예제 1
    - boj.kr/9012
    - 올바른 괄호 문자열인지 알아보는 문제
    - 괄호문자열이란?
    - (와 )로만 이루어진 문자열
    - 올바른 괄호 문자열: 괄호의 쌍이 올바른 문자열
    - 닫는 괄호의 위치는 어디에 위치해야 할까?
    - 왼쪽에 있어야 한다.
    - 아직 짝이 맞지 않아야 한다.
    - 가장 오른쪽에 있는 괄호.
    - 가장 빠르게 떠오른 아이디어
    - 닫는 괄호의 개수와 여는 괄호의 개수를 세어서 맞으면 클리어?
    - )( 등의 문제를 해결할 수 없다.
    - 스택에 괄호를 순서대로 PUSH하고 괄호가 맞아떨어지면 POP
    - 마지막에 닫는 괄호가 나왔는데 스택이 비어있다면 여는 괄호가 부족
    - 마지막에 여는 괄호가 나왔는데 스택이 비어있다면 닫는 괄호가 부족
    - 마지막에 스택에 아무것도 남지 않는다면 클리어
    - CNT를 이용한 문제 해결 아이디어
    - 기존 개수 세기 아이디어에서 발전
    - '(' 여는 괄호가 들어온 경우와 ')' 닫는 괄호가 들어온 경우를 구분하여 조건

  • 스택의 예제 2
    - 쇠막대기 boj.kr/10799
    - 쇠막대기 문제 조건
    1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '()'로 표기 모든 '()'는 반드시 레이저를 표기
    2. 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 닫힌 괄호 ')'로 표현된다.
    - PS 아이디어
    1. 괄호를 받으며 위치를 인덱스로 기록하며 쇠막대인지 레이저인지 판단
    - 열린 괄호를 만날 때 index를 기록
    - 닫히는 괄호를 만나면 pop
    - pop되는 순간 자신이 레이저인지 쇠막대인지 구분한다.
    - index의 차이가 1이라면 레이저
    - 아니라면 쇠막대
    2. 쇠막대를 지나가는지 판단
    - 쇠막대 길이를 저장하는 배열을 만들고 레이저가 그 범위 안이라면 쇠막대는 2조각으로 잘린다.
    3. 초기값
    - 일단 쇠막대가 하나도 잘리지 않더라도 쇠막대는 그 갯수만큼 조각 수를 갖는다.
    - PS 정석 아이디어
    - 레이저가 발생하는 경우
    - Stack에 아무것도 없는데 레이저가 발생하는 경우
    - 아무런 영향을 미치지 못한다.
    - Stack에 무언가가 들어있을 때 레이저가 발생하는 경우
    - size만큼 piece를 더해주게 된다.
    - 그 이유는 괄호가 언젠간 닫히는 것이 보장되어 있기 때문
    - 쇠막대기가 발생하는 경우
    - piece에 1을 더해준다.
    - 쇠막대기 자체도 piece이기 때문.
    - 실제 구현 소스

    public static void main(String args[]) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Stack stack = new Stack();
    char[] parentheses = br.readLine().toCharArray();

    }
    }

  • 스택의 예제 3
    - '에디터' boj.kr/1406
    - 조건
    - 커서: 문장의 맨 앞, 맨 뒤, 문장 중간 임의의 곳에 위치 가능
    - L : 커서를 왼쪽으로 한 칸 옮김
    - D : 커서를 오른쪽으로 한 칸 옮김
    - B : 커서 왼쪽에 있는 문자를 삭제함
    - P $ : $라는 문자를 커서 오른쪽에 추가함. 커서는 $에 위치
    - 입력받은 명령어를 수행한 뒤의 문자를 출력하면 된다.
    - 문제의 N제한이 중요하다.
    - 길이가 10만을 넘지 않는다.
    - 명령어의 갯수는 60만을 넘지 않는다.
    - 아이디어 1
    - LinkedList< Char>를 이용하여 풀기
    - ArrayList vs LinkedList의 상황에서 LinkedList는 Add Remove가 O(1)의 시간이어서 선택
    1. LinkedList에 문자열을 한자씩 넣어놓는다.
    2. 커서의 위치는 index라는 변수에 저장
    - index는 0이하로 줄지 않는다.
    - index는 ArrayList의 길이보다 커지지 않는다.
    3. B(DELETE)명령어는 index번째에 있던 문자를 지운다.
    4. P $는 index번째에 문자를 추가시킨다.
    - 구현
    - A

스택의 활용

  • 스택은 가장 가까운 자료만 의미를 가질 때, 사용하면 좋다.
  • 가장 가까운 자료의 삽입, 삭제가 O(1)의 시간 복잡도를 갖는다.
profile
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다.

0개의 댓글