블로그

최신순
인기순
좋아요순

운영체제

*이 내용은 인프런 그림으로 쉽게 배우는 운영체제를 수강하며 정리한 내용입니다. program과 process하드디스크등과 같은 저장장치에 저장된 명령문의 집합체를 말해.애플리케이션이나 앱이라고도 불리고 windows 운영체제에서는 .exe 의 모습을 하고있지.그럼 process는 뭘까?간단히 말하면 실행중인 프로그램이야.하드디스크에 저장된 프로그램이 메모리에 올라갔을 때 실행 중인 프로그램, 즉 프로세스라고 불려.프로그램은 수동적, 프로세스는 수동적인 존재라고 할 수 있어. process의 구조CodeDataHeap : 프로그래머가 동적으로 메모리를 할당하는데에 쓰인다. ( malloc, free )Stack컴파일 과정멀티프로그래밍과 멀티프로세싱유니프로그래밍 : 메모리에 오직 하나의 프로세스가 올라온 것 멀티프로그래밍 : 메모리에 여러 개의 프로세스가 올라온 것 멀티프로세싱 : CPU가 여러 개의 프로세스를 처리하는 것PCB (Process Control Block)프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고있는 PCB를 만들고 저장해.PCB들은 연결리스트라는 자료구조로 저장돼.운영체제는 프로세스가 종료되면 해당 프로세스의 PCB를 연결리스트에서 제거해.프로세스 상태실행상태에 있는 프로세스의수는 CPU의 개수만큼 입니다.대기상태프로세스가 입출력 요청을 하면 입출력이 완료될 때까지 기다리는 상태야.CPU에 비해 입출력작업은 상당히 느려.특정 프로세스가 입출력 요청을 하면 입출력이 완료될 때까지 CPU를 기다리게 하는건 굉장히 비효율적이야.대신 입출력 요청을 한 프로세스를 "대기상태"로 두고 다른 프로세스에게 CPU를 할당해그러다가 시간이 지나서 입출력 작업이 완료되면 "대기상태"에 있던 프로세스에게 CPU 할당 기회를 줘 컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 변경하는 작업이야.컨텍스트 스위칭이 일어날 때 PCB의 내용이 변경돼. 실행 중인 프로세스의 작업 내용을 PCB에 저장하고 실행될 기존 프로세스의 PCB의 내용대로 CPU가 다시 세팅돼.컨텍스트 스위칭이 일어날 때 PCB에 변경하는 값들로는 아래와 같아.운영체제에서 프로세스 A와 프로세스 B사 컨텍스트 스위칭을 하는 법을 알려줄게.먼저 CPU에서 프로세스 A를 실행해.시간이 지난 후 운영체제에서 CPU가 프로세스 A를 너무 오래 실행했다고 판단하면프로세스 A는 하던 일을 멈추고, 현재 CPU의 레지스터 값 등을 PCB A에 저장해.이제 PCB B를 참조해서 이전 프로세스 B의 상태로 CPU의 레지스터값을 설정해.여기에는 다음 실행할 명령어의 주소를 가지고있는 프로그램 카운터(PC)를 가지고있기 때문에 바로 프로세스 B의 명령어를 실행할 수 있어.프로세스 B가 점유시간동안 CPU를 사용하다가 점유시간이 다되면 운영체제는 다시 인터럽트를 발생시키는거지. 컨텍스트 스위칭은 CPU 점유시간이 다됐거나, I/O 요청이 발생하거나, 다른 종류의 인터럽트가 있을 때 등의 상황에서 발생해. 프로세스 생성과 종료일반적으로 프로세스가 생성될 때의 방법에 대해 설명할게..exe 파일을 더블클릭으로 실행하면 운영체제는 해당 프로그램의 코드영역과 데이터영역을 메모리에 로드하고 빈 스택과 빈 힙을 만들어 공간을 확보해.그리곤 이 프로세스를 관리하기 위한 PCB를 만들어서 값을 초기화해줘.지금 설명한 프로세스 생성과정은 운영체제가 부팅되고 0번 프로세스가 생성될 떄 딱 한번 실행돼.그리고나서 나머지 모든 프로세스는 새로 생성하지않고 0번 프로세스를 복사해서 사용하게 돼.이때 fork() 함수를 사용해.복사해서 사용하는 이유는 새로 생성하는 것보다 복사를 하는게 더 빠르기 때문이야.0번 프로세스를 복사해서 생성된 프로세스들을 자식 프로세스라고 해. 그럼 0번 프로세스는 부모 프로세스가 되겠지?자식 프로세스는 부모 프로세스의 코드영역, 데이터영역, 스택영역과 PCB의 내용을 전부 복사해.0번 프로세스의 코드와 데이터를 모두 복사해서 실행하면 0번 프로세스가 똑같이 실행되는거 아닌가?맞아...그럼 자기가 원하는 함수를 어떻게 실행시킬까? 바로 exec() 함수를 이용하면 돼.fork() 함수로 프로세스를 복사 후 exec() 함수를 실행시키면 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓰게 돼.그럼 이때부터 자식 프로세스는 부모 프로세스와 완전히 다르게 동작하게되는거지!쓰레드 참조 : 그림으로 쉽게 배우는 운영체제 3주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.

