오늘은 기본적인 자료구조인 큐, 해시 테이블, 그래프를 공부했습니다 ! 사실 저는 아직 많은 자료구조를 접해보지 않았기 때문에 이제 슬슬 아직 써보지 않았던 자료구조들도 보이는 것 같습니다 ! 알고리즘과 자료구조는 기초 중의 기초라고 생각하고 더 열심히 학습하고 있습니다 ✏️
[1] - 큐
-
First In First Out 이라는 개념을 가진 선형 자료구조
-
Linear Queue와 Cirular Queue가 존재한다.
-
Array 또는 Linked List로 큐를 표현할 수 있다.
큐의 구현
-
array로 큐 구현
=> 보통 코딩테스트에서는 array로 구현한다 !
간혹 js에서 array의
shift()함수를 사용해 큐를 구현하는 경우가 있는데=> shift는 쓰지 말자 !
=> shift는 선형 시간 O(n)이 걸리기 때문에 큐에서 기대하는 로직이 구현되지 않음
- Linked List로 큐 구현
✏️ 큐 실습 예제
프로그래머스 42587번 프린터
-
queue를 직접 구현해줘야 하는 문제였다.
-
priorities들의
index까지 같이 queue에 넣고(queue.push[1, 0])나중에 pop할 때, pop된 요소의
index와location이 같다면 그때의count값을 return 해주면 된다.
[2] - 해시 테이블
📌 해시 테이블이란
사물함 같은 자료구조 !
해시 테이블은 한정된 배열 공간에 key를 index로 변환 하여 값들을 넣는다.
index는 어떻게 구할까 ?
- key와 value를 받아, key를 해싱(Hashing)하여 나온 index(bucket이라고 부름)에 값을 저장하는 자료구조이다.
- 삽입은
O(1)이며 key를 알고 있다면 삭제, 탐색 모두O(1)로 수행한다. - 서로 다른 key를 해싱해서 나온 index가 값이 같은 상황을 충돌이라고 한다.
해시 테이블의 사용
-
학생 정보를 관리하는 출석부 소프트웨어
=> 이름을 key로 하여 학생의 정보를 저장하면
ex) key :
박민우=> value :26, 남
JS에서 해시 테이블의 사용
array, object, set 으로도 사용가능하지만 보통 map을 사용한다.
map
- get과 set으로 접근
const table = new Map();
table.set("key", 100);
table.set("key2", "Hello");
console.log(table.get("key"));
const object = { a: 1 };
table.set(object, "A1"); // map은 object도 key로 사용 가능
console.log(table.get(object));
console.log(table.keys());
console.log(table.values());
table.clear()메서드
- map.size : Key-Value쌍의 데이터 수를 리턴
- map.set( key, value ) : Key, Value 데이터 삽입
- map.get( key ) : Key값을 통해 Value 데이터 조회
- map.delete( key ) : Key값으로 해당 데이터 제거
- map.has( key ) : 해당 Key값의 데이터가 있는지 true/false 리턴
- map.clear() : 모든 데이터 제거
- map.keys() : Key로만 이루어진 Iterator 객체 리턴
- map.values() : Value로만 이루어진 Iterator 객체 리턴
- map.entries() : [ Key, Value ] 배열로 이뤄진 Iterator 객체 리턴
✏️ 해시 테이블 실습 예제
단순한 구현 문제인데 고차함수를 적절히 사용할 수 있느냐가 중요한 문제 !
다시 풀어보기 !
[3] - 그래프
그래프란?
-
정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조
-
정점은 여러 개의 간선을 가질 수 있다.
-
방향 그래프와 무방향 그래프로 나눌 수 있다.
-
간선은 가중치를 가질 수 있다.
-
사이클이 발생할 수 있다.
무방향 그래프
- 간선으로 이어진 정점끼리는 양방향으로 이동이 가능
- (A, B)와 (B, A)는 같은 간선으로 취급된다.
방향 그래프
- 간선에 방향성이 존재하는 그래프
- 양방향으로 갈 수 있더라도 <A, B>와 <B, A>는 다른 간선으로 취급 된다.
전체 그래프의 연결상태에 따른 분류
-
연결 그래프
모든 정점이 서로 이동 가능
-
비연결 그래프
특정 정점이 다른 어느 정점으로도 갈 수 없는 그래프
-
완전 그래프
모든 정점끼리 연결된 상태의 그래프
-
사이클
그래프에서 순환이 되는 부분
그래프의 구현방법
- 인접 행렬
const graph = Array.from(
Array(5),
() => []
);
graph[0].push(1); // 0 => 1
graph[0].push(3); // 0 => 3
graph[1].push(2); // 1 => 2 - 인접 리스트
const graph = Array.from(
Array(5),
() => []
);
graph[0].push(1); // 0 => 1
graph[0].push(3); // 0 => 3
graph[1].push(2); // 1 => 2 ✏ 그래프 실습 예제
프로그래머스 85582번 가장 먼 노드
참고 및 출처
