🦁_21.12.14 TIL

21년 12월 14일

📝 자료구조 및 알고리즘

체크 리스트

• 플랫폼에 익숙해지기
• 사용 가능한 라이브러리 확인
• 언어 선택(속도 : c++, 풀이 : python)
• 코드 스니펫(트리, 검색, 순열, 조합, 최단경로(ex 다익스트라)), Cheat sheet와 종이 미리 준비
• 유용한 라이브러리 정리
• 예외처리 하기

몸풀기

문제1) 1부터 10,000까지 8이라는 숫자가 총 몇번 나오는가?

8이 포함되어 있는 숫자의 갯수를 카운팅 하는 것이 아니라 8이라는 숫자를 모두 카운팅 해야 한다.
예를 들어 8808은 3, 8888은 4로 카운팅 해야 함
https://codingdojang.com/scode/393?answer_mode=hide

// 문제 풀이
// 빈 배열 만드는 방법
Array(10);
let x = Array(10);
x[2] = undefined;
x[3] = null;
x;
// [비어있음 x 2, undefined, null, 비어있음 x 6]
x.length = 20;
x;
// [비어있음 x 2, undefined, null, 비어있음 x 16]
Array(10).fill(0);
Array(10).fill(10);
// Array(100).fill().map((_, i) => i + 1)
// [...Array(100)].map((_, i) => i + 1)
Array(100)
  .fill(1)
  .map((val, idx) => val + idx);
".".repeat(10);
".".repeat(10).split("."); // lenght : 11
".".repeat(9).split("."); // lenght : 10
Array.from("abc");
Array.from("a", repeat(10));
Array.from("ab", repeat(10));

Array(100)
  .fill(1)
  .map((val, idx) => val + idx) + "";

(
  Array(100)
    .fill(1)
    .map((val, idx) => val + idx) + ""
).split("8").length - 1; 
// 8이 1개인 경우 8을 기준으로 나뉘면서 배열이 2개로 쪼개짐 => length - 1을 하는 이유

문제2) 1차원의 점들이 주어졌을 때, 그 중 가장 거리가 짧은 것의 쌍을 출력하는 함수를 작성하시오. (단 점들의 배열은 모두 정렬되어있다고 가정한다.)

예를 들어 S={1, 3, 4, 8, 13, 17, 20} 이 주어졌다면, 결과값은 (3, 4)가 될 것이다.
https://codingdojang.com/scode/408?langby=javascript#answer-filter-area

let s = [1, 3, 4, 8, 13, 17, 20];
let arr = new Array();
// for (let i = 0; i < s.length - 1; i++) {
//   console.log(s[i + 1] - s[i]);
// }
//  위와 동일한 코드
for (let i = 1; i < s.length; i++) {
  // console.log(s[i] - s[i - 1]);
  arr.push(s[i] - s[i - 1]);
}

// arr.indexOf(5)
let result = arr.indexOf(Math.min(...arr));
console.log(s[result], s[result + 1]);

// 다른 풀이
let s = [1, 3, 4, 8, 13, 17, 20];
// let ss = [3, 4, 8, 13, 17, 20];

// const zip = (a, b) => a.map((v, i) => [v, b[i]]);
const zip = (a, b) => a.map((val, idx) => [val, b[idx]]);

// zip(s.slice(), s.slice(1)).slice(0, -1);
// zip(s.slice(0, s.length - 1), s.slice(1));
let pairs = zip(s.slice(), s.slice(1)).slice(0, -1);

// -1 순서 유지
// 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);
pairs.sort(compare)[0];

// 쉬운 풀이
let s = [1, 3, 4, 8, 13, 17, 20];

const zip = (a, b) => a.map((val, idx) => [val, b[idx]]);
let pairs = zip(s.slice(0, s.length - 1), s.slice(1));

// 초기값, for문 안에서는 최솟값을 비교하는 용도로 사용
// MAX_SAFE_INTEGER를 주로 사용
// let init = Number.MAX_SAFE_INTEGER;
// let init = Number.MIN_SAFE_INTEGER;
let init = pairs[0][1] - [0][0];
// result는 최종 결과값
let result = [];

for (let i of pairs) {
  // console.log(i);
  if (init > i[1] - i[0]) {
    init = i[1] - i[0];
    result = i;
  }
}

console.log(result);

📎 스택(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();
    }
    // index가 있을경우
    // let result = this.arr[index];
    // this.arr = [...this.arr.slice(0, index), ...this.arr.slice(index + 1)];
    let result = this.arr.splice(index, 1);
    return result;
  }

  empty() {
    if (arr.length === 0) {
      return true;
    } else {
      return false;
    }
  }

  top() {
    return this.arr[this.arr.length - 1];
  }

  bottom() {
    return this.arr[0];
  }
}

let s = new Stack();
s.push(10);
s.push(20);
s.push(30);
s.push(100);
s.push(200);
s.push(300);

s.pop();
console.log(s);

s.pop(2);
console.log(s);

📎 연결리스트(Linked list)

• 개념 : https://en.wikipedia.org/wiki/Linked_list
• 알고리즘 시각화 : https://visualgo.net/ko
  
  
• 연결리스트, 메모리 효율을 위해 사용되는 경우가 많음
  => Javascript에서는 메모리 효율이 그다지 좋지 못함

const list = {
  head: {
    value: 90,
    next: {
      value: 2,
      next: {
        value: 77,
        next: {
          value: 35,
          next: null, // 마지막 값은 null을 가리킨다
        },
      },
    },
  },
};

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;
  }

  length() {
    return this.데이터수;
  }

  append(data) {
    let 새로운노드 = new Node(data);
    // 마지막 값이 null에서 새로운 노드가 됨
    this.tail.next = 새로운노드;
    // 마지막 노드는 새로운 노드가 됨
    this.tail = 새로운노드;
    this.데이터수 += 1;
  }

  toString() {
    let 순회용현재노드 = this.head;
    순회용현재노드 = 순회용현재노드.next;

    let s = "";
    for (let i = 0; i < this.데이터수; i++) {
      s += `${순회용현재노드.data},`;
      순회용현재노드 = 순회용현재노드.next;
    }
    // 맨 마지막에 콤마와 띄어쓰기가 있으므로 -1 작성
    return s.slice(0, -1);
  }

  get fullData() {
    let 순회용현재노드 = this.head;
    순회용현재노드 = 순회용현재노드.next;

    let s = "";
    for (let i = 0; i < this.데이터수; i++) {
      s += `${순회용현재노드.data},`;
      순회용현재노드 = 순회용현재노드.next;
    }
    return JSON.parse(`[${s.slice(0, -1)}]`);
  }
}

// console
l = new LinkedList();
l.append(1);
l.append(2);
l.append(3);
l.append(10);
l.append(20);
l.append(30);
l.length();

📝 온라인 강의 수강

📎 코드라이언 - 일단 만드는 Javascript

---

마무리

• 수업 전에 리액트랑 파이어베이스 셋팅만 해놓자
  => 실패!^^ 아유 나 자신 답답♡
• 자료구조와 알고리즘 타이틀만 들어도 막막했는데 설명을 들을 수 있어서 좋았습니다.
  => 전에 공부해뒀던 것이 또 도움이 되었다!
• 애플펜슬 구매 기념 이벤트 그림 그리기 너무 재밌네요 호호호호
  => 너무 즐거워라