22-10-31-자료구조, 알고리즘

워밍업 문제

1. 1차원 점들 중 가장 거리가 짧은 것의 쌍을 출력하는 함수 작성
   S = [1, 3, 4, 8, 13, 17, 20] 이 주어졌다면, 결과값은 (3, 4)

• 방법 1

let s = [1, 3, 4, 8, 13, 17, 20];
let arr = [];
for (let i = 1; i < s.length; i++) {
	arr.push(s[i] - s[i-1]);
}
let index = arr.indexOf(Math.min(...arr));
console.log(s[index], s[index + 1]);

• 방법 2

let s = [1, 3, 4, 8, 13, 17, 20];
let 최솟값 = Infinity;
let 최솟값인덱스 = 0;
for (let i = 1; i < s.length; i++) {
	if (Math.abs(s[i] - s[i - 1]) < 최솟값) {
    	최솟값 =Math.abs(s[i] - s[i - 1]);
        최솟값인덱스 = i;
    }
}
console.log(s[최솟값인덱스], s[최솟값인덱스 - 1]);

Infinity로 시작해서 최솟값을 계속 바꿔준다는 점이 인상깊었다.

스택과 큐

스택 : 삽입 (push), 삭제 (pop)
큐 : 삽입 (push), 삭제 (shift)
unshift -> 맨 앞에 삽입
shift -> 맨 앞 값 삭제
push -> 맨 뒤 값 삽입
pop -> 맨 뒤 값 꺼냄

class Stack {
    constructor(){
        this.arr = []; 
        this.length = 0;
    }

    push(data){
        this.arr.push(data);
        this.length += 1;
    }

    pop(index){
        if (this.length == 0){
            return
        }
        if (index > this.arr.length - 1){
            this.length -= 1
            return this.arr.pop()
        }
        let result = this.arr.splice(index, 1)
        this.length -= 1
        return result
    }

    empty(){
        if (this.length == 0){
            return 1
        } else {
            return 0
        }
    }

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

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

    display(){
        return this.arr
    }
  }

  let s = new Stack()
  s.push(10)
  s.push(20)
  s.push(30)
  s.push(40)
  s.push(50)
  s.display()

연결리스트

• class로 node 구현

class Node {
	constructor(data) {
    	this.data = data;
      	this.next = null;
    }
}
const node1 = new Node(90);
const node2 = new Node(2);
const node3 = new Node(77);
const node4 = new Node(35);
const node5 = new Node(21);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

node1.next.next.next.data; // 35

• class로 linkedList 구현

class Node {
	constructor(data) {
    	this.data = data;
      	this.next = null;
    }
}
class LinkedList {
	constructor() {
    	let init = new Node('init');
      	this.head = init;
      	this.tail = init;
    }
  	append(data) {
    	let newNode = new Node(data);
      	this.tail.next = newNode;
      	this.tail = newNode;
    }
}
const l = new LinkedList();
l.append(1);
// (1, null)
l.append(2);
l.append(3);
l.append(10);
l.append(15);
l.append(17);
l.append(36);

• toString을 순회로 구현!! (처음부터 순서대로 방문 - 순회)

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.length = 0
    }

    length(){
        return this.length
    }
    toString() {
        let 순회용현재노드 = this.head;
        // 처음 순회용 현재 노드가 init이기 때문에
        순회용현재노드 = 순회용현재노드.next

        let 출력데이터 = '';
        for (let i = 0; i < this.length; i++) {
            출력데이터 += `${순회용현재노드.data}, `;
            순회용현재노드 = 순회용현재노드.next;
        }
        return 출력데이터;
    }
    append(data){
        let 새로운노드 = new Node(data)
        // 마지막 값(null)은 새로운 노드가 됨
        this.tail.next = 새로운노드
        // 마지막 노드는 새로운 노드가 됨
        this.tail = 새로운노드
        this.length += 1
    }
}

l = new LinkedList()
l.append(1)
l.append(2)
l.append(3)
l.append(10)
undefined
l.toString();