📌 셸 정렬 - 셸 정렬(Shell Sort): 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘. 삽입 정렬은 다음과 같은 특징을 갖고 있다. 1. 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 빠르다. (장점) 2. 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다. (단점) 앞에서 말했듯 셸 정렬은 삽입 정렬의 장점은 살리고 단점은 보완한 알고리즘이다. 셸 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나누어 각 그룹별로 정렬을 수행한 뒤, 정렬된 그룹을 합치는 작업을 반복해 원소의 이동 횟수를 줄이는 방법이다. 우선, 삽입 정렬의 경우 '주목한 원소보다 앞 쪽에서 이전의 값들과 비교하며 삽입을 수행'하는 정렬 알고리즘이다. 삽입 정렬의 가장 큰 장점은 '거의 ..

📌 동기화 (Synchronization) 동기화 (Synchronization): 다수의 프로세스 혹은 스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것 멀티 스레드는 하나의 프로세스에서의 공유된 자원을 사용하며 얻는 이점이 많다. 공유된 자원을 사용함으로써 메모리를 효율적으로 사용할 수 있고, 스레드 간 컨텍스트 스위칭이 가볍다는 장점이 있다. 하지만 이러한 이점과 동시에 동기화 작업을 해야 된다는 단점 또한 존재한다. 즉, 자원을 공유하며 공동으로 사용하기 때문에 공유 자원 접근 순서를 정하여 문제가 발생하지 않도록 해야 한다는 것이다. 예를 들어 하나의 객체에 두 개의 스레드가 접근할 때, 스레드가 언제 컨텍스트 스위칭이 되었는지에 따라 결과가 달라질 수 있는 현상이 발생할 수도 있는 ..

📌 IPC (Interprocess Communication) 프로세스의 가장 큰 특징은 독립된 메모리 공간을 할당 받는다는 것이다. 이는 개별 독립적이기 때문에 동기화를 위한 작업을 하지 않아도 된다는 장점이 있으나, 자원 소모적이라는 단점도 함께 존재한다. 그렇다면 이렇게 독립적으로 메모리 공간을 할당 받는 프로세스들이 어떻게 상호 간 통신을 할까? 이는 바로 커널에서 제공하는 IPC를 통해 서로 다른 프로세스들끼리 통신을 한다. IPC (=Interprocess Communication)는 프로세스들 사이에 서로 데이터를 주고 받는 행위 또는 그에 대한 방법이나 경로를 말한다. (IPC 정의 출처: 위키피디아) IPC 없이는 프로세스 간 통신이 어렵기 때문에 커널에서 IPC라는 내부 프로세스 간 통..

📌 프로그램과 프로세스 프로그램과 프로세스를 설명하기 전에, 사진과 함께 용어들을 간단하게 정리하고자 한다. Program: 컴퓨터가 실행할 수 있는 명령어들의 집합 Proess: 컴퓨터에서 실행 중인 프로그램 CPU(Central Processing Unit): 명령어를 실행하는 연산 장치 Main Memory: 프로세스가 CPU에서 실행되기 위해 대기하는 곳 PCB(Process Control Block): 특정한 프로세스를 관리할 필요가 있는 정보를 포함하는 운영 체제 커널의 자료 구조 우리는 컴퓨터를 사용하면서 흔히 프로그램이라는 단어를 접하곤 한다. 하지만 컴퓨터 용어에 관심이 없거나 작업 관리자 창을 자세히 보지 않았을 경우 프로세스라는 단어는 다소 생소할 수 있다. 또한 프로그램과 어떤 관계..

📌 정렬 알고리즘 - 정렬 알고리즘 (Sorting Algorithm): 원소들을 번호 순이나 사전 순과 같이 일정한 순서대로 열거하는 알고리즘. - 우리는 일상 속에서 정렬되어 있는 수많은 것들을 접하고 있다. 나의 일상을 예시로 들자면, 개인적으로 아침마다 확인하는 MTS 속에서도 특정한 기준으로 주식 종목들이 정렬되어 있는 것을 확인할 수 있다. 그리고 오후에 코딩테스트 공부를 하기 위해 programmers와 leetcode 사이트를 접속하는데, 사이트에 있는 코딩 문제들도 특정한 기준으로 문제들이 정렬되어 있는 것을 확인할 수 있으며, 저녁 11시에 업데이트 되는 네이버 웹툰에서도 조회순, 남성 인기순 등으로 만화들이 정렬되어 있는 것을 확인할 수 있다. 이렇듯 정렬은 우리의 일상 속에서 흔히 ..

📌 Queue란? 큐(Queue): 데이터를 임시 저장하는 자료구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO)구조이다. 스택(Stack): 큐와 같이 데이터를 임시 저장하는 자료구조로, 가장 마지막에 넣은 데이터를 가장 먼저 꺼내는 후입선출(LIFO)구조이다. 큐에 데이터를 넣는 작업을 인큐(enqueue)라 하고, 반대로 큐에서 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다. 큐에서 데이터를 넣는 쪽을 리어(rear)라 하고, 반대로 큐에서 데이터를 꺼내는 쪽을 프런트(front)라고 한다. 큐의 가장 큰 특징은 선입선출(FIFO)의 구조를 띄고 있다는 점과 너비 우선 탐색(BFS)에서 자주 사용된다는 점이다. 📌 OS scheduler와 Queue OS에서 프로세스를 스..

📌 이진 트리와 완전 이진 트리란? - 이진 트리(binary tree): 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리. 즉, 자식 노드가 최대 두 개인 노드들로 구성된 트리를 말한다. - 완전 이진 트리(complete binary tree): 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨에 한해서 가장 왼쪽부터 오른쪽으로 노드가 채워져 있는 트리를 말한다. 📌 이진 검색 트리란? - 이진 검색 트리(binary search tree): 이진 검색 트리는 다음과 같은 조건을 갖는 이진 트리다. 왼쪽 서브트리 노드의 키 값은 노드의 키 값보다 작아야 한다. 오른쪽 서브트리 노드의 키 값은 노드의 키 값보다 커야 한다. 왼쪽 및 오른쪽 서브트리 노드도 각각 이진 검색 트리여야 한..

📌 해시 테이블이란? 해시 테이블(Hash Table): (key, value)로 데이터를 저장하는 자료구조다. 즉, key와 value가 1:1로 연관 되어 key를 통해 value를 도출할 수 있는 자료구조다. Hash Table은 마치 사전과 같다. 사전은 단어를 찾기 위해 사용되기보단, 단어의 정의를 찾기 위해 사용된다. Hash Table 또한 마찬가지이다. Hash Table에서 key는 단순히 value를 찾기 위한 수단이며, 결국 우리가 얻고자 하는 것은 value이다. 📌 해시 테이블 구성 - key: 임의 크기의 데이터 - hash function: 가변 길이의 값을(key) 고정 크기 값으로(hash) 매핑시켜주는 함수. - hash (=index): 고정된 크기의 값. - bucke..