인프런 워밍업 클럽 CS 3기 1주차 발자국

강의 내용 요약

운영체제

운영체제의 기본 개념

1. 운영체제의 필요성과 역할

• 컴퓨터 동작에 있어서 운영체제는 반드시 필요한가?

✔ 정답은 No 다.

❗하지만 운영체제가 없으면 컴퓨터는 처음 설계한 대로 동작할 뿐 다른 기능을 수행할 수 없다.

• 운영체제의 역할

  1. 프로세스 관리

  2. 메모리 관리

  3. 하드웨어 관리

  4. 파일 시스템 관리

2. 운영체제의 구조

    

   • 커널 ⭐⭐⭐

     • 프로세서, 메모리, 저장장치를 관리하는 핵심 기능을 담당

     • 사용자는 운영체제의 커널에 직접 접근할 수 없으며 인터페이스(CLI, GUI)를 통해 접근 가능

     • 어플리케이션(게임, 인터넷, MS office, 멜론 뮤직….)은 시스템 콜을 통해 커널에 접근 가능

        

     • 인터페이스(GUI/CLI)는 쉘(Shell)이나 API를 통해 간접적으로 시스템 콜을 이용

       • (인터페이스(GUI/CLI) → 쉘 또는 API → 시스템 콜 → 커널)

     • 시스템 콜은 응용 프로그램이 직접 커널을 호출하는 방식

컴퓨터 하드웨어

1. 폰 노이만 구조

• CPU와 메모리를 버스(데이터를 전달하는 통로)로 연결하는 방식

• 프로그램을 메모리에 올려서 실행시킴(프로그램 내장 방식)

2. CPU 구조

• 산술논리 연산장치(ALU, Arithmetic and Logical Unit)

  • CPU 내에서 실제로 데이터 연산을 담당

• 제어 장치(Control Unit)

  • 모든 장치들의 동작을 지시하고 제어

• 레지스터(Register)

  • CPU 내에서 계산을 위해 임시로 보관하는 장치

     

     

  3. 메모리 종류

• RAM(Random Access Memory)

  • 무작위 위치의 데이터를 읽어도 저장된 위치와 상관없이 데이터를 읽는 속도가 같음

  • 전력이 끊기면 데이터가 소실됨(휘발성)

  • 메인 메모리로 사용

• ROM(Read Only Memory)

  • 전력이 끊겨도 계속 데이터를 보관할 수 있음(비휘발성)

  • 데이터를 한 번 쓰면 수정이 불가능함

  • 부팅과 관련된 BIOS를 저장하는 용도로 사용

4. 인터럽트와 폴링

• CPU가 입출력 작업을 처리한다고 가정

• 폴링 방식

  • CPU가 주기적으로 입출력 명령을 확인하여 명령을 처리하는 방식

  • CPU의 성능 저하가 발생

• 인터럽트 방식

  • CPU가 프로그램을 실행하고 있을 때, 입출력 처리가 필요한 경우 CPU에게 이를 알려주는 방식

  • CPU는 인터럽트가 발생했을 때만 입출력을 처리하므로 그 외의 경우에는 다른 작업을 수행할 수 있음 → 비동기적으로 동작하기 때문에 성능 이점

  • 하드웨어 인터럽트: 입출력 인터럽트, 외부 신호 인터럽트 등등

  • 소프트웨어 인터럽트: 프로그램 오류로 인한 인터럽트(Exception, Underflow/Overflow, Divison by Zero 등등)

프로그램과 프로세스

1. 프로그램이란?

• 하드디스크나 SSD와 같은 저장장치에 저장된 명령문의 집합체

• 애플리케이션 혹은 앱이라고도 불리며 windows 운영체제 기준 .exe 확장자를 가짐

• 컴퓨터 관점에서 저장장치만 사용하는 수동적인 형태

   

   

   

   

  2. 프로세스란?

• 실행중인 프로그램 → 저장장치에 저장된 프로그램이 메모리에 올라가서 실행중인 상태

