인프런 워밍업 클럽 스터디 2기 CS 1주차 발자국
운영체제
섹션 1
- 기초
운영체제는 개인용 컴퓨터나 대형 컴퓨터, 스마트폰, 임베디드 등에 들어간다.
컴퓨터는 운영체제가 있어야 동작하는가 - NO
하지만 운영체제가 없으면 한가지 기능만 가능할 뿐 다양한 기능을 사용 불가능하다.
옛날 전화기는 전화만 가능했지만 지금은 스마트폰의 운영체제를 통해 통화를 비롯해 다양한 기능을 사용 가능하다.
- 운영체제가 하는 일
프로세스 관리 -> 만약 하지 않는다면 하나의 프로세스가 CPU를 혼자 먹어서 다른 프로세스가 동작하지 않을 것이다
메모리 관리 ->모든 프로그램은 메모리에 올라와서 동작하는데 다양한 방법으로 메모리를 관리한다
하드웨어 관리 -> 운영체제가 판단하여 적절한 위치에 사용자의 프로그램을 저장한다
파일 시스템 관리 -> 파일을 효울적으로 관리해준다
- 운영체제의 역사
1940 -> 애니악
1950 초 -> 직접회로가 개발되었다, 펀치카드로 프로그래밍하여 넣으면 라인프린터로 출력되었다.
1950 중후반 -> 50년대 초의 인간의 프로그래밍 과정이 너무 오래 걸려서 싱글스트림 배치시스템이 개발되었다.
1960 -> 앞선 방법의 한계가 해결되었다, 시분할 시스템을 사용하였다, UNIX가 개발되었다.
ㄴ허나 시분할 시스템으로 인해 메모리 침범 문제가 생겼다.
1970 이후 -> 개인용 컴퓨터의 시대, 애플의 매킨토시와 마이크로소프트의 MS-DOS가 많이 사용되었다
ㄴ매킨토시는 GUI의 적용으로 인기를 끌었다
- 운영체제의 구조
핵심은 커널이다, 사용자는 인터페이스(GUI,CLI)를 통해 커널에 접근한다.
GUI : 그래픽으로 된 인터페이스
CLI : 유닉스나 리눅스가 지원하는 인터페이스
app은 시스템 콜을 통해 부른다, 시스템 콜 없이 불러져서 어플리케이션이 맘대로 저장소에 저장하면 중요한 데이터를 덮어쓰거나 할 수도 있기 때문에 시스템 콜이 필요하다. 시스템 콜은 write를 통해 저장하는데 자동으로 빈 공간에 저장하는 역할을 한다.
하드웨어와 커널의 인터페이스로는 드라이버를 사용한다.
운영체제는 다양한 하드웨어를 사용할 수 있어야 하는데 운영체제에 모든 하드웨어에 맞는 프로그램을 가지고 있기는 어려워서 제조사에서 드라이버를 제공하는 편이다.
- 컴퓨터 하드웨어와 구조
현대의 컴퓨터는 폰 노이만 구조를 하고있다. 애니악 때의 방식이 불편하다고 생각하여 이를 해결하기 위해 CPU와 메모리를 두고 버스로 연결한다.
프로그램을 작동하려면 메모리에 올려야 하는데 프로그램을 메모리에 내장했다고 해서 프로그램 내장 방식이라고 한다.
메인보드 -> 메인보드는 다른 하드웨어를 연결하는 역할
CPU -> 중앙처리장치로 불리며 산술논리연상장치, 제어 장치, 레지스터로 이루어져있다.
메모리 종류 -> RAM과 ROM으로 나누어지는데 RAM은 전력이 끊기면 저장된 값을 잃어서 메인 메모리로 사용된다. ROM은 전력이 끊겨도 값이 사라지지 않아서 부팅과 관련된 바이오스를 저장하는데 주로 쓰인다.
- 컴퓨터의 부팅과정
전원버튼을 통해 전력이 들어가면 바이오스가 켜진다. (바이오스는 주요 하드웨어를 체크한다)
이상 없을 시 부트로더를 가져와 RAM으로 실행한다.
운영체제를 모니터로 불러오고 우리가 아는 바탕화면이 나온다.
- 인터럽트
CPU는 입출력을 하려고 하면 입출력 관리자에게 명령을 내린다.
CPU는 스스로 입출력을 하지 않기 때문에 관리자에게 지속적으로 확인을 한다.
앞선 방식을 폴링 방식이라고 한다.
폴링 방식은 너무 자주 신호를 보내서 성능이 좋지 않다.
이런 단점을 해결한 것이 인터럽트이다.
CPU는 입출력 신호를 보내고 다른 일을 한다, 만약 입출력관리자에게 신호가 온다면 ISR을 실행시킨다.
ISR은 특정 인터럽트가 들어오면 그 인터럽트를 해결하는 함수이다.
인터럽트는 2개의 방식으로 나누어진다
하드웨어 방식 : 앞서 설명한 입출력 같은 인터럽트
소프트웨어 방식 : 사용자 프로그램에서 발생한 인터럽트 (유효하지 않은 접근이나 0으로 나누기 등...)
섹션 2
- 프로그램과 프로세스
프로그램 : 저장장치에 저장된 명령문의 집합체(app등으로 불리고 .exe의 모양을 가지고 있다)
프로세스 : 실행중인 프로그램(하드디스크에 있는 앱이 메모리로 가서 작동되면 그것이 프로세스이다)
차이점 : 프로그램은 그저 명령문의 집합체인 수동적이 존재이고 프로세스는 메모리에서 CPU도 사용하고 입출력도 하는 능동적인 존재이다.
프로세스의 구조는 code,data,stack,heap으로 이루어져 있다.
c언어의 컴파일 과정
파일 -> 전처리기 -> .i로 변경 -> 컴파일러 -> .s로 변경 -> 어셈블러로 변경 -> .o로 변경 -> 링커 -> .exe로 변경
위 과정을 걸쳐 exe파일을 더블클릭하면 메모리로 올라가고 운영체제가 관리를 한다.
- 멀티프로그래밍과 멀티프로세싱
유니프로그래밍 : 메모리에 오직 하나의 프로세스가 올라온 상황
멀티프로그래밍 : 메모리에 여러개의 프로세스가 올라온 상황
멀티프로세싱 : CPU가 여러 개의 프로세스를 처리하는 것을 말한다
현대에는 멀티프로그래밍과 멀티프로세싱이 있다.
옛날에는 메모리의 크기가 작아서 멀티프로그래밍이 불가능해서 유니프로그래밍으로 멀티프로세싱을 했다.
유니프로그래밍(옛날) : 메모리에 프로그램 올리기 -> 실행 -> 저장장치에 상태 저장하고 넣기 -> 다른 프로그램 메모리에 두기 -> 새로 가져온 프로그램 실행하기(프로그램을 메모리와 저장장치 사이로 옮기는 것을 스와핑이라고 한다)
- PCB(Process Control Block)
운영체제는 여러개의 프로세스를 알고리즘에 따라 실행시켜야 한다.
프로세스가 만들어지면 해당 프로세스의 정보를 가지고 있는 PCB를 만들고 저장한다.(연결리스트 자료구조의 형이다)
운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거한다.
구조 : 프로세스 구조, 프로세스 ID, 프로그램 카운터, 레지스터 정보 등....
- 프로세스 상태
사용자가 프로그램을 실행시키면 메모리에 올라가면서 프로세스가 생성된다.
운영체제가 프로세스를 관리하기 위해 프로세스 상태라는 것이 존재한다.
생성상태 : PCB를 생성하고 메모리에 프로그램 적재를 요청
준비상태 : 적재승인 시 적재를 기다리고 있는 상태
대기상태 : 프로세스가 입출력 요청을 할 시 입출력이 올 때 까지 대기상태로 변환, 입출력이 끝날 시 준비상태로 이동
실행상태 : 실행상태에 있는 프로세스의 수는 CPU의 개수와 같다.(부여된 시간만큼만 CPU사용 가능, 시간이 끝날 시 준비상태로 변함)
완료상태 : 프로세스가 종료된 상태
- 콘텍스트 스위칭
시분할 처리 중 다른 프로세스를 실행하기 위해 현재 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 바꾸는 작업
콘텍스트 스위칭이 일어나면 PCB의 내용이 변경된다.
작업중이었던 내용을 PCB에 저장하고 다음 프로세스의 PCB내용을 토대로 CPU의 상태를 바꾼다.
발생 이유는 다양하지만 인터럽트나 CPU점유시간이 끝났을 때 일어난다.
- 프로세스 생성과 종료
프로세스가 생성될때의 가정은 이러하다.
exe파일 더블클릭
운영체제가 프로그램의 코드영역과 데이터영역을 로드하고 빈 스택과 빈 힙을 만들어 공간을 확보한다.
PCB를 만들어서 값을 초기화한다.
위 방법은 부팅될때 1번만 실행되고 그 뒤로는 0번 프로세스(1~3번 과정에서 만들어진 프로세스)를 복사하여 사용한다.
복사하여 생성되는 프로세스는 자식 프로세스라고 하며 반대로는 부모 프로세스라고 한다.
주로 부모 프로세스가 자식프로세스에게 시작 신호를 보내고 자식이 종료 신호를 보내면 부모 프로세스가 자식 프로세스를 종료시킨다.
하지만 부모 프로세스가 먼저 사라지거나 자식프로세스가 종료 신호를 보내지 못하고 사라지면 종료되지 못하고 남아있는 좀비 프로세스가 생긴다. 이러한 프로세스는 컴퓨터의 성능 저하를 유발하나 컴퓨터를 껐다가 키면은 사라진다.
- 쓰레드
운영체제의 작업 처리 단위는 프로세스이다.
사용자가 운영체제에게 작업을 요구하면 그만큼 프로세스의 수가 늘어난다.
프로세스가 생성되는 PCB가 생성되고 코드,데이터,스택,힙 등의 영역이 생긴다.
만약 웹브라우저를 20개 틀면 20번 복제되고 메모리의 사용량이 너무 많아진다.
앞선 문제를 해결하기 위해 쓰레드를 고안해냈다.
쓰레드는 프로세스 안에 존재하며 여러개가 있을 수 있다.
프로세스 내에 쓰레드들은 PCB, 코드, 데이터,힙 영역을 공유한다.
쓰레드를 관리하기 위해 ID를 부여하고 TCB도 생겼다.
이렇게 되면 운영체제가 작업을 관리하는 단위는 쓰레드가 되었다.
이렇게 되면 탭을 생성할 때 최초생성은 프로세스가 생격나지만 탭을 추가하면 프로세스가 아닌 쓰레드가 추가된다.
프로세스와 쓰레드의 장단점
프로세스는 독립적이어서 하나가 문제가 생겨도 문제가 생기지 않는다.
허나 쓰레드는 예를 들어 힙 영역이 문제가 생기면 공유하는 모든 프로세스가 문제가 생긴다
--
프로세스는 모든 자원을 각각의 프로세스가 가지고 있어서 통신하려면 IPC통신을 사용해야 하는데 오버헤드가 크고 속도가 느리다.
반면 쓰레드는 다양한 자원을 공유해서 오버헤드가 굉장히 작다.
섹션 3
- CPU스케줄링 개요
프로그램을 실행하면 메모리에 프로세스가 생기고, 그 안에는 1개 이상의 쓰레드가 있다.
프로세스들은 CPU를 사용하기 위해서 운영체제의 명령을 기다린다.
운영체제는 모든 프로세스들에게 CPU 할당/해제하는데 이를 CPU스케줄링이라고 한다.
오늘날 운영체제는 프로세스들을 시분할 처리방식으로 CPU를 할당한다.
- 다중큐
프로세스들은 준비 상태에 있다가 운영체제의 명령으로 실행 상태가 된다, 그 후 지정된 시간이 끝나면 준비 상태, I/O가 필요하면 대기 상태, 끝나면 완료 상태로 변한다.
이 중 준비와 대기는 큐 자료구도로 작동된다.
작동은 선입선출구조이다.(FIFO)
운영체제는 준비상태에 프로세스가 있으면 다양한 프로세스 중 우선순위를 보고 그에 맞는 '준비 큐'에 넣는다.
또한 대기상태에 있는 프로세스는 동류에 따라 다른 큐에 넣는데 예를 들어 하드디스크를 사용하는 경우에는 HDD큐에 들어가고 키보드를 사용하면 키보드 큐에 넣는다.
(자세히는 프로세스 그 자체보다는 PCB가 들어간다)
- 스케줄링 목표
리소스 사용률
CPU 혹은 I/O디바이스 사용률을 높이는 것이 목표이다.
오버헤드 최소화
공평성
처리량 증가
대기시간 감소
응답시간
앞선 목표들을 다 맞추기는 힘들다.
그 이유는 목표가 서로 상반되는 경우도 있기 때문이다.
- FIFO
CPU스케줄링 알고리즘 중 하나.
가장 정석적인 알고리즘으로 먼저 들어온 순서대로 CPU를 할당받는 방식이다.
마트의 계산대와 같은 느낌이다.
장점 : 단순하고 직관적
단점 : 순서가 가장 중요하기에 비효율적인 상황이 생길 수 있다(예시 I/O작업)
스케줄링의 성능은 평균 대기시간으로 정한다.
현대 운영체제에서는 잘 쓰이지 않고 일괄처리시스템에 쓰인다.
자료구조와 알고리즘
섹션 1
- 하고 싶은 말
알고리즘은 무지성으로 따라하거나 암기하는 것이 아닌 이해하는 것이 문제를 해결 할 때 가장 좋다.
- 자료구조와 알고리즘이란
자료구조
자료구조란 테이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냅니다.
가장 단순한 자료구조는 변수이다.
그 외에도 사용했었던 자료구조는 배열이 있다.
a = 87
b = 70
c = 100
average = (a+b+c)/3arr = [87,70,100]
average = 0
for i in arr:
average+=i
average/=len(average)위의 코드 예시처럼 자료구조 간의 사용 방법과 저장된 모양도 다르다
알고리즘
어떤 문제를 해결하기 위한 확실한 방법
예를 들어 평균을 구하는 문제를 풀 때는 알고리즘이 필요하다
- 시간 복잡도
보통 시간이 가장 적게 걸리는 알고리즘을 좋은 알고리즘이라고 한다.
보통 반복문이 시간에 영향을 미쳐서 반복문으로 성능을 확인한다.
예를 들어 5개의 리스트에서 특정 숫자를 찾을 때 처음부터 찾는다면 최악의 경우 리스트의 길이만큼 체크한다.
이런 경우를 O(n)이라고 한다.
상수시간 알고리즘은 O(1)로 표현한다.(문제를 해결할 때 입력과 상관없이 계산량이 같을 때 이다)
그 외에도 O(nlogn), O(n^2), O(2^n)등이 있다.
섹션 2
- 배열
일반전인 배열
배열을 선언하면 운영체제가 그 크기만큼 빈 공간을 찾아서 순서대로 값을 선언한다.
운영체제는 배열의 첫번쨰 주소만 저장한다
운영체제는 배열의 시작 주소를 기준으로 가져온다(O(1)의 성능)
데이터의 삽입,삭제는 느리다
만약 할당된 공간의 크기를 넘기면 운영체제는 새로 빈 공간을 찾는다.
물론 처음부터 큰 크기의 배열을 만들면 편하겠지만 메모리 사용량이 너무 크다
JS식 배열
js배열은 불연속적으로 할당하고 내부적으로 연결한다
기능상 배열이라고 부를 수 있다
- 연결리스트
연결리스트 - 개념
개발자들은 배열의 단점을 해결하기 위해 연결리스트를 만들었다
연결리스트는 노드로 이루어져있다
노드는 다음 노드의 주소를 알고있다. 즉, 처음 노드의 주소만 알면 모든 노드를 찾을 수 있는 것이다
장점
연결리스트는 새로 삽입하면 주소만 바뀌주면 되서 문제가 없다
또한 삭제도 노드를 지우고 주소를 바꾸면 된다
단점
배열은 데이터 접근이 O(1)의 성능으로 아주 빠르다. 허나, 연결리스트는 1번부터 천천히 가야해서 O(n)의 성능이다.
선택
참조가 메인이라면 배열
삽입&삭제가 메인이라면 연결리스트
연결리스트 - 구현
import { Node, LinkedList } from "./LinkedList.mjs";
let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
node1.next = node2;
node2.next = node3;
console.log(node1.data);
console.log(node1.next.data);
console.log(node1.next.next.data);
let list = new LinkedList();
console.log("========= insertAt() 다섯 번 호출 ==========");
list.insertAt(0, 0);
list.insertAt(1, 1);
list.insertAt(2, 2);
list.insertAt(3, 3);
list.insertAt(4, 4);
list.printAll();
console.log("======= clear() 호출==========");
list.clear();
list.printAll();
console.log("======= insertLast() 호출==========");
list.inserLast(0);
list.inserLast(1);
list.inserLast(2);
list.printAll();
console.log("======= deleteAt() 호출==========");
list.deleteAt(0);
list.printAll();
list.deleteAt(1);
list.printAll();
console.log("======= deleteLast() 호출==========");
list.inserLast(5);
list.deleteLast();
list.deleteLast();
list.printAll();
console.log("======= getNodeAt() 호출==========");
list.inserLast(1);
list.inserLast(2);
list.inserLast(3);
list.inserLast(4);
list.inserLast(5);
let secondNode = list.getNodeAt(2);
console.log(secondNode);class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.count = 0;
}
printAll() {
let currentNode = this.head;
let text = "[";
while (currentNode != null) {
text += currentNode.data;
currentNode = currentNode.next;
if (currentNode != null) {
text += ", ";
}
}
text += "]";
console.log(text);
}
clear() {
this.head = null;
this.count = 0;
}
insertAt(index, data) {
if (index > this.count || index < 0) {
throw new Error("범위를 넘어갔습니다.");
}
let newNode = new Node(data);
if (index == 0) {
newNode.next = this.head;
this.head = newNode;
} else {
let currentNode = this.head;
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
newNode.next = currentNode.next;
currentNode.next = newNode;
}
this.count++;
}
inserLast(data) {
this.insertAt(this.count, data);
}
deleteAt(index) {
if (index >= this.count || index < 0) {
throw new Error("제거할 수 없습니다.");
}
let currentNode = this.head;
if (index == 0) {
let deleteNode = this.head;
this.head = this.head.next;
this.count--;
return deleteNode;
} else {
for (let i = 0; i < index - 1; i++) {
currentNode = current.next;
}
let deleteNode = currentNode.next;
currentNode.next = currentNode.next.next;
this.count--;
return deleteNode;
}
}
deleteLast() {
return this.deleteAt(this.count - 1);
}
getNodeAt(index) {
if (index >= this.count || index < 0) {
throw new Error("범위를 넘어갔습니다.");
}
let currentNode = this.head;
for (let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
}
export { Node, LinkedList };
-스택
스택 - 개념
스택이란 단순한 규칙을 가지고 있는 배열
작동 구조는 FILO(First In Last Out) (선입후출)
예시 : 엘리베이터에 타는 사람들 등
구현의 개념
삽입은 오직 첫번째에(head 위치)
삭제도 오직 첫번째만(head 위치)
스택 - 구현
import { Stack } from "./stack.mjs";
let stack = new Stack();
console.log("===첫 번째 출력====");
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
console.log(stack.pop().data);
console.log(stack.pop().data);
console.log(stack.pop().data);
console.log(stack.pop().data);
console.log("===두 번째 출력====");
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
console.log(stack.peek().data);
stack.pop();
console.log(stack.peek().data);
console.log(`isEmpty: ${stack.isEmpty()}`);
stack.pop();
stack.pop();
stack.pop();
console.log(`isEmpty: ${stack.isEmpty()}`);
console.log(stack.pop());
import { LinkedList } from "./LinkedList.mjs";
class Stack {
constructor() {
this.list = new LinkedList();
}
push(data) {
this.list.insertAt(0, data);
}
pop() {
try {
return this.list.deleteAt(0);
} catch (e) {
return null;
}
}
peek() {
return this.list.getNodeAt(0);
}
isEmpty() {
return this.list.count == 0;
}
}
export { Stack };
- 큐
큐 - 개념
리스트의 일종
선입선출, FIFO
운영체게가 프로세스를 큐에 넣고 CPU가 들어온 순서대로 실행
구현의 개념
삽입은 head에
삭제는 tail에(tail : 마지막 노드 위치)
tail삭제 후 이전 노드를 tail로 지정해야하기 때문에 이중연결리스트를 사용
큐 - 구현
class Node {
constructor(data, next = null, prev = null) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.count = 0;
}
printAll() {
let currentNode = this.head;
let text = "[";
while (currentNode != null) {
text += currentNode.data;
currentNode = currentNode.next;
if (currentNode != null) {
text += ", ";
}
}
text += "]";
console.log(text);
}
clear() {
this.head = null;
this.count = 0;
}
insertAt(index, data) {
if (index > this.count || index < 0) {
throw new Error("범위를 넘어갔습니다.");
}
let newNode = new Node(data);
if (index == 0) {
newNode.next = this.head;
if (this.head != null) {
this.head.prev = newNode;
}
this.head = newNode;
} else if (index == this.count) {
newNode.next = null;
newNode.prev = this.tail;
this.tail.next = newNode;
} else {
let currentNode = this.head;
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
newNode.next = currentNode.next;
newNode.prev = currentNode;
currentNode.next = newNode;
newNode.next.prev = newNode;
}
if (newNode.next == null) {
this.tail = newNode;
}
this.count++;
}
inserLast(data) {
this.insertAt(this.count, data);
}
deleteAt(index) {
if (index >= this.count || index < 0) {
throw new Error("제거할 수 없습니다.");
}
let currentNode = this.head;
if (index == 0) {
let deleteNode = this.head;
if (this.head.next == null) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
this.count--;
return deleteNode;
} else if (index == this.count - 1) {
let deleteNode = this.tail;
this.tail.prev.next = null;
this.tail = this.tail.prev;
this.count--;
return deleteNode;
} else {
for (let i = 0; i < index - 1; i++) {
currentNode = current.next;
}
let deleteNode = currentNode.next;
currentNode.next = currentNode.next.next;
currentNode.next.prev = currentNode;
this.count--;
return deleteNode;
}
}
deleteLast() {
return this.deleteAt(this.count - 1);
}
getNodeAt(index) {
if (index >= this.count || index < 0) {
throw new Error("범위를 넘어갔습니다.");
}
let currentNode = this.head;
for (let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
}
export { Node, DoublyLinkedList };import { DoublyLinkedList } from "./DoublyLinkedList.mjs";
class Queue {
constructor() {
this.list = new DoublyLinkedList();
}
enqueue(data) {
this.list.insertAt(0, data);
}
dequeue() {
try {
return this.list.deleteLast();
} catch (e) {
return null;
}
}
front() {
return this.list.tail;
}
isEmpty() {
return this.list.count == 0;
}
}
export { Queue };import { Queue } from "./Queue.mjs";
let queue = new Queue();
console.log("====== enqueue() 세 번 호출==========");
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.front());
console.log("===== dequeue() 네 번 호출 ======");
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(`isEmpty: ${queue.isEmpty()}`);
- 덱
덱 - 개념
덱은 삽입삭제를 head와 tail에서 자유롭게 하는 자료구조이다.
덱을 이용하면 스택과 큐를 다 구현할 수 있다.
덱 - 구현
import { DoublyLinkedList } from "./DoublyLinkedList.mjs";
class Deque {
constructor() {
this.list = new DoublyLinkedList();
}
printAll() {
this.list.printAll();
}
addFirst(data) {
this.list.insertAt(0, data);
}
removeFirst() {
return this.list.deleteAt(0);
}
addLast(data) {
this.list.insertAt(this.list.count, data);
}
removeLast() {
return this.list.deleteLast();
}
isEmpty() {
return this.list.count == 0;
}
}
export { Deque };import { Deque } from "./Deque.mjs";
let deque = new Deque();
console.log("==== addFirst =====");
console.log(deque.isEmpty());
deque.addFirst(1);
deque.addFirst(2);
deque.addFirst(3);
deque.addFirst(4);
deque.addFirst(5);
deque.printAll();
console.log(deque.isEmpty());
console.log("\n");
console.log("======== removeFirst =========");
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();
console.log(deque.isEmpty());
console.log("\n");
console.log("========= addList========");
deque.addLast(1);
deque.addLast(2);
deque.addLast(3);
deque.addLast(4);
deque.addLast(5);
deque.printAll();
console.log(deque.isEmpty());
console.log("\n");
console.log("=====removeLast====");
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();
console.log(deque.isEmpty());
- 해시테이블
해시테이블 - 개념
해시테이블은 언어마다 여러가지 이름으로 불린다
해시
맵
해시맵
딕셔너리
이름처러 해시+테이블인 자료구조이다
해시테이블은 key 와 value로 이루어져있고 삽입, 수정 등이 O(1)의 시간이 걸린다.
장점
빠른 데이터 탐색, 삽입, 삭제 등..
단점
공간의 효율성이 좋지 않다
좋은 해시 함수의 구현이 필수적
해시테이블 - 구현
import { DoublyLinkedList } from "./DoublyLinkedList.mjs";
class HashData {
constructor(key, value) {
this.key = key;
this.value = value;
}
}
class HashTable {
constructor() {
this.arr = [];
for (let i = 0; i < 10; i++) {
this.arr[i] = new DoublyLinkedList();
}
}
hashFunction(number) {
return number % 10;
}
set(key, value) {
this.arr[this.hashFunction(key)].insertAt(0, new HashData(key, value));
}
get(key) {
let currentNode = this.arr[this.hashFunction(key)].head;
while (currentNode != null) {
if (currentNode.data.key == key) {
return currentNode.data.value;
}
currentNode = currentNode.next;
}
return null;
}
remove(key) {
let list = this.arr[this.hashFunction(key)];
let currentNode = list.head;
let deletedIndex = 0;
while (currentNode != null) {
if (currentNode.data.key == key) {
return list.deleteAt(deletedIndex);
}
currentNode = currentNode.next;
deletedIndex++;
}
return null;
}
}
export { HashTable };import { HashTable } from "./HashTable.mjs";
let hashTable = new HashTable();
hashTable.set(1, "이운재");
hashTable.set(4, "최진철");
hashTable.set(20, "홍명보");
hashTable.set(6, "유상철");
hashTable.set(22, "송종국");
hashTable.set(21, "박지성");
hashTable.set(5, "김남일");
hashTable.set(10, "이영표");
hashTable.set(8, "최태욱");
hashTable.set(9, "설기현");
hashTable.set(14, "이천수");
console.log(hashTable.get(1));
hashTable.remove(1);
console.log(hashTable.get(1));
console.log(hashTable.get(21));
- 셋
셋 - 개념
셋은 오직 데이터의 중복을 허용하지 않는 자료구조
헤시 셋이라고도 불린다
셋 - 구현
import { HashTable } from "./HashTable.mjs";
class HashSet {
constructor() {
this.HashTable = new HashTable();
}
add(data) {
if (this.HashTable.get(data) == null) {
this.HashTable.set(data, -1);
}
}
isContain(data) {
return this.HashTable.get(data) != null;
}
remove(data) {
this.HashTable.remove(data);
}
clear() {
for (let i = 0; i < this.HashTable.arr.length; i++) {
this.HashTable.arr[i].clear();
}
}
isEmpty() {
let empty = true;
for (let i = 0; i < this.HashTable.arr.length; i++) {
if (this.HashTable.arr[i].count > 0) {
empty = false;
break;
}
}
return empty;
}
printAll() {
for (let i = 0; i < this.HashTable.arr.length; i++) {
let currentNode = this.HashTable.arr[i].head;
while (currentNode != null) {
console.log(currentNode.data.key);
currentNode = currentNode.next;
}
}
}
}
export { HashSet };import { HashSet } from "./HashSet.mjs";
let hashSet = new HashSet();
console.log(hashSet.isEmpty());
console.log("=========add=========");
hashSet.add(1);
hashSet.add(1);
hashSet.add(123);
hashSet.add(512);
hashSet.printAll();
console.log(hashSet.isEmpty());
console.log("=========check=========");
console.log(hashSet.isContain(1));
console.log("=========remove=========");
hashSet.remove(1);
hashSet.printAll();
console.log(hashSet.isEmpty());
console.log("=========check2=========");
console.log(hashSet.isContain(1));
console.log("=========clear=========");
hashSet.clear();
hashSet.printAll();
console.log(hashSet.isEmpty());댓글을 작성해보세요.
