4일차 배운 것 정리 (1)

이전 내용

7. 큐

7-a. 큐(Queue)란?

First In First Out, 선입선출의 구조를 가진 선형 자료구조

큐의 종류

선형 큐

1.배열을 통한 큐 구현

Queue를 구현할 경우, EnQueue와 DeQueue 시 비워진 공간을 매꾸기 위해 O(n)이 소요되기 때문에 추천되지 않는다.

// 직접 구현해보기
class Queue {

enqueue(){}
dequeue(){}
peek(){}
size(){}
}

2.링크드 리스트를 통한 구현

Head = Front, Tail = Rear로 대응하여 구현 가능

//직접 구현해보기
class Node{}
class Queue{
	enqueue(){}
	dequeue(){}
	peek(){}
	size(){}
}

참고 shift를 통해 간단히 구현가능하지만, 선형시간이 소요되기 때문에, 본질적인 큐의 구조와 다르다

환형 큐

Front와 Rear가 이어져있는 Queue

• 환형 큐는 js에서 사용되는 경우가 많지는 않다.

 

7-b. 실습

• 💻프린터 문제 큐를 이용하여 풀어보기
문제이해
• location에 해당하는 문서가 몇번째로 인쇄되는지 구하는 문제
• 처음 로케이션이 2였다는 것을 어떻게 나중에 보장할 것인가 처리가 핵심
• idx와 중요도를 묶어서 자료형을 바꿔줌 properties: [2,1,3,2] => [[0,2],[1,1],[2,3],[3,2]]
• 현재 인쇄된 문서수(order)로 관리
풀이방법
• (pre) priorities를 [ [중요도, idx], [1,1], [3,2], [2,3] ] 로 파싱
• 맨 앞 문서 추출 [2,0]
• 나머지와 중요도 비교 2 vs 1, 3, 2 , isMostImportant()
• 1) 제일 중요하다면 문서 인쇄하고, 인쇄순서(order) 1증가
• 재귀탈출 만약 현재 인쇄순서(order)가 target위치(location)가 일치한다면 order리턴!
• 2) 제일 중요하지 않다면 제일 뒤로 이동 [ [1,1], [3,2], [2,3], [2,0] ]
• 재귀를 통한 반복 실행

function solution(priorities, location) {
let order = 0;
priorities = priorities.map((p,i)=>[p,i])

function isMostImportant(p, pList){
    pList = pList.map(p => p[0])
    return p >= Math.max(...pList);
}
// 재귀로 풀기
function print(pList){
    let [p, l] = pList.shift()
    if(isMostImportant(p, pList)){
        order++
        if(l === location) return order
    } else {
        pList.push([p,l])
    }
    return print(pList)
}
return print(priorities)
}

 

8. 해시 테이블

키와 값을 받아, 키를 해싱하여 나온 index에 값을 저장하는 선형 자료구조

입력받은 값을 특정 범위 내 숫자로 변경하는 함수

해시함수의 결과가 동일하여 저장공간이 겹치는 상황

• 학생부 사례
• 연결리스트 사용시, 학생 정보 탐색 시 O(n) 걸림.
• 배열 사용시, 인덱스를 모를 경우 탐색에 O(n)이 걸림.
• 해시테이블 사용 시 이름을 키로 하여, O(1)로 탐색, 삽입, 삭제 가능

• 배열을 통한 사용

const table = [];
table["key1"] = 100;
table["key2"] = "남자";

table["key1"] // 100

• 객체를 통한 사용 (정석)

const table = {};
table["key1"] = 100;
table["key2"] = "남자";

table["key1"] // 100

• Map을 통한 사용 (key값으로 문자열 이외 타입도 가능)
• 순회와 메소드 사용의 이점

const table = new Map();
table.set("key1", 100);
table.set("key2","남자")

table.get("key1") // 100

table.set({a: 1}, "Object 키도가능");
table.keys()
table.values();
table.clear();

• Set을 통한 사용 (key와 value를 같은 값으로 저장)

그래프

정점(node)과 정점 사이를 연결하는 간선(edge)으로 이루어진 비선형 자료구조

구현

인접행렬을 통한 구현

• 정점의 크기 만큼 2차원 배열을 초기화

• 시작(행), 도착(열)으로 연결

인접 리스트를 통한 구현

• 정점의 수만큼 배열을 만들고, 연결된 노드를 배열에 넣어준다