• 컴퓨터 관점에서 메모리를 사용하고 운영체제의 CPU 스케줄링 알고리즘에 따라서 CPU도 사용하고 필요에 따라 입출력도 수행하는 능동적인 형태

• 프로세스 구조(메모리 구조와 같음)

  

  • code(text) : 실행할 소스코드가 저장되어 있는 영역

  • data : 전역 변수와 정적(static) 변수가 할당되는 영역

  • stack : 지역 변수와 함수 호출 시 필요한 정보(매개변수 등)가 저장되는 영역

  • heap : 프로그래머에 의해 동적으로 할당/해제되는 메모리 영역

    • C언어의 malloc(), free()가 대표적인 heap 영역을 동적 할당하는 함수

       

멀티프로그래밍과 멀티프로세싱

1. 유니프로그래밍

    

   • 메모리에 하나의 프로세스가 올라온 것

    

2. 멀티프로그래밍

    

   • 메모리에 여러 개의 프로세스가 올라온 것

    

3. 멀티프로세싱

    

   • CPU가 여러 개의 프로세스를 처리하는 것

   • 메모리 관점이 아닌 CPU 관점

    

4. 현대의 멀티프로그래밍과 멀티프로세싱

• 현대의 OS(운영체제)에는 멀티프로그래밍과 멀티프로세싱이 공존함

• 메모리에는 여러 개의 프로세스가 동시에 올라올 수 있고(멀티프로그래밍), CPU는 시분할처리를 이용하여 각각의 프로세스를 짧은 시간 동안 교대로 실행함(멀티프로세싱)

PCB(Process Control Block)

1. PCB란?

• 프로세스에 대한 정보를 가지고 있는 커널의 자료구조

• PCB는 특정 프로세스에 관한 모든 정보를 가지고 있음

• PCB들은 연결 리스트 방식으로 저장됨.

   

• PCB의 구조

  • 포인터 : 부모/자식 프로세스에 대한 포인터, 프로세스의 현재 위치에 대한 포인터, 할당된 자원에 대한 포인터 정보

  • 프로세스 상태 : 프로세스의 상태(생성, 준비, 실행, 대기, 종료)에 대한 정보를 저장

  • 프로세스 ID : 프로세스를 식별하기 위한 고유한 숫자값이 저장

  • 프로그램 카운터 : 다음에 실행될 명령어의 주소를 저장

  • 레지스터 정보 : 프로세스가 실행될 때 사용했던 레지스터 값들이 저장됨(CPU를 뺏기고 다시 시작할 때 이전에 사용하던 값을 복구하기 위한 용도)

  • 메모리 관련 정보 : 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기 위한 경계 레지스터 값 등이 저장됨

  • CPU 스케줄링 정보: CPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간 등이 저장됨

프로세스 상태

1. 프로세스 상태가 왜 존재하는가?

• 시분할 시스템을 사용하는 운영체제는 여러 개의 프로세스를 돌아가면서 실행함

• 속도가 매우 빨라 동시에 실행하는 것처럼 보이지만, CPU는 한 순간에는 하나의 프로세스밖에 처리하지 못함

• 시분할 시스템에 대응하기 위해 프로세스는 5가지의 상태를 가짐

2. 프로세스 상태의 종류

• 생성(New)

  • 메모리에 프로그램 적재를 요청한 상태

  • 메모리에 프로그램 적재가 승인되면 그 때 PCB가 생성되고 준비 상태로 넘어간다.

• 준비(Ready)

  • 프로세스가 CPU 사용을 위해 기다리고 있는 상태

  • 준비 상태의 프로세스는 CPU 스케줄러에 의해 CPU가 할당됨

  • 대부분의 프로세스는 준비 상태에서 CPU 사용을 기다리고 있음

• 실행(Running)

  • 프로세스가 CPU 스케줄러에 의해 CPU를 할당받아 실행되는 상태

    • 준비 → 실행 (Dispatch)

  • 실행 상태에 있는 프로세스의 수는 CPU의 개수(CPU의 코어 개수)만큼임

  • 실행 상태에 있는 프로세스는 CPU 스케줄러가 부여한 시간 만큼만 CPU를 사용할 수 있음

  • 프로세스가 할당된 시간을 초과하면 CPU 스케줄러는 CPU를 강제로 빼앗기며 준비 상태로 돌아감 (Timeout)

    • 실행 → 준비 (Timeout)

