✏️ Achievement Goals

✅ 자료구조가 무엇인지 설명할 수 있다.
✅ Stack, Queue, Tree, Graph 자료구조에 대해 이해할 수 있다.
✅ 알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내 낼 수 있다.
✅ 각 자료구조의 개념과 구조를 파악하고 목적을 이해할 수 있다.
✅ 알고리즘 문제의 각 상황에 맞는 자료구조를 떠올릴 수 있다.
✅ 트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.
✅ Binary Search Tree를 이해할 수 있다.
✅ BFS와 DFS의 개념을 이해하고 알고리즘 문제에서 사용할 수 있다.
✅ 자료구조를 활용하여 알고리즘 문제에 접근할 수 있다.

📝summary

1. 자료구조란?

메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 목표다
상황에 맞게 적절하게 사용될 수 있도록 특정 구조를 이루고 있다
데이터를 사용하려는 목적에 따라 형태를 구분하고, 분류하여 사용한다

자료구조를 활용해서 영화예매사이트를 어떻게 만들 것인가?

고려해야 될 점

현실 -> 사용되는 자료구조
1 어떤 영화를 볼지 선택한다 -> 영화검색 Trie
2 영화를 예매하기 위해 줄을 선다 -> 줄서기 Queue
3 내 차례가 돌아오면 좌석을 선택한다 -> 선택 HashTable
4 돈 결제

자료구조는 일차원적인 컴퓨터 메모리를 현실에 대응되게 구조를 만든 것이라 할 수 있다

2. 자료구조의 종류

선형구조
한 원소뒤에 하나의 원소만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가진다

비선형구조
원소 간 다대다 관계를 가지는 구조로 계층적 구조, 망형구조(그물망형태)를 표현하기에 적절하다

Stack

Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고있다
마치 접시를 쌓아 놓은 형태와 비슷한 이 자료구조는
직역 그대로, 데이터(data)를 순서대로 쌓는 자료구조다

들어간 입구와 나가는 출구가 동일하기 때문에 나중에 들어간 데이터가 가장 먼저 나올 수 있다
이런 Stack 자료구조의 특징을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부른다

배열 메소드 push 와 pop을 사용해서 구현 할 수 있다

stack 의 실사용 예제

웹페이지의 뒤로 가기, 앞으로 가기 기능을 구현할 때 stack 자료구조가 활용된다

올바른 괄호(Stack)

괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.
(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

<script>
    function solution(s){
      // 배열을 만든 뒤 사용하면 된다 
      // 여는괄호를 만났을때 스택에 넣어주고 
      // 닫는 괄호를 만났을때 스택에서 빼주면 된다
      // 정상적인 괄호는 마지막에 스택에 아무것도 없어야 한다 
      let answer = "YES";
      stack = []
      for(let x of s){
        if(x === '('){
          stack.push(x)
        }else{
          if(stack.length===0){
            return "NO"
          }
          stack.pop()
        }
      }
      
      return answer;
    }
    
    let a="(()(()))(()";
    console.log(solution(a));
</script>

괄호 문자 제거

입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하세요.

<script>
    function solution(s){  
      // 여는괄호이거나 문자일때 스택에 push
      // 닫는 괄호를 만나면 스택에서 여는 괄호를 찾아서 사이에있는것도 같이 제거
      let answer;
      let stack = []
      for(let x of s){
        if(x === ')'){
          while(stack.pop() !== '(');
          // 
        }else{
          stack.push(x);
        }
      }
      answer = stack.join('')
      return answer;
    }

    let str="(A(BC)D)EF(G(H)(IJ)K)LM(N)";
    console.log(solution(str));
</script>

크레인 인형뽑기 (카카오 기출)

프로그래머스

<script>
    function solution(board, moves){
      let answer = 0;
      let stack = [];
      moves.forEach(pos => {
        for(let i=0; i<board.length; i++){
          if(board[i][pos-1] !== 0){
            let tmp = board[i][pos-1];
            board[i][pos-1] = 0;
            if(tmp === stack[stack.length-1]){
              stack.pop();
              answer += 2;
            }else{
              stack.push(tmp);
            }
            break
              // 멈춰주지 않으면 1행에서 4만 꺼내야 하는데
              // 맨 마지막까지 꺼내게 된다 
          }
        }
      });
        return answer;
    }
    
    let a=[[0,0,0,0,0],
          [0,0,1,0,3],
          [0,2,5,0,1],
          [4,2,4,4,2],
          [3,5,1,3,1]];

    let b=[1, 5, 3, 5, 1, 2, 1, 4];
    console.log(solution(a, b));
</script>