그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)

자료구조 & 알고리즘

• 자료구조 : 데이터가 어떤 구조로 저장되고, 어떻게 사용되는지를 나타낸다.

  • 자료구조에 따라서 결과를 얻기 위한 처리 방법이 달라진다.

• 알고리즘 : 어떤 문제를 해결하기 위한 확실한 방법

시간 복잡도

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

• Bit-Ω : 최선의 시간 복잡도

• Big-O : 최악의 시간 복잡도

  • 가장 많이 사용된다.

• Big-θ : 평균의 시간 복잡도

ADT(Abstract Data Type)

• 데이터의 논리적인 동작을 정의한다.

• 구현 방법을 명시하지 않고, 자료구조의 특성과 연산만을 설명한다.

• 내부 구현 세부사항은 숨기고 인터페이스만을 제공한다.

Array

• 배열의 인덱스 참조는 길이에 상관없이 한 번에 가져온다.

• 삽입, 삭제의 성능이 좋지 않다.

Linked List

• 배열의 단점인 삽입, 삭제의 성능을 보완하기 위한 자료구조

• 특정 데이터를 찾고 싶다면 노드를 순차적으로 순회해야 한다.

• 저장하려는 데이터들을 메모리에 분산하여 할당하고, 해당 데이터를 서로 연결한다.

• 노드를 사용하여 데이터들을 저장하고, 각 노드가 다음 노드를 가리키도록 한다.

• 첫 노드의 주소만 알고 있으면 그 이후의 모든 노드에 접근할 수 있다.

Stack

• LIFO(Last-in First-out)

• 단방향 Linked List를 사용하여 구현할 수 있다.

  • head를 사용하여 스택을 간단하게 구현할 수 있다.

  • 데이터 삽입을 무조건 첫 번째 인덱스에 수행한다.

Queue

• FIFO(First-in First-out)

• 양방향 Linked List를 사용하여 구현할 수 있다.

Deque

• 데이터의 삽입과 제거를 head와 tail에서 자유롭게 할 수 있는 자료구조

Hash Table

Hash Function

• 해시 함수는 키(key)를 입력받아 해당 키의 저장 위치(버킷 또는 인덱스)를 결정하는 계산을 하는 함수

• 좋은 해시 함수 ⇒ 데이터를 골고루 분배시켜주는 함수

   

  Hash Collision

• 해시 충돌은 해시 함수가 서로 다른 두 개 이상의 입력 값에 대해 동일한 해시 값을 출력하는 상황을 의미

• Hash 충돌이 발생한 곳의 Value들을 연결리스트로 구성하여 데이터들을 연결한다.

  • 기존값과 새로운 값을 동시에 저장할 수 있다.

  • 찾고자 하는 Value가 나올 때까지 연결리스트를 탐색한다.
    → O(n)의 성능을 갖는다.

  Set

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

• HashTable을 사용하여 구현할 수 있다.
  → HashTable을 사용하기 때문에 HashSet이라고도 한다.
  → HashTable의 value 값은 사용하지 않고 key만 사용하여 구현한다.
  (key가 key와 value의 역할을 수행한다.)

그림으로 쉽게 배우는 운영체제

OS가 하는 일

• 프로세스 관리 : 여러 개의 프로그램들을 동시에 수행할 수 있게 한다.

• 메모리 관리 : 모든 프로그램은 메모리에 올라가서 동작한다.

• H/W 관리 : 사용자가 직접 H/W에 접근하는 것을 막는다.

• File System 관리

Program

• 저장장치에 저장된 명령문의 집합체

• 저장 장치만 사용하는 수동적인 존재

Process

• 실행중인 프로그램

• 저장장치에 저장된 프로그램이 메모리에 올라갔을 대 프로세스라고 한다.

• 메모리, CPU, I/O 작업을 수행하는 능동적인 존재

Multi-Programming

• 메모리 관점

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

Multi-Processing

• CPU 관점

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

PCB(Process Control Block)

• 프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 갖고 있는 PCB를 만들고 저장한다.

• PCB들은 연결 리스트로 저장된다.

• 운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거한다.

Context Switching

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

  • 작업 과정에서 PCB의 내용(프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등)이 변경된다.

  Process의 생성

• OS가 부팅되고 0번 프로세스가 생성될 때 딱 한 번만 수행된다.
  → 그 이후에 생성되는 프로세스는 fork()를 사용하여 복사해서 사용된다.
  → 새로 생성하는 것보다 복사를 하는 것이 더 빠르기 때문

좀비 프로세스

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

Thread

• 프로세스 내에 존재하고, 1개 이상이 존재할 수 있다.

• 하나의 프로세스 내에 있는 쓰레드들은 프로세스의 PCB, Code, Data, Heap 영역을 공유한다.

• Stack은 공유하지 않고, 쓰레드 마다 하나씩 갖고 있다.

• OS에서 작업을 처리하는 단위이다.

Process vs Thread

안정성

• Process는 독립적이기 때문에 서로 영향을 받지 않는다.

• Thread는 하나의 Process를 공유하기 때문에 하나의 Thread에 이상이 생기면 다른 Thread에도 이상이 전파될 수 있다.
  ⇒ Process가 유리

속도와 자원

• 각각의 Process는 서로 고유한 자원을 갖는다.

  • 코드, 데이터, 힙, 스택 영역을 전부 따로 두고 있다.

  • Process간에 통신을 하려면 IPC를 사용해야 해서 오버헤드가 크고 속도가 느리다.

• 쓰레드는 하나의 Process의 자원을 스택 영역을 제외한 영역을 모두 공유하기 때문에 오버헤드가 느리다.

CPU Scheduling

목표

• 목표들을 전부 만족할 수는 없다.
  → 목표들에 따라 Trade-Off가 있기 때문
  ex) 처리량 ↑ ⇒ CPU 오래 할당, 응답시간 ↓ ⇒ 여러 프로세스에 CPU를 골고루 할당
  ⇒ 처리량과 응답시간 사이에 Trade-Off가 발생한다.

리소스 사용률

• CPU 사용률 높이기

• I/O 디바이스의 사용률 높이기

오버헤드의 최소화

• Context Switching시에 발생하는 오버헤드를 최소화하는 것

공평성

• 모든 프로세스에게 우선순위에 따라 공평하게 CPU가 할당되어야 한다.

처리량

• 같은 시간내에 더 많은 처리를 할 수 있게 하는 것

대기시간

• 작업을 요청하고 실제 작업이 실행되기 전까지 대기하는 시간이 짧은 것

응답시간

• 사용자의 요청이 얼마나 빨리 요청하는지

Retrospect

아쉬운 점

• 커리큘럼을 잘못 봐서 운영체제 쪽은 쉬는 날에 몰아서 들었다.

  • 커리큘럼을 명확하게 파악하고 당일에 들을 강의들을 정확히 정리해야겠다.

잘한 점

• 매일매일 빠지지 않고 강의를 들은 점

• 매일 들은 강의 내용을 요약/정리하고 그 주차의 내용들을 하나의 게시글로 정리한 것