• 대기(Waiting)

  • 프로세스가 입출력 요청을 하면 입출력이 완료될 때까지 기다리는 상태

  • 실행 중인 프로세스가 입출력 요청을 하면 해당 프로세스를 대기 상태로 두고 다른 프로세스에게 CPU를 할당함

    • 실행 → 대기 (Block)

  • 입출력 작업이 끝나면 대기 상태에 있던 프로세스는 다시 CPU 할당을 위해 준비 상태로 이동

    • 대기 → 준비 (Wakeup)

• 완료(Terminated)

  • 프로세스가 종료된 상태

  • 프로세스가 사용했던 데이터를 메모리에서 제거하고 PCB도 제거

• 프로세스 상태 전이 다이어그램

컨텍스트 스위칭(Context Switching)

1. 컨텍스트 스위칭이란?

• 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업

• 컨텍스트 스위칭이 발생할 때 PCB의 내용이 변경됨

  • 프로세스 상태

  • 프로그램 카운터

  • 레지스터 정보

  • 메모리 관련 정보

   

• 실행 중인 프로세스의 작업내용을 해당 프로세스의 PCB에 저장 → 다음에 실행될 프로세스의 PCB의 내용대로 CPU를 세팅

프로세스 생성과 종료

1. 프로세스의 생성 (0번 프로세스)

    

   • 운영체제는 프로그램의 코드영역과 데이터 영역을 메모리에 로드

   • 빈 스택과 힙을 만들어 메모리 공간을 확보

   • 프로세스를 관리하기 위한 PCB 생성하여 값을 초기화

      

   • 위의 과정은 운영체제가 부팅되고 0번 프로세스가 생성될 때 딱 1번만 실행

    

2. 프로세스의 복사 (나머지 프로세스)

• 나머지 모든 프로세스는 새로 생성이 아닌 0번 프로세스를 복사해서 사용

• 프로세스 복사는 fork() 함수를 이용

  • 부모 프로세스를 복사해서 자식 프로세스를 생성

  • 리턴값으로 부모 프로세스에는 자식 프로세스의 PID, 자식 프로세스에는 0을 반환

   

• 프로세스 복사를 통해 생성되는 프로세스는 자식 프로세스

• 복사의 원본이 되는 프로세스는 부모 프로세스

• 자식 프로세스는 부모 프로세스의 코드,데이터, 스택 영역과 PCB의 모든 내용을 복사 → 부모 프로세스와 완전 동일

• 자식 프로세스가 부모와 완전히 같으면 자신이 원하는 코드는 어떻게 실행할까?

  • exec() 함수 이용

  • fork() 함수로 프로세스 복사 → exec() 함수로 코드와 데이터 영역을 원하는 값으로 덮어쓰기

  • exec() 함수가 완료된 시점부터 부모 프로세스와는 완전히 다른 방식으로 작동 (부모-자식 관계는 계속 유지)

• 좀비 프로세스?

  • 부모 프로세스가 자식 프로세스보다 먼저 종료되거나 자식 프로세스가 비정상적으로 종료돼 exit() 신호를 주지 못해서 부모가 Exit status를 읽지 못해 메모리에 계속 살아있는 상태

쓰레드(Thread)

• 쓰레드는 왜 필요한가?

   

  • 운영체제가 기본적으로 작업을 처리하는 단위는 프로세스

  • 프로세스의 수가 많아지면 각각의 프로세스에 대해서 PCB를 생성하고 메모리에 코드, 데이터, 스택, 힙영역을 모두 할당해줘야 하므로 너무 무거워짐

     

  • 크롬 브라우저의 경우 탭 1개 당 프로세스 1개로 동작

  • 탭을 많이 띄울 수록 크롬 브라우저가 가지는 프로세스의 수가 늘어남

  • 크롬 브라우저가 메모리를 너무 많이 차지하게 됨

  • 크롬 브라우저의 탭들은 통신을 위해 IPC(Inter Process Communication)을 이용하는데 IPC는 상대적으로 통신의 비용이 비쌈

   

  • 프로세스가 컴퓨터 자원을 많이 차지하는 문제점을 해결하기 위해 쓰레드 라는 개념을 도입

   

   

  2. 쓰레드란?

   

