CS 공부44 해시 테이블 (Hash Table) 해시 테이블이란? 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 효율적인 탐색(빠른 탐색)을 위한 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 저장, 삭제, 검색의 시간복잡도는 모두 O(1)이다. 직접 주소화 테이블? 해시 테이블와는 다르게 직접 주소화 테이블(Direct-address Table)이라는 key값으로 k를 갖는 데이터를 index k에 저장하는 방.. 2022. 8. 20. 기수 정렬 (Radix Sort) 기수 정렬(Radix Sort) 의 개념 요약 자릿수를 기준으로 차례대로 데이터를 정렬하는 정렬 알고리즘이다. 여기서 '기수' 라는 것은 '자릿수' 를 의미한다. 구체적 개념 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 알고리즘이다. 비교 연산을 하지 않아서 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 이 메모리는 기수 정렬에서 '버킷' 이라고 불리는데 숫자에 알맞게 새로운 공간에 값을 임시적으로 저장해주는 것이라고 생각하면 된다. 밑에서 더 자세히 설명하겠다. 가장 작은 자리수부터 비교하는 방법을 LSD(Least-Significant-Digit)라고 한다. 가장 큰 자리수부터 비교하는 방법은 MSD(Most-Significant-Dig.. 2022. 8. 13. IPC(Inter Process Communication) 프로세스는 독립적으로 실행된다. 즉, 독립 되어있다는 것은 다른 프로세스에게 영향을 받지 않는다고 말할 수 있다. (스레드는 프로세스 안에서 자원을 공유하므로 영향을 받는다) 때문에, 원칙적으로 다른 프로세스의 주소 공간을 참조할 수 없다. 하지만, 이런 독립적 구조를 가진 프로세스 간의 통신을 해야 하는 상황이 있을 것이다. 이를 가능하도록 해주는 것이 바로 IPC(Inter Process Communication) 통신이다. 프로세스는 커널이 제공하는 IPC 설비를 이용해 프로세스간 통신을 할 수 있게 된다. ※ 커널이란? 운영체제의 핵심적인 부분으로, 다른 모든 부분에 여러 기본적인 서비스를 제공해준다. IPC 종류 공유메모리 방식 통신을 이용한 설비가 있지만, 데이터 자체를 공유하도록 지원하는 방.. 2022. 8. 7. 합병정렬 (Merge Sort) 합병 정렬(Merge Sort) 의 개념 요약 분할 정복 알고리즘 중 하나이다. 분할 정복(divide and conquer) 방법 - 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 구체적인 개념 합병 정렬은 다음의 단계들로 이루어진다. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의.. 2022. 8. 7. PCB와 Context Switching Process Management CPU가 프로세스가 여러 개일 때, CPU 스케줄링을 통해 관리하는 것을 말한다. 이 때, CPU는 각 프로세스들이 누군지 알아야 관리가 가능하다. 이러한 프로세스들의 특징을 갖고 있는 것이 바로 Process Metadata이다. Process Metadata에는 다음과 같은 정보들이 있다. - Process ID : PID(Process Identification Number) 라고도 한다. : 프로세스 고유 식별 번호 - Process State (프로세스 상태) : 프로세스의 현재 상태(준비, 실행, 대기 상태)를 기억시킨다. - Process Priority (스케줄링 정보) : 프로세스 우선순위 등과 같은 스케줄링 관련 정보를 기억시킨다. - CPU Regis.. 2022. 7. 31. 버블정렬 (Bubble Sort) 버블 정렬(bubble sort) 의 개념 요약 서로 인접한 두 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하며 정렬해나가는 알고리즘이다. 구체적인 개념 버블 정렬은 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 교환하면서 정렬한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 예제 → 배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 오름차순으로 정렬해 보.. 2022. 7. 30. 이전 1 2 3 4 5 6 7 8 다음
