[인프런 워밍업클럽 CS 2기] 1주차 발자국
자료구조와 알고리즘
자료구조 : 데이터를 효율적으로 저장하고 관리하는 방법. 배열, 연결리스트, 스택, 큐, 트리, 그래프 등이 있다.
알고리즘 : 어떤 문제를 해결하기 위해 정해진 일련의 절차나 규칙을 의미하며, 주어진 입력에 대해 결과를 도출하는 과정이다.
시간 복잡도 : 알고리즘이 수행되는 데 걸리는 시간을 입력 크기에 대한 함수로 표현한 것.
주로 O(1), O(n), O(n²) 등의 표기법으로 나타낸다.
배열 : 고정된 크기의 연속된 메모리 공간에 데이터를 저장하는 자료구조. 인덱스를 통해 빠르게 접근할 수 있지만 크기가 고정되어 있으며 중간에 데이터를 삽입하거나 삭제하는 데는 비효율적이다.
시간 복잡도: 접근 O(1), 삽입/삭제 O(n)
연결 리스트(Linked List) :
각 노드가 데이터와 다음 노드의 주소를 가지는 동적 자료구조. 삽입과 삭제가 용이하지만,
특정 위치에 접근하려면 순차적으로 접근해야 하므로 시간이 더 걸린다.
시간 복잡도: 접근 O(n), 삽입/삭제 O(1)
export class Node{
constructor(data, next = null){
this.data = data;
this.next = next;
}
}
// * 연결 리스트 추상 자료형
// 1. 모든 데이터 출력 -> printAll();
// 2. 모든 데이터 제거 -> clear();
// 3. 원하는 인덱스에 데이터를 삽입 -> insertAt(index, data);
// 4. 마지막 데이터 뒤에 데이터를 삽입 -> insertLast(data);
// 5. 원하는 인덱스에 데이터를 삭제 -> deleteAt(index);
// 6. 마지막 데이터를 제거 -> deleteLast();
// 7. 원하는 인덱스에 있는 데이터 읽기 -> getNodeAt(index);
export class LinkedList {
constructor(){
// 연결 리스트의 시작 Node를 가리킨다.
this.head = null;
// 총 저장된 Node의 수
this.count = 0;
}
/**
* 원하는 인덱스에 데이터를 삽입
* @param {number} index - 삽입할 위치 index
* @param {any} data - 삽입할 데이터
*/
insertAt(index, data){
// 예외 처리
if(index > this.count || index < 0) throw new Error('범위를 넘어갔습니다.');
// 새로운 Node 생성
let newNode = new Node(data);
if(index === 0){
// 리스트의 가장 앞부분에 삽입할 경우
// 1. 생성된 Node의 next가 head를 가리키도록 설정
newNode.next = this.head;
// 2. 생성된 Node를 head로 설정
this.head = newNode;
}else{
// 앞부분 삽입을 제외한 원하는 인덱스에 삽입할 경우
// head에서 부터 시작하기 때문에 head로 초기화
let currentNode = this.head;
// 목표 인덱스 바로 전까지 next를 이용해 currentNode를 이동시킨다.
for(let i=0; i<index -1; i++){
currentNode = currentNode.next;
}
// 1. 새로운 Node가 currentNode의 next Node를 가리키도록 설정
newNode.next = currentNode.next;
// 2. currentNode가 새로운 Node를 가리키도록 설정
currentNode.next = newNode
}
// 새로운 Node가 삽입되었으니 count를 증가
this.count++;
}
/**
* 모든 데이터 출력
* @returns {string} - 모든 Node의 data를 하나의 문자열에 담아 반환
*/
printAll(){
let currentNode = this.head;
let text = '['
while(currentNode){
text += currentNode.data
currentNode = currentNode.next;
if(currentNode) text += ', ';
}
text += ']';
console.log(text);
return text;
}
/**
* 모든 데이터 제거
*/
clear(){
this.head = null; // head 초기화
this.count = 0; // count 초기화
}
/**
* 마지막 데이터 뒤에 데이터를 삽입
* @param {any} data - 삽입할 데이터
*/
insertLast(data){
this.insertAt(this.count, data);
}
/**
* 원하는 인덱스에 데이터를 삭제
* @param {number} index - 제거할 위치 index
* @return {{data: number, next: {data: number, next: any} | null}} - 제거된 노드의 데이터와 그 다음 노드에 대한 정보.
*/
deleteAt(index){
// 예외 처리
if(index >= this.count || index < 0) throw new Error('제거할 수 없습니다.');
let currentNode = this.head;
if(index === 0){
// 리스트의 가장 앞부분에 제거할 경우
// 반환하기 위해 삭제된 Node를 저장
const deleteNode = this.head;
// head를 다음 Node인 head.next로 설정
this.head = this.head.next;
// 제거했으므로 count를 내린다.
this.count--;
// 삭제한 Node 반환
return deleteNode;
}else{
// 리스트의 가장 앞부분을 제외한 위치를 제거할 경우
// 제거할 Node 이전 Node까지 순회해 제거할 Node의 이전 Node를 가리키게 한다.
for(let i=0; i<index -1; i++){
currentNode = currentNode.next;
}
// currentNode.next가 참조하고 있는 다음 Node 즉, 제거해야 할 Node를 저장
let deleteNode = currentNode.next;
// 제거할 Node의 next Node를 가리키게 한다.
currentNode.next = currentNode.next.next;
// 제거했으므로 count를 내린다.
this.count--;
// 삭제한 Node 반환
return deleteNode;
}
}
/**
* 마지막 데이터를 제거
* @return {{data: number, next: {data: number, next: any} | null}} - 제거된 노드의 데이터와 그 다음 노드에 대한 정보.
*/
deleteLast(){
return this.deleteAt(this.count - 1);
}
/**
* 원하는 인덱스에 있는 데이터 읽기
* @param {number} index - 읽고자하는 Node의 index
* @return {{data: number, next: any}} - 해당 Node 반환
*/
getNodeAt(index){
// 예외 처리
if(index >= this.count || index < 0) throw new Error('범위를 넘어갔습니다.');
let currentNode = this.head;
// currentNode가 해당 index까지 순회한다.
for(let i=0; i< index ; i++){
currentNode = currentNode.next;
}
// 최종적으로 이동한 Node를 반환
return currentNode;
}
}
스택(Stack) :
후입선출(LIFO: Last In, First Out) 방식의 자료구조. 마지막에 추가된 요소가 먼저 제거된다. 함수 호출, 되돌리기 기능 등에서 사용된다.
시간 복잡도: 접근/삽입/삭제 O(1)
import { LinkedList } from './../LinkedList/LinikedList.mjs';
// * 스택의 추상자료형
// 1. 데이터 삽입 -> push();
// 2. 데이터 제거 -> pop();
// 3. top에 있는 데이터 참조 -> peek();
// 4. 스택이 비었는지 체크 -> isEmpty();
export class Stack{
constructor(){
this.list = new LinkedList();
}
push(data){
this.list.insertAt(0, data);
}
pop(){
try {
return this.list.deleteAt(0);
} catch (error) {
return null;
}
}
peek(){
return this.list.getNodeAt(0);
}
isEmpty(){
return this.list.count === 0;
}
}
큐 (Queue):
선입선출(FIFO: First In, First Out) 방식의 자료구조. 먼저 들어온 데이터가 먼저 처리된다. 대기열, 주문 처리 등 순차적으로 처리해야 할 때 사용된다.
시간 복잡도: 접근/삽입/삭제 O(1)
import { DoublyLinkedList } from "./DoublyLinkedList.mjs";
// * 기존에 구현한 Node에서 이전 Node도 가리킬 수 있도록 Node를 수정
// * 기존의 LinkedLst를 연결 리스트의 끝을 가리킬 수 있도록 수정 -> DoublyLinkedList
// * 큐의 추상자료형
// 1. 데이터 삽입 -> enqueue();
// 2. 데이터 제거 -> dequeue();
// 3. 데이터 참조 -> front();
// 4. 큐가 비었는지 확인 -> isEmpty();
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};
운영체제
폴링 방식 : 주기적으로 상태를 확인하는 방식.
인터럽트 : 외부나 내부에서 발생하는 사건이 CPU의 주의를 끌어 현재 작업을 중단하고 즉시 그 사건을 처리하도록 하는 메커니즘.
프로그램과 프로세스 :
프로그램: 실행되지 않은 상태의 정적 코드. 하드디스크 등에 저장된 명령어 집합.
프로세스: 실행 중인 프로그램. 운영체제에서 메모리와 CPU 등의 자원을 할당받아 실행되는 단위.
PCB : 프로세스 제어 블록으로, 운영체제가 프로세스를 관리하기 위한 정보(프로세스 상태, 프로그램 카운터, 메모리 정보 등)를 담고 있는 구조체.
프로세스 : 실행 중인 프로그램으로, CPU와 메모리 자원을 할당받아 동작하며 독립적인 실행 단위를 형성한다.
컨텍스트 스위칭: 하나의 프로세스나 스레드가 CPU에서 실행되다가 다른 프로세스로 전환될 때, 현재 프로세스의 상태를 저장하고 새로운 프로세스의 상태를 복구하는 과정.
답변 0