• 쓰레드는 프로세스 내에 존재하는 것으로 하나의 프로세스는 1개 이상의 쓰레드를 가질 수 있음.

• 한 프로세스 내의 쓰레드들은 그 프로세스의 PCB, 코드, 데이터, 힙영역을 공유하며 스택은 쓰레드마다 각자 가지고 있음

  • 쓰레드는 스택을 제외한 나머지 영역을 공유해서 사용하기 때문에 프로세스 대비 메모리 절약이 많이 됨

• 한 프로세스의 내의 여러 쓰레드를 구분하기 위해 쓰레드 ID를 부여하고 쓰레드 관리를 위한 TCB(Thread Control Block)도 생성

  • 운영체제는 프로세스 내의 쓰레드를 구분할 수 있으며 작업을 처리하는 단위는 쓰레드가 되었음

• 크롬 브라우저와 달리 파이어폭스 브라우저는 처음 4개의 탭만 프로세스를 생성하고 추가적인 탭은 생성된 프로세스 내에 쓰레드를 추가하는 방식으로 동작
  

  3. 프로세스 vs 쓰레드

CPU 스케줄링

1. CPU 스케줄링이란?

• 운영체제가 특정 규칙에 따라 프로세스에게 CPU를 할당/해제하는 것

• CPU 스케줄러(운영체제 내부에 존재)가 CPU 스케줄링에서 고려해야 할 사항

  • 어떤 프로세스에게 CPU 리소스를 줘야 하는가?

  • CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야 하는가?

• CPU Burst : 프로세스가 CPU를 할당받아 작업을 수행하는 것

• I/O Burst : 프로세스가 입출력(I/O) 장치를 사용하여 데이터를 처리하는 것

2. 다중 큐와 프로세스 스케줄링

    

   • 프로세스의 상태 중 준비 상태와 대기 상태는 다중 큐에 의해 관리됨

   • 프로세스가 실행 상태에서 준비 상태로 돌아갈 때 운영체제는 해당 프로세스의 우선순위를 보고 그에 맞는 준비 큐에 넣음

      

   • CPU 스케줄러는 준비 상태의 다중 큐에 들어있는 프로세스들 중에 우선순위가 높은 프로세스를 선택하여 실행 상태로 전환시킴

      

   • 프로세스가 실행 상태에서 I/O 요청을 받아 대기 상태로 오게 되면 I/O 작업 종류에 따라 분류된 큐에 들어가게 됨

      

   • 정확히는 큐에는 프로세스 자체가 아닌 프로세스의 정보를 가지고 있는 PCB가 들어감

    

3. CPU 스케줄링의 핵심 목표

   • 리소스 사용률 (CPU, I/O 디바이스 등의 사용률을 높이는 것을 목표)

   • 오버헤드 최소화 (복잡하지 않은 스케줄링 방식 채택, 컨텍스트 스위칭 최소화가 목적)

   • 공평성 (모든 프로세스에서 공평하게 CPU가 할당되는 것을 목표)

     • 공평성의 의미는 사용하는 시스템의 환경에 따라 달라질 수 있음

     • ex) 자율주행 자동차의 운영체제는 다른 프로세스보다 자율주행 프로세스에 CPU를 더 많이 할당

     • 위와 같은 특수한 시스템이 아닌 일반 시스템의 경우, 모든 프로세스에게 CPU가 골고루 할당되는 것이 공평

   • 처리량 (단위시간당 더 많은 처리하는 것을 목표)

   • 대기시간 (작업을 요청하고 실제 작업이 이루어지기 전까지 대기시간이 짧은 것을 목표)

   • 응답시간 (사용자의 요청에 빠르게 반응하는 것을 목표)

    

   • 목표 간의 서로 상충하는 부분이 있기 때문에 사용하는 시스템에 따라서 목표를 다르게 설정해야 함

      

   • 일반적인 시스템의 경우 밸런스를 유지하는 것이 중요

    

   4. CPU 스케줄링 알고리즘

