0826 TIL 자료구조

🙆‍♀️자료구조가 무엇인지 설명할 수 있다.

자료구조 = 여러 데이터들의 묶음을 저장하고 사용하는 방법을 정의하는 것이다.

🙆‍♀️Stack, Queue, Tree, Graph 자료구조에 대해 이해할 수 있다.

• Stack : 데이터를 순서대로 쌓는 자료구조이다.
  입출력이 한 방향으로 이루어지는 제한적 접근에 있다.
  LIFO(Last In First Out) 혹은 FILO(First In Last Out) 이라고 부른다.

• Queue : 대기행렬이라는 뜻. 먼저 들어간 데이터가 먼저 나온다.
  FIFO(First In First Out)

• Tree : 단방향 그래프의 한 구조로 나무와 닮아있어 트리구조라 부른다.
  가계도처럼 데이터가 바로 아래에있는 하나이상의 데이터에 단방향으로 연결된 계층적 자료구조이다.

• Graph : 여러개의 점들이 서로 복잡하게 연결되어있는 관계를 표현한 자료구조이다.

🙆‍♀️알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내낼 수 있다.

🙆‍♀️각 자료구조의 개념과 구조를 파악하고 목적을 이해할 수 있다.

🙆‍♀️알고리즘 문제의 각 상황에 맞는 자료구조를 떠올릴 수 있다.

🙆‍♀️트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.

🙆‍♀️Binary Search Tree를 이해할 수 있다.

이진탐색트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다.

Stack , Queue

🙆‍♀️배열로 Stack, Queue를 사용할 때 주의해야 할 사항은 어떤것들이 있나요?

Stack 에서는 push,pop,empty,size 메서드를 만든다.
Queue 에서는 push,shift,empty,size 메서드를 만든다.

🙆‍♀️배열로 Stack을 사용할 때 push, pop 이외에 필요한 메서드를 어떻게 구현할 수 있나요?

🙆‍♀️배열로 Queue를 사용할 때 push, shift 이외에 필요한 메서드를 어떻게 구현할 수 있나요?

🙆‍♀️JavaScript의 배열과 Stack, Queue는 어떤 차이가 있나요?

자바스크립트 배열은 push,pop,shift,unshift 등 메서드를 사용해서 원하는 요소를 순서에 상관없이 넣었다가 뺄 수 있지만 stack과 queue는 순서를 지켜서 요소가 빠져야한다.

Stack으로 브라우저 뒤로가기 앞으로가기 구현

처음엔 이해가 안갔는데 그림을 그려보니 이해가 되었다.

function browserStack(actions, start) {  //그려보니까 이해가됌

  let prevStack = []; //뒤로가기
  let nextStack = []; //앞으로가기
  let current = start; //현재 페이지
  
  for(let i = 0; i < actions.length; i++) {
    // 만약 actions 배열의 요소가 -1이고(뒤로가기를 눌렀고), prevStack의 길이가 0이 아닐 때(이전으로 돌아가는 페이지가 있다면)
    if(actions[i] === -1 && prevStack.length !== 0) {
      let prevPage = prevStack.pop(); //이전 페이지 = 뒤로가기에서 사라진 페이지
      nextStack.push(current); //현재페이지가 앞으로가기배열로 들어간다.
      current = prevPage; //현재 페이지는 뒤로가기를 눌럿러서 prevStack에서 사라진 이전페이지로 변한다

      // 만약 actions 배열의 요소가 1이고(앞으로가기를 눌렀고), nextStack의 길이가 0이 아닐 때(다음으로 넘어가는 페이지가 있다면)
    } else if(actions[i] === 1 && nextStack.length !== 0) {
      let nextPage = nextStack.pop(); //다음페이지 = 앞으로가기에서 사라진 페이지
      prevStack.push(current); //뒤로가기에 현재페이지를 추가해준다.
      current = nextPage; //현재페이지는 앞으로가기를 눌러서 nextStack에서 사라진 페이지가 된다.

      // 만약 actions 배열의 요소가 알파벳이라면 (새로운 페이지라면)
    } else {
      // prevStack에 current를 삽입합니다.
      // current에 현재 알파벳 요소를 할당합니다.
      // 새로운 페이지는 앞으로 갈 수 없기 때문에 nextStack을 비웁니다.
      prevStack.push(current);
      current = actions[i];
      nextStack = [];
    }
  }
  
  // 배열에 prevStack, current, nextStack을 순서대로 담아 반환합니다.
  return [prevStack, current, nextStack];
}

Queue 박스포장

function paveBox(boxes) {
  let answer = [];

    while(boxes.length > 0){
        let finishIndex = boxes.findIndex(el => boxes[0] < el); //0번째요소보다 큰 요소를 찾는다.
        if(finishIndex === -1){ //0번째 요소보다 큰 요소가 없다면  
            answer.push(boxes.length); //boxes의 길이를 answer배열에 넣고  //[3,1]
            break

        } else { //0번째요소보다 큰 요소를 찾았다면
            answer.push(finishIndex); // 큰요소의 인덱스를 answer배열에 넣는다.
            boxes.splice(0, finishIndex); //boxes배열의 0번째요소에서 finishIndex 바로 앞까지의 요소를 다지운다  
        }    //boxes = [6] -> 다시 while문 돌아감
    }
    return Math.max(...answer);  //[3,1] -> 3
}

boxes가 [5, 1, 4, 6]이라고 가정하면, 3이 출력되어야한다.
boxes의 길이가 4기때문에 while문으로 들어가고 finishIdx는 3이된다.(6의 인덱스)
else문으로 들어가고 answer = [3]이 되고 boxes는 [6]이된다.

boxes의 길이는 1이기때문에 다시 while문이 돌아가고 finishIndex는 -1이 된다.
if문에 들어가고 answer는 [3,1]이 된다. 그리고 3이 리턴된다.

그 외

array.findIndex : 주어진 판별 함수를 만족하는 배열의 첫 요소에대한 인덱스를 반환한다. 만족하는 요소가 없으면 -1을 반환한다.

느낀 점

오늘 toy도 겨우 이해했는데, 내일이나 모레보면 또 까먹을것같고 재귀함수도 여전히 어렵고, 자료구조는 더 모르겠고 걱정만 쌓여간다. 안되면 될때까지 해야지뭐 ㅎ