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

강의 요약

자료구조

• 어떤 알고리즘의 성능의 지표로 빅오표기법($O(n)$)을 사용한다.

• 배열(array)

  • 동일한 자료형 요소들의 모임

  • 메모리의 연속된 공간에 위치한다

  • 데이터의 참조의 시간복잡도 $O(1)$

  • 데이터 추가 및 삭제 시간복잡도 $O(n)$

• 연결리스트(linked list)

  • 데이터와 다음 노드의 주소를 저장하는 포인터를 가진 노드들이 일자로 연결된 자료구조

     

  • 각 노드들이 랜덤한 공간에 위치해도 된다.

  • 데이터의 참조의 시간복잡도 $O(n)$

  • 데이터 추가 및 삭제 시간복잡도 $O(1)$

• 스택(stack)

  • 후입선출(LIFO, Last In First Out)

• 큐(queue)

  • 선입선출(FIFO, First In First Out)

• 덱(deque)

  • 양방향으로 데이터의 접근 및 처리가 가능한 자료구조

• 해시테이블(hashtable)

  • 키(key)와 값(value)을 매핑시켜 저장하는 자료구조

  • 키를 해시함수를 통해서 변환하여, 변환된 값으로 값을 참조한다.

  • 해싱(hashing) : 임의의 크기의 값을 해시 함수를 통해 고정된 크기의 값으로 변환하는 작업

  • 해시 충돌(collision) : 다른 키로부터 동일한 해시 함수의 결과값이 나오는 경우

    • chaining 기법 : 해시테이블의 공간을 연결리스트 자료구조를 사용하여 존재하는 데이터 뒤에 연결시킨다.

    • open addressing : 해시 함수의 반환값의 위치에 이미 데이터가 있는 경우 다른 해시 코드를 사용하는 것

  • 데이터의 CRUD 작업에 대해 $O(1)$의 시간복잡도를 갖는다. (해시충돌이 없는 경우)

  • 메모리를 많이 차지하고, 해시 충돌 시 다른 자료구조를 사용하거나 좋은 해시함수를 구현해야 함

• 셋(set)

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

  • 순서도 고려되지 않는다.

학습 내용 정리

[배열, linked list](https://github.com/yeeuniii/TIL/blob/main/DataStructure/%EB%B0%B0%EC%97%B4%EA%B3%BC-%EB%A7%81%ED%81%AC%EB%93%9C%EB%A6%AC%EC%8A%A4%ED%8A%B8.md)

[stack, queue, deque](https://github.com/yeeuniii/TIL/blob/main/DataStructure/%EC%8A%A4%ED%83%9D-%ED%81%90-%EB%8D%B1.md)

[hash table](https://github.com/yeeuniii/TIL/blob/main/DataStructure/%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94.md)

[set](https://github.com/yeeuniii/TIL/blob/main/DataStructure/Set.md)

운영체제

프로세스와 스레드

프로세스는 메모리에 프로그램이 적재되어 운영체제의 관리하에서 실행되는 프로그램이다.

프로세스가 생성되면 PCB가 생성되고, 준비 상태(Ready)가 되어 운영체제로부터 CPU를 할당받기를 기다린다.
CPU를 할당받으면 실행 상태(Running)가 된다.
이때 CPU 점유 시간을 초과하면 운영체제로부터 CPU 제어권을 빼앗고 다시 대기 상태(Ready)가 되고,
입출력 작업이 요청되면 대기 상태(Waiting)가 되어 CPU 스케줄링의 대상에서 제외된다.
입출력 작업 완료 시, 다시 대기 상태(Ready)가 된다.
모든 작업이 완료되면 프로세스의 자원(PCB, 메모리 등)이 회수된다.

프로세스는 고유한 메모리와 PCB를 갖기 때문에 프로세스의 수에 비례하게 메모리도 증가한다.
따라서 프로세스 내에서 스택을 제외한 메모리와 PCB를 공유하는 스레드를 사용하여 멀티태스킹을 구현한다.
스레드는 가볍지만, 메모리를 공유하기 때문에 동기화 문제가 발생할 수 있다.

CPU 스케줄링

운영체제가 여러 프로세스에 합리적으로 CPU를 할당 / 해제하는 행위

CPU 스케줄링의 성능은 평균 대기 시간에 따라 결정된다.

• FIFO

  • 들어온 순서대로 작업을 처리한다.

  • 하나의 프로세스의 작업이 완료되어야 다음 프로세스를 실행할 수 있다.

• SJF

  • 프로세스의 작업 시간을 정확히 예측할 수 없다.

  • Burst Time이 큰 프로세스는 무한 대기가 발생할 수 있다.

• RR(Round Robin)

  • time slice를 기반으로 모든 프로세스에 공평하게 CPU를 할당한다.

  • time slice가 너무 작을 경우 잦은 컨텍스트 스위칭에 의한 오버헤드가 발생할 수 있다.

• MLFQ(Multi Level Feedback Queue)

  • 프로세스의 우선순위를 줘서(프로세스마다 time slice를 다르게 줌) CPU 처리율과 I/O 처리율의 균형을 제공한다.

     

   

[1주차 학습 내용 정리](https://github.com/yeeuniii/TIL/blob/main/OS/%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%89%BD%EA%B2%8C-%EB%B0%B0%EC%9A%B0%EB%8A%94-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C.md)

회고

강의에서 이해가 되지 않거나 부족한 부분들을 더 찾아보고 채워나가면서 생각보다 학습 시간이 오래 걸렸다. 이렇게 학습함으로써 확실히 이해하고 머릿속에 남는 것 같아 후회되지는 않지만, 그럼으로써 매일매일 계획된 스케줄대로 학습하기가 어려워진 것 같다.

자료구조의 경우, 이전 알고리즘 스터디에서 학습했던 것과 비슷한 부분이 많아 리마인드하는 느낌으로 반복 학습해줬다. 그래도 이전과 다르게 연결리스트로 자료구조를 구현하면서 또 다른 방식을 알아갈 수 있어 좋았던 것 같다.

운영체제는 진짜 42서울에서 배웠던 것은 헛이었다... 운영체제의 역사, 컴퓨터 구조와 같은 완전 기본부터 학습을 시작하니 다음께 다다 이해되는 느낌.. 이때까지 OS는 주먹식 암기로 학습했었는데 이해를 기반으로 학습되니 운영체제의 기반이 잡힌 기분이다! 그러면서 이때까지 조금씩 주워듣고 겉핥기로만 알고 있던 부분을 플러스알파로 학습하면서 지식을 탄탄히 채워나갈 수 있었다!! 스터디 고민했었는데 운영체제의 개념을 정리할 수 있는 시간이 되었다는 점에서 스터디 신청이 하나도 후회되지 않는다!

다만 이번주는 CS 학습에 좀 끌려다니듯이 살았는데, 다음주부터는 일정 학습시간을 정해두고 그날 학습할 것은 그날 끝내도록하자! 미션과 발자국을 이렇게 시간 임박해서 작성하는 불상사를 만들지 않도록... 다음주도 화이팅!