• FIFO(First In First Out)

• SJF(Shortest Job First)

• RR(Round Robin)

• MLFQ(Multi Level Feedback Queue)

   

자료구조

자료구조와 알고리즘

1. 자료구조란?

• 데이터가 저장, 사용되는 방법 및 형식

• 자료구조에 따라서 처리 방법이 달라질 뿐만 아니라 코드가 더 단순해질 수도 있음.

  // 일반 변수를 이용해 평균을 구하는 경우
  
  let a = 87;
  let b = 70;
  let c = 100;
  // 데이터를 1개 추가하는 경우
  let d = 55;
  
  let average = (a+b+c)/3;
  
  average = (a+b+c)/4;

// 배열을 이용해 평균을 구하는 경우

let arr = [87,70,100];
// 데이터를 1개 추가하는 경우
arr.push(55);

let average = 0;

for (let i = 0; i < arr.length; i++) {
	average += numbers[i];
}

average /= arr.length;

2. 알고리즘이란?

• 어떤 문제를 해결하기 위한 방법

• 사용하는 자료구조에 따라서 알고리즘이 달라짐

• 같은 자료구조에 대해서도 알고리즘은 여러가지가 존재할 수 있음

시간복잡도

1. 시간복잡도란?

• 일반적으로 알고리즘의 속도를 성능의 척도로 사용함

• 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간

• 컴퓨터의 사양이 사용자에 따라 다르기 때문에 절대적인 시간 측정이 아닌 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측함

  • 코드에서 성능을 많은 영향을 주는 부분 → 반복문(loop)

  • 최선의 경우 : Big-Ω (Big-Omega)

  • 최악의 경우 : Big-O (Big-Oh)

  • 평균의 경우 : Big-θ ****(Big-theta)

  • Big-O와 Big-θ를 주로 사용하며 가장 많이 사용하는 것은 Big-O

   

• 대표적인 시간 복잡도 그래프

  • O(n) : 선형시간 알고리즘

    • 입력 데이터 수에 비례하여 계산량이 증가함

  • O(1) : 상수시간 알고리즘

    • 입력 데이터 수와 상관없이 상수(1,2,3,4…)의 계산량을 가짐

   

• Big-O 표기법의 특징

  • 계산에 가장 많은 영향을 미치는 항만을 표기

  • Big-O 표기법으로 표시할 때는 상수는 큰 의미가 없으므로 제거

    • ex) n^2 + 2n +100 → O(n^2)

    • ex) 3n + 60 → O(n)

배열

1. 배열의 특징

• 배열의 생김새

• 일반적으로 프로그래밍 언어에서는 배열 선언 시 배열의 크기를 입력해야 함

• 운영체제는 메모리에서 연속된 빈 공간을 찾아서 순서대로 값을 할당함

• 할당하지 않는 부분은 쓰레기 값이 저장됨

• 운영체제는 배열의 시작 주소(arr[0]의 주소)만을 기억함. 배열은 0번째 인덱스부터 시작!

• 값에 접근 시 배열의 인덱스(arr[2], arr[4], arr[1]…)를 이용하여 접근함

• 배열은 인덱스 참조를 통해 길이에 상관없이 한번에 값에 접근할 수 있기 때문에 참조에서는 O(1)의 성능을 가짐. → 참조(읽기/쓰기)에서는 매우 훌륭한 성능을 지님

   

   