운영체제･워밍업클럽CS

알고리즘

*이 내용은 인프런 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)을 수강하며 정리한 내용입니다. 재귀(recursion)재귀는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻해. 그러므로 재귀함수는 탈출 조건, 즉 기저 조건이 반드시 있어야 해.콜스택함수가 호출되면서 올라가는 메모리 영역으로 스택이라고도 불러. FILO의 특징을 띄고있어.상향식 계산 vs 하향식 계산재귀를 이용한 상향식 계산하지만 재귀는 하향식 계산일 때 위력을 발휘해!하노이 탑function hanoi(count, from, to, temp){ if(count == 0) return; hanoi(count - 1, from, temp, to); console.log(`${count} ${from} -> ${to}`); hanoi(count - 1, temp, to, from); } hanoi(3, "A", "C", "B"); 정렬버블정렬데이터를 옆 데이터와 비교하는 정렬이야.function BubbleSort(arr){ for(let i = 0; i < arr.length - 1; i++){ for(let j = 0; j < (arr.length - i - 1); j++){ if(arr[j] > arr[j + 1]){ // j, j+1 비교 let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }성능위와 같으므로 빅 오는 O(n**2)이 돼!성능이 중요한 시스템을 만드려면 버블 정렬은 어려울 수도 있어...장점 : 이해와 구현이 간단함단점 : 성능이 좋지 않음선택 정렬배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 뭔소로 가져오는 정렬이야.function SelectionSort(arr){ for(let i = 0; i < arr.length - 1; i++){ let minValueIndex = i; for(let j = i + 1; j < arr.length; j++){ // 가장 작은 index 찾기 if(arr[j] < arr[minValueIndex]){ minValueIndex = j; } } let temp = arr[i]; arr[i] = arr[minValueIndex]; arr[minValueIndex] = temp; } }성능 버블정렬과 동일해! 즉 선택 정렬의 정렬도 O(n**2)이야.장점 : 이해와 구현이 간단함단점 : 성능이 좋지 않음 삽입정렬정렬되지 않은 영역의 데이터를 정렬된 영역에 끼워 넣는 정렬방식이야. 정렬된 영역을 뒤에서부터 역순으로 비교해.function InsertionSort(arr){ for(let i = 1; i < arr.length; i++){ let insertingData = arr[i]; let j; for(j = i - 1; j >= 0; j--){ if(arr[j] > insertingData){ arr[j + 1] = arr[j]; }else{ break; } } arr[j + 1] = insertingData; } } 성능 :위 정렬들과 마찬가지고 O(n**2)이야.장점 : 이해와 구현이 간단함단점 : 성능이 좋지 않음병합정렬분할 정복 알고리즘이야.숫자 하나가 들어있는 배열로 만들어주었으면 두 배열을 순서에 맞게 정렬한 후 두개의 숫자가 들어있는 배열 하나로 만들어 줘.이런식으로~같은 방식으로 이렇게 배열해주면 돼.function MergeSort(arr, leftIndex, rightIndex){ if(leftIndex < rightIndex){ let midIndex = parseInt((leftIndex + rightIndex) / 2); MergeSort(arr, leftIndex, midIndex); MergeSort(arr, midIndex + 1, rightIndex); Merge(arr, leftIndex, midIndex, rightIndex); } } function Merge(arr, leftIndex, midIndex, rightIndex){ let leftAreaIndex = leftIndex; let rightAreaIndex = midIndex + 1; let tempArr = []; tempArr.length = rightIndex + 1; tempArr.fill(0, 0, rightIndex + 1); let tempArrIndex = leftIndex; // tempArrIndex에 정렬해주기 ( leftArea 혹은 rightArea 둘 중 하나 정렬.) while(leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex){ // 왼쪽 영역과 오른쪽 영역이 정렬되지 않을 동안 if(arr[leftAreaIndex] <= arr[rightAreaIndex]){ tempArr[tempArrIndex] = arr[leftAreaIndex++]; }else{ tempArr[tempArrIndex] = arr[rightAreaIndex++]; } tempArrIndex++; } // 남은 절반 값 넣어주기 // 한쪽 영역이 전부 병합되었다면 나머지 영역은 정렬이 되어있다. if(leftAreaIndex > midIndex){ for(let i = rightAreaIndex; i <= rightIndex; i++){ tempArr[tempArrIndex++] = arr[i]; } }else{ for(let i = leftAreaIndex; i <= midIndex; i++){ tempArr[tempArrIndex++] = arr[i]; } } for(let i = leftIndex; i <= rightIndex; i++){ arr[i] = tempArr[i]; } }성능하나의 데이터와 하나의 데이터가 하나로 합쳐질 때 비교 연산을 두 번 해.마찬가지로 두개의 데이터와 두개의 데이터가 하나로 합쳐질 때에는 비교가 네번 이루어져.각 단계를 거칠 때마다 영역의 수가 반으로 줄기 때문에 log(n)으로 말할 수 있어.분할된 배열을 병합할 때는 n개의 데이터를 n번 비교하므로n과 log(n)을 곱해서 O(nlogn)이야.장점 : 성능이 좋음단점 : 이해와 구현이 어려움퀵정렬병합정렬과 마찬가지고 분할 정복 알고리즘이야.우선 pivot을 랜덤으로 설정해.leftStartIndex는 오른쪽으로 이동하다가 피벗보다 큰 값을 만나면 멈춰.rightStartIndex는 왼쪽으로 이동하다가 피벗보다 작은 값을 만나면 멈춰.그리고 두 값을 swap 해.계속 반복하다가 서로 지나치게 되면 rightStartIndex와 pivot을 swap해줘.이렇게되면 pivot를 기준으로 왼쪽은 모두 pivot보다 작은 값이 위치하고, 오른쪽은 모두 pivot보다 큰 값이 위치하게 돼.이를 반복하면 되는거지!quickSortfunction quickSort(arr, left, right){ if(left <= right){ // 기저 조건 let pivot = divide(arr, left, right); // 정렬된 pivot의 위치 console.log(right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot + 1, right); } }dividefunction divide(arr, left, right){ // 정렬 let pivot = arr[left]; let leftStartIndex = left + 1; let rightStartIndex = right; while(leftStartIndex <= rightStartIndex){ // leftStartIndex 이동 while(leftStartIndex <= right && pivot >= arr[leftStartIndex]){ leftStartIndex++; } while(rightStartIndex >= (left + 1) && pivot <= arr[rightStartIndex]){ // rightStartIndex 이동 rightStartIndex--; } if(leftStartIndex <= rightStartIndex){ // 서로 지나치지 않았다면 swap swap(arr, leftStartIndex, rightStartIndex); } } swap(arr, left, rightStartIndex); // pivot과 rightStartIndex를 swap return rightStartIndex; }swapfunction swap(arr, index1, index2){ let temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } 성능데이터가 한 개가 될 떄까지 반으로 나누므로 log(n)!이 작업을 데이터 n개만큼 반복해야하므로 n을 곱함!보통 최악의 pivot을 선택하는 경우는 드물기때문에 평균 성능인 nlogn으로 표시해.퀵 정렬의 장단점은 병합 정렬과 동일해. 병합 정렬이 더 좋아보이지만 실제로 퀵 정렬이 더 좋게 평가돼. 동적 프로그래밍메모이제이션피보나치 수열을 구현할 때 재귀함수를 이용하게되면 위 사진처럼 중복되는 호출이 많아. 그럼 중복되는 계산 결과를 저장하고, 같은 계산이 필요할 때 저장도니 결과를 사용하면 더 좋겠지?그렇게되면 함수의 호출 수가 줄어들게되고 성능이 향상될거야.이를 메모이제이션이라고 해.그럼 어떤 자료구조를 사용하면 될까? 바로 해시 테이블이야.빠른 데이터 탐색, 삽입, 삭제가 가능하기 때문이지!해시 테이블의 key로 계산하려는 값을, value로 계산 결과를 저장하면 검색을 빠르게 할 수 있을거야.자바스크립트 객체 또한 해시테이블이므로 이를 이용하여 코드를 작성해볼게.function fibonacci2(n, memo){ if(n == 0 || n == 1) return n; if(memo[n] == null){ // 계산 결과가 없다면 저장 memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo); } return memo[n]; }이러면 실행 속도가 훨씬 빨라져.타뷸레이션function fibonacci2(n, memo){ if(n == 0 || n == 1) return n; if(memo[n] == null){ memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo); } return memo[n]; } 참조 : 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 3주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.

알고리즘 · 자료구조･워밍업클럽CS

자료구조

*이 내용은 인프런 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)을 수강하며 정리한 내용입니다. Linked List 구현 (JS)추상자료형어떠한 데이터와 그 데이터에 대한 연산을 표기하는 것이야. 연결리스트의 추상자료형모든 데이터 출력 - printAll()모든 데이터 제거 - clear()인덱스 삽입 - insertAt(index, data); 마지막 삽입 - insertLast(data); 인덱스 삭제 - deleteAt(index);마지막 삭제 - deleteLast();인덱스 읽기 - getNodeAt(index); 구현이제 위 추상자료형을 바탕으로 구현을 해보자.연결리스트는 데이터를 담은 노드를 서로 연결하는 구조야. 이를 위해서 가장 먼저 만들어야하는 것은 노드겠지?노드 class Node{ // 생성자의 매개변수로 data, next를 만들어준다. // 매개변수 data는 필수이지만, // next는 입력하지 않는다면 null이 할당된다. constructor(data, next = null){ this.data = data; this.next = next; } } 아래와 같이 자기 참조 변수를 만들어준 후 추상자료형에서 나열한 함수들을 만들어볼게.class LinkedList{ constructor(){ this.head = null; // 연결리스트의 시작 노드 this.count = 0; // 총 저장된 노드의 수 }insertAt(index, data);insertAt(index, data){ // 예외 처리 if(index > this.count || index < 0){ throw new Error("범위를 넘어갔습니다."); } let newNode = new Node(data); // 리스트의 가장 앞부분에 삽입하는 경우 if(index == 0){ newNode.next = this.head; // next 노드 설정 this.head = newNode; // 새 노드를 head로 설정 } else { // 목표 index의 전 노드까지 도달 let currentNode = this.head; for(let i = 0; i < index - 1; i++){ currentNode = currentNode.next; } newNode.next = currentNode.next; // next 노드 설정 currentNode.next = newNode; // 전 노드와 연결 } this.count++; }printAll()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()clear(){ this.head = null; this.count = 0; }insertLast(data); insertLast(data){ // insertAt(index, data) this.insertAt(this.count, data); }deleteAt(index);deleteAt(index){ // 예외 처리 if(index >= this.count || index < 0){ throw new Error("제거할 수 없습니다."); } let currentNode = this.head; if(index == 0){ // 첫번째 노드를 제거하는 상황 let deletedNode = this.head; this.head = this.head.next; // head 노드 변경 this.count--; // count 줄여줌 return deletedNode; } else { for(let i = 0; i < index - 1; i++){ // 제거할 노드의 이전 노드까지 순회 currentNode = currentNode.next; } let deletedNode = currentNode.next; currentNode.next = currentNode.next.next; // 노드 연결 this.count--; return deletedNode; } }deleteLast();deleteLast(){ return this.deleteAt(this.count - 1); }getNodeAt(index);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; } 스택FILO의 리스트 형태야. ctrl+z를 구현할 때 스택이 사용되지!FILO의 조건만 충족한다면 어떤 자료구조로 구현하던지 상관없어.즉, 배열이나 연결리스트 각각으로 스택을 구현할 수 있어. 지금은 만들어놓은 연결리스트로 스택을 구현해볼게.새로 들어온 노드를 head로 지정해주면 돼. 스택의 추상자료형push - 데이터 삽입pop - 데이터 제거peek - 데이터 참조isEmpty - 비었는지 체크 구현class Stack{ constructor(){ this.list = new LinkedList(); } push(data){ // 0 인덱스에 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); } }큐FIFO의 형태야. 마찬가지로 연결리스트로 구현해보자.이번에도 삽입하는 노드를 head로 지정하는 대신, 삭제하기 쉽도록 tail 이라는 변수를 하나 더 만들어서 가장 처음 삽입한 노드를 가리키도록 하자.이렇게했을때 처음 삽입한 노드를 삭제하게되면 tail은 전 노드를 가리켜야해.하지만 우리는 단방향 연결리스트를 구현했기 때문에 전 노드를 알 수 없어. 즉, 이중연결리스트로 수정해야해! 큐의 추상자료형enqueue - 데이터 삽입dequeue - 데이터 제거front - 데이터 참조isEmpty - 비었는지 확인DoublyLinkedList.mjsnode 수정 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; // tail 추가 this.count = 0; }insertAt(index, data) 수정데이터가 삽입될 때 이전 노드를 가리키는 코드를 추가하자.insertAt(index, data){ if(index > this.count || index < 0){ throw new Error("범위를 넘어갔습니다."); } let newNode = new Node(data); if(index == 0){ // head에 삽입하는 경우 newNode.next = this.head; if(this.head != null){ this.head.prev = newNode; } this.head = newNode; }else if(index == this.count){ // tail에 삽입하는 경우 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++; } deleteAt(index) 수정deleteAt(index){ if(index >= this.count || index < 0){ throw new Error("제거할 수 없습니다."); } let currentNode = this.head; if(index == 0){ let deletedNode = this.head; if(this.head.next == null){ // 데이터가 1개일 때 this.head = null; this.tail = null; } else { this.head = this.head.next; this.head.prev = null; } this.count--; return deletedNode; } else if(index == this.count - 1){ // 마지막 노드를 제거할 경우 let deletedNode = this.tail; this.tail.prev.next = null; this.tail = this.tail.prev; this.count--; return deletedNode; } else { for(let i = 0; i < index - 1; i++){ currentNode = currentNode.next; } let deletedNode = currentNode.next; currentNode.next = currentNode.next.next; currentNode.next.prev = currentNode; this.count--; return deletedNode; } } Queue.mjsclass 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); } } 참조 : 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 2주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.다음 주에는 권장 커리큘럼을 지켜 수강하는 것이 목표입니다!

알고리즘 · 자료구조･워밍업클럽CS

운영체제

*이 내용은 인프런 그림으로 쉽게 배우는 운영체제를 수강하며 정리한 내용입니다. 인터럽트## 인터럽트- 정의: CPU가 현재 실행 중인 작업을 중단하고, 외부 또는 내부에서 발생한 중요한 이벤트를 처리하기 위해 호출되는 신호. 인터럽트는 현재 작업을 일시적으로 멈추고, 급한 작업을 먼저 처리한 후 다시 원래 작업으로 돌아오게 함.- 종류: - 하드웨어 인터럽트: 키보드 입력, 마우스 클릭, 타이머 등 하드웨어에서 발생하는 인터럽트. - 소프트웨어 인터럽트: 프로그램 내에서 오류가 발생하거나 시스템 호출 시 발생하는 인터럽트.- 역할: CPU가 매번 직접 확인하지 않아도 중요한 사건이 발생하면 즉시 대응할 수 있게 해줌. 멀티태스킹 환경에서 필수적임.## 프로세스- 정의: 실행 중인 프로그램의 인스턴스. CPU에서 독립적으로 실행되는 기본적인 실행 단위로, 운영체제가 프로세스를 관리하고 스케줄링함.- 특징: - 각각 고유의 메모리 공간(코드, 데이터, 스택 등)을 가지고 있으며, 다른 프로세스와 메모리를 공유하지 않음. - 운영체제는 프로세스 상태(생성, 준비, 실행, 대기, 종료)를 관리하며, CPU가 하나의 프로세스를 실행 중일 때 다른 프로세스는 대기 상태로 전환될 수 있음.- 프로세스 상태: - 생성: 프로세스가 생성되고 운영체제에 등록됨. - 준비: CPU가 할당되기를 기다리는 상태. - 실행: 프로세스가 CPU를 할당받아 명령을 실행하는 상태. - 대기: 입출력 등의 이유로 잠시 멈춰 있는 상태. - 종료: 프로세스가 실행을 마치고 종료된 상태.## 쓰레드- 정의: 프로세스 내에서 실행되는 가벼운 실행 단위. 하나의 프로세스는 여러 개의 쓰레드를 가질 수 있으며, 각 쓰레드는 독립적으로 실행됨.- 특징: - 같은 프로세스 내의 다른 쓰레드와 메모리를 공유하므로, 프로세스보다 가벼운 자원을 사용함. - 쓰레드는 CPU를 효율적으로 사용하여 병렬 처리(멀티스레딩)를 가능하게 함. - 그러나 메모리를 공유하기 때문에, 동기화 문제(공유 자원 접근 충돌)가 발생할 수 있음.- 장점: 메모리 공간을 적게 사용하면서 병렬 처리 성능을 높일 수 있음. 또한 쓰레드 간 통신이 빠름.- 단점: 공유 메모리를 사용할 때 동기화 문제를 해결하지 않으면 데이터 일관성 문제가 발생할 수 있음. 참조 : 그림으로 쉽게 배우는 운영체제 2주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.다음 주에는 권장 커리큘럼을 지켜 수강하는 것이 목표입니다!

운영체제･워밍업클럽CS

자료구조

*이 내용은 인프런 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)을 수강하며 정리한 내용입니다. 덱데이터의 삽입과 제거를 head와 tail 두군데서 자유롭게 할 수 있어.덱의 추상자료형printAll - 모든 데이터 출력addFirst - head에 데이터 삽입removeFirst - head에서 데이터 제거addLast - tail에 데이터 삽입removeLast - tail에서 데이터 제거isEmpty - 리스트 비었는지 체크구현DoublyLinkedList.mjs를 import 해줘.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); } }해시테이블해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)라고도 불려.해시 테이블은 이름에서도 알 수 있듯이 해시와 테이블이 합쳐진 자료구조야.해시 함수Key만 알면 Value에 O(1)의 성능으로 읽기가 가능하다!하지만 동일한 Key에 많은 Value를 집어넣는다면 많은 연결리스트를 뒤져야해.그러므로 데이터를 골고루 분배하는 것이 중요해!!장점 : 빠른 데이터 읽기, 삽입, 삭제단점 : 메모리를 많이 차지함, 좋은 해시 함수의 구현이 필수적!추상자료형set - 데이터 삽입get - 데이터 읽기remove - 데이터 제거 구현구현하기 전 hash 함수를 어떻게 만들거냐면~위와같은 형식으로 10으로 나눈 나머지의 인덱스에 값을 삽입할거야!HashDataclass HashData{ constructor(key, value){ this.key = key; this.value = value; } }HashTableclass HashTable{ constructor(){ this.arr = []; for(let i = 0; i < 10; i++){ // 0~9까지 연결리스트 초기화 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; } }Set데이터의 중복을 허용하지 않는 자료구조야. 셋은 해시 테이블을 이용해.해시 테이블의 value 값은 사용하지 않고 key만 사용해서 구현해!!추상자료형add(data) - 데이터 삽입isContain(data) - 데이터 체크remove(data) - 데이터 제거clear() - 셋 비우기isEmpty() - 셋이 비었는지 체크printAll() - 모든 데이터 출력구현class HashSet{ constructor(){ this.hashTable = new HashTable(); } add(data){ if(this.hashTable.get(data) == null){ this.hashTable.set(data, -1); // value는 쓰이지 않기때문에 그냥 -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; } } } } 참조 : 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 3주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.

알고리즘 · 자료구조･워밍업클럽CS