[Front-end🦁] #33 알고리즘, 자료구조 (Stack, LinkedList)

오늘은 알고리즘을 처음 나간 날이었다. 어려운 문제를 풀진 않았지만, C++도 아니고 기본 C를 쓰던 나에게는 js에 있는 아름다운 빌트인 함수들을 쓰는 법을 배우는 좋은 기회였다! 파이썬에도 대체로 있으니까 찾아보고 풀면 될 것 같다. Swift로도... 풀어야지...

1. 알고리즘

컴퓨터가 어떤 일을 하기 위해서 알려줘야 하는 순서, 절차

<측정 방법>
1. 시간 복잡도
2. 계산 복잡도 - Big O
3. 공간 복잡도

coding test tips✨

• 프로그래머스, 구름 EDU 같은 플랫폼에 익숙해지기.
• 사용 가능한 언어, 라이브러리 미리 확인하기.
• 코드 스네핏 (트리, 검색, 순열, 조합, 최단경로), Cheat Shetet와 A4 용지는 미리 준비
• 유용한 라이브러리 미리 정리해두기
• 예외처리 꼬옥!

2. 문제풀이

1. 8의 개수 구하기

문제1

핵심 코드

// 와 천잰데 배열에 있는 것을 문자열로 다 합쳐놓고
// 8을 기준으로 나누면 8개수 + 1 만큼 나눠지니깐
// -1 하면 8의 갯수가 나온다.
Array(100).fill(1).map((value, index) => value + index + '').split('8').length - 1;

2. 거리가 가장 짧은 것의 쌍 출력

문제2

핵심 코드 - 1번째 방법

// 새로운 배열에 인접 점들의 거리를 넣고
for(let i = 0; i < s.length - 1; i++) {
    arr.push(s[i+1] - s[i]);
}
// 거리 최소 값에 해당하는 index를 찾아서 해당 점과 그 다음 점 출력.
let result = arr.indexOf(Math.min(...arr));
console.log(`(${s[result]}, ${s[result + 1]})`);

핵심 코드 - 2번째 방법

// 두개씩 array에 넣어놓고 이용
const zip = (a,b) => a.map((value, index) => [value, b[index]]);
let pairs = zip(s.slice(0, s.length-1), s.slice(1));
// 그리고 정렬 메소드를 이용해서 정렬.
// 대신 문제 상황에 맞춰서 차를 가지고 한다.
function compare(a, b) {
    if( a[1] - a[0] < b[1] - b[0] ) {
        return -1;
    }
    if ( a[1] - a[0] > b[1] - b[0] ) {
        return 1;
    }
    return 0;
}
pairs.sort(compare);
console.log(pairs[0]);

• 나 같으면 그냥 for문에서 최솟값, 최소 인덱스 저장해놓고 따로 거리 차를 배열에 안넣고 풀었을 것 같은데, 이렇게도 풀 수 있구나 싶었다.
• 만약 반복문으로 최솟값 구할거면, min 초기값에 Infinity 대신 Number.MAX_SAFE_INTEGER 넣자.

3. 자료구조

1. Stack

위만 열려있어서 위로만 넣었다 뺐다 할 수 있는 구조

class Stack {
  constructor() {
      this.arr = [];
  }
  push(data) {
      this.arr.push(data);
  }
  pop(index = this.arr.length - 1) {
    // 원래는 index 없지만 넣어서 구현해 봄.
    if (index === this.arr.length - 1) {
        return this.arr.pop();
    }
    let result = this.arr[index];
    this.arr = [...this.arr.slice(0, index)] + [...this.arr.slice(index + 1)];
    return result;
  }
  empty() {
      return (this.arr.length == 0) ? true : false;
  }
  top() {
      return this.arr[this.arr.length - 1];
  }
  bottom() {
      return this.arr[0];
  }
}

let s = new Stack();
s.push(10);
s.pop();
s.top();
s.bottom();
s.empty();

2. 연결 리스트 (Lineked List)

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        let init = new Node('init');
        this.head = init;
        this.tail = init;
        this.현재노드 = undefined;
        this.데이터수 = 0;
    }
    get fullData() {
        let currentNode = this.head;
        currentNode = currentNode.next;
        let s = ''
        for (let i = 0; i < this.데이터수; i++) {
            s += `${currentNode.data}, `;
            currentNode = currentNode.next;
        }
    }
    length() {
        return this.데이터수;
    }
    append(data) {
        let newNode = new Node(data);
        // 마지막 값은 새로운 노드
        this.tail.next = newNode;
        // 마지막 노드는 새로운 노드
        this.tail = newNode;
        this.데이터수 += 1;
    }
    toString() {
        let currentNode = this.head;
        currentNode = currentNode.next;
        let s = [];
        while (currentNode) {
            s.push(currentNode.data);
            currentNode = currentNode.next;
        }
        return `${s.join(' -> ')}`
    }
    insert(index, data) {
        let currentNode = this.head;
        currentNode = currentNode.next;
        for(let i = 0; i < index; i++) {
            currentNode = currentNode.next;
        }
        let newNode = newNode(data);
        newNode.next = currentNode.next;
        currentNode.next = newNode;
        this.데이터수 += 1;
    }
}

2. 작은 회고

1. 오늘은 알고리즘 문제를 2개 풀었다.

• 사실 풀 수 있는 문제이긴 했다.
• 하지만 반복문만 돌리는 것 말고 내가 상상치 못한 방법으로 푼 풀이와 빌트인 함수들을 기준으로 복습하기
  

2. 자료구조 스택, 연결리스트를 공부했다.

• 위에 정리한 직접 구현법 다시 공부해보기 전에
• 학교 수업에서 들었던.. 수업 자료로 개념 복습하고
• C로도 구현해보기

+ 지금 들어와보니까 클론 스터디 해야지... 수업 복습도 해야지.. 심지어 지난주에는 면접가고 회식가고.. 너무 정신 없다. 그러다보니 딥다이브가 먼저 낙오됐다.... 이제 면접은 없으니까 수업 복습 -> 클론 -> 딥다이브 순으로 달려보자고!!!