• But, 데이터의 삽입,삭제의 성능은 좋지 않음. Why?

  • 운영체제로부터 할당받은 배열의 길이를 넘어서는 메모리 공간에는 다른 중요한 데이터가 있을 수도 있음. → 함부로 접근 불가

  • 배열의 크기가 부족하다면?

    • 다른 메모리 공간에서 기존 배열보다 더 큰 연속된 크기의 공간을 찾아야 함.

    • 찾은 뒤 그 공간에 값을 복사한 뒤에 값을 삽입해야 함

    • 따라서 매우 비효율적이다.

  • 아예 배열의 크기를 엄청 크게 해놓으면?

    • 언제 삽입될지 모르는 데이터를 위해 큰 공간을 미리 할당하는 것은 엄청난 메모리 낭비임.

  • 배열 중간에 데이터 삽입/삭제는?

    • 넣으려는 위치의 값을 덮어씌우거나 혹은 모두 한 칸씩 뒤로 밀어야 한다. → 많은 연산 발생(오버헤드가 큼)

    • 삭제하려는 값을 지우고 그 뒤의 값을 모두 한 칸씩 앞으로 당겨야 한다. → 많은 연산 발생(오버헤드가 큼)

   

   

   

  2. 자바스크립트의 배열

• 자바스크립트의 배열은 일반적인 배열과는 조금 다르게 동작한다.

• 자바스크립트의 경우 상황에 따라서 연속적, 불연속적으로 메모리를 할당

• 불연속적으로 할당된 메모리는 내부적으로 연결해서 사용하여 사용자에게는 배열인 것처럼 보임

• 자료구조의 기능적인 부분은 일반적인 배열과 동일하므로 배열이라 부른다.

연결리스트(Linked List)

1. 연결리스트

• 배열의 단점인 메모리 낭비와 데이터 삽입/삭제를 해결하기 위해 탄생한 자료구조

• 저장하려는 데이터를 메모리 공간에 분산해 할당 + 데이터들을 서로 연결

• 연결리스트의 노드 구조

• 데이터를 담는 변수(DATA) + 다음 노드를 가리키는 변수(NEXT)로 구성

• 연결리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근 할 수 있음.

• 장점

  • 데이터 삽입 시 빈 메모리 공간 아무 곳에 데이터를 생성하고 연결만 하면 되기 때문에 초기 크기를 알 필요가 없음

  • 삭제도 삽입과 마찬가지로 연결만 끊어주면 됨

  • 따라서 삽입/삭제가 수월함
    

• 단점

  • 연결리스트의 경우 데이터들이 모두 분산되어 있기 때문에 배열처럼 바로 접근할 수 없음.

    • ex) 5번째 노드의 데이터에 접근하고 싶어!

    • 1번째 노드의 next로 2번째 노드 접근 → 2번째 노드의 next로 3번째 노드 접근 → 3번째 노드의 next로 4번째 노드 접근 → 4번째 노드의 next로 5번째 노드 접근 → 5번째 노드 데이터 찾았다! → O(n)의 성능

2. 배열 vs 연결리스트

스택(Stack)

1. 스택이란?

• FILO(First In Last Out)의 규칙을 가지는 자료구조

  

• 사용 사례

  • Ctrl+Z(되돌리기), 인터넷의 뒤로 가기, 문법 검사기

   

• 연결 리스트를 이용한 스택의 구현 방법

  • 삽입(Push)

    • 데이터 삽입을 무조건 첫번째 인덱스(head)에 하는 방식

  • 제거(Pop)

    • 무조건 첫번째 인덱스(head)만 제거하는 방식

큐(Queue)

1. 큐란?

• FIFO(First In, First Out)의 규칙을 가지는 자료구조

• 큐는 운영체제에서도 사용됨(FIFO 스케줄링)

• head와 tail을 이용하는 큐를 구현할 때, 단방향 연결리스트는 이전 노드를 가리켜야 하는 삭제 작업을 수행하기 어렵기 때문에 양방향 연결리스트로 구현해야 함

덱(Deque)

1. 덱이란?

    

   • 데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 구조 (Double Ended Queue)

   • 덱은 이러한 특징을 가지고 있기 때문에 덱을 이용하면 스택과 큐를 모두 구현할 수 있음

     • 스택 → (head에 데이터 삽입 + head에서 데이터 제거) or (tail에 데이터 삽입 + tail에서 데이터 제거)

     • 큐 → (head에 데이터 삽입 + tail에서 데이터 제거) or (tail에 데이터 삽입 + head에서 데이터 제거)

해시 테이블(Hash Table)

1. 해시 테이블이란?

• 해시와 테이블이 합쳐진 자료구조

• 프로그래밍 언어에 따라 조금씩 다른 내용을 가지고 있음 (Hash, Map, HashMap, Dictionary)

  

• 왼쪽과 같은 데이터 형식을 테이블이라 부르며 이를 저장하기 가장 간단한 방법은 배열에 저장하는 것

• 테이블을 오른쪽 배열과 같은 형식으로 저장했을 때 중간중간 빈 공간이 많이 발생하게 되어 메모리 낭비가 심하게 됨

• 이를 보완하기 위하여 기존의 인덱스를 어떠한 계산을 통해 정해진 범위 내로 한정하는 방법을 고안해냄 → 해시 함수

• 오른쪽의 배열은 해시 함수를 통해 테이블의 인덱스를 새로 만들기 때문에 해시 테이블이라 불림

• 해시 테이블의 인덱스는 key, 데이터는 value라고 불림

• 해시 테이블은 데이터 접근, 삽입, 삭제, 수정 모두 O(1)의 성능을 가짐

• 다만 해시 테이블은 collision(충돌)이 발생할 가능성이 있음

  • 충돌 : 같은 key를 가지는 데이터가 여러 개인 경우

  • 해시 함수를 등번호를 10으로 나눈 나머지라고 가정할 때, “이운재”와 “박지성”, “최진철”과 “이천수”는 같은 key값(1과 4)을 가져 충돌이 발생

• 충돌을 해결하기 위해 해당 key의 value를 연결리스트 형태로 구성하여 데이터를 연결 → O(n)의 성능을 가짐

• 하나의 key에 value들이 집중되는 충돌 현상을 최소화하기 위해 해시 함수의 선정이 굉장히 중요함

  • 좋은 해시 함수 : 데이터를 각 key에 골고루 분배시켜주는 함수

2. 해시 테이블의 장/단점 정리

셋(set)

1. 셋이란?

    

• 데이터의 중복을 허용하지 않는 자료구조

• 셋은 해시 테이블을 이용하기 때문에 해시 셋(Hash Set)이라고도 불림

• 셋은 해시 테이블의 value값은 사용하지 않고 key만을 사용하여 구현

• 위 테이블에서 “리오넬 메시”와 “크리스티아누 호날두”는 key가 중복되기 때문에 셋에서는 허용되지 않는다.

일주일 간의 회고

🍷칭찬하고 싶은 점

• 전공시간에 한번 배웠던 내용들이라서 생소하지는 않았지만 감자님이 강의하시는 내용을 뼈대로 제가 알고 있는 지식, 구글링을 통해 알게 된 지식 등을 살을 붙여 개인 노션 및 velog에 업로드하였습니다.

• 자료구조의 추상 자료형 이해를 위해 그림을 그려가며 이해하도록 노력하였고 강의 내의 질문 및 답변에서 스스로 답을 도출하거나 혹은 질문을 통해 모르는 부분을 해소하였습니다.

😅아쉬웠던 점

• 정리를 위해서 강의를 여러 번 돌려보다 보니 생각보다 많은 시간이 소요되었습니다.

• 강의 하나의 템포가 길어지니 생각보다 정신적으로 피로가 빨리 찾아왔습니다.

🛠보완하고 싶은 점

• 다음 주에 예비군 훈련이 있어서 평일에 시간을 내기가 더 어려울 것이라 예상되므로 시간 관리를 더 잘하도록 노력해야겠습니다.

• 미리 예습을 하는 방식으로 진도표에 적힌 진도는 반드시 맞출 수 있도록 해야겠습니다.

• 강의를 보면서 정리하는 것이 아니라 일단 한 번 정독한 후에 다시 한 번 돌려보면서 정리를 하는 것이 시간 절약 측면에서 도움이 될 지 한 번 시험해보는 1주를 보내야겠습니다.