1주차 학습 내용 - 발자국

자료구조 & 알고리즘

자료구조

• 데이터가 어떤 구조로 저장되고 어떻게 사용되는지 나타낸 것

  • 예를들어 데이터를 변수에 담아 처리하는 평균을 구하는 식과 배열에 담아 평균을 구하는 식이 다른 로직으로 돌아가는 것 처럼?

알고리즘

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

• 같은 자료구조에도 다양한 알고리즘(풀이법)이 존재하기 때문에 적합하다고 판단되는 것을 골라 사용하면 됨.

시간복잡도

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

• 표기법은 빅오 표기법으로 사용하고 반복문이 한번 돌면 O(n)이라고 함. O(n) -> O(n²)

연결리스트

• 데이터를 저장하는 선형 자료구조, 각 요소(Node)가 다음 요소를 가리키는 방식으로 연결된 구조

  • Node의 구성요소: data(자신), next(다음)

• 장점: 아무 곳에 데이터를 생성하고 연결만 해주면 되기때문에 배열의 단점을 극복함

• 단점: 배열은 인덱스를 통해 O(1)로 즉시 접근 가능하지만, 연결 리스트는 head부터 순차적으로 접근해야 하므로 O(n)의 탐색 시간이 필요함

   

스택(FILO)

• 먼저 들어간 데이터가 나중에 나오는 자료구조

   

큐(FIFO)

• 먼저 들어간 데이터가 먼저 나가는 자료구조

   

덱

• 데이터의 삽입과 제거를 자유롭게 할 수 있는 자료구조, 쉽게말해 스택 + 큐 같은 느낌

해시테이블

• Key-Value(키-값) 쌍으로 데이터를 저장하는 자료구조

• 장점: 빠른 데이터 읽기, 삽입, 삭제

• 단점: 메모리를 많이 차지함

   

셋 

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

운영체제

커널

• 운영체제의 핵심

• 프로세스와 메모리, 저장장치를 관리하는 핵심적인 기능 담당

• 사용자는 커널에 접근하기 위해 인터페이스(GUI, CLI)를 통해 접근 가능함.

CPU

• 제어 장치, 산술논리 연산장치, 레지스터로 나뉨

폴링과 인터럽트

• 폴링은 CPU가 하드웨어 쪽에서 어떤 일이 바로 발생하는지 인지할 수 없어서 입출력 명령이 왔는지 주기적으로 확인하여 작업을 완료하는 방식

• 인터렙트는 이런 불필요하게 확인하는 폴링의 단점을 보완해서 CPU에서 입출력 명령을 내리고 다른일을 하다가 입출력이 완료 되었다는 신호를 받고 작업을 완료하는 방식

프로그램과 프로세스

• 프로그램은 저장장치에 저장된 명령문의 집합체( 앱, .exe )

• 프로세스는 실행중인 프로그램(하드디스크에 저장된 프로그램이 메모리에 올라갔을 경우 실행중이라고 함)

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

• 멀티프로그래밍은 메모리로 여러개의 프로그램을 올려놓고 사용하는 것

• 멀티프로세싱은 시분할 처리로 CPU가 각각의 프로세스를 짧은 시간 동안 교대로 실행하는 것

컨텍스트 스위칭

• 프로세스를 동작하다가 다른 프로세스를 동작시키기 위해 현재 프로세스를 저장하고 다른 프로세스로 바꾸는 과정

• 현재까지 진행된 CPU의 레지스터 값을 동작했던 프로세스에 저장하고, 나중에 다시 그걸 가지고 이어서 작업함.

CPU 스케줄링

• 운영체제가 여러 프로세스의 실행을 기다릴 때, CPU를 어떤 순서와 방식으로 할당하고 해제할지를 결정하는 과정

FIFO

• 가장 먼저 들어온 프로세스를 먼저 처리하는 방식

• 단점: P1이 실행되는 동안 P2, P3가 기다려야해서 대기 시간 지며 CPU 사용률이 떨어짐.

SJF

• 실행 시간이 제일 짧은 프로세스를 먼저 처리하는 방식

• 단점: 프로세스가 얼마나 실행될지 알 수 없음, 실행시간이 긴 프로세스는 오랫동안 실행되지 않을수도 있음.

RR

• 모든 프로세스에게 공평하게 CPU 시간을 할당하는 방식

• 단점: 타임 슬라이스가 너무 길면 굉장히 끊기고, 너무 짧으면 컨텍스트 스위칭이 자주 일어나며 불필요한 처리를 해야함. 그래서 적절한 타임슬라이스를 지정해줘야 함.

MLFQ

• 여러 개의 큐를 사용하여 우선순위를 동적으로 변경하는 방식

• 짧은 작업은 낮은 타임슬라이스를 주고, 긴 작업은 높은 타임슬라이스를 부여함. (현대에서 제일 많이 사용)

1주차 회고

• 비전공자여서 CS지식은 완전 0이라 복습을 자주 해야할 것같다고 생각했습니다.

• 감자 강사님께서 강의는 지루하지 않고 이해가 편하도록 노력해서 만드신게 눈에 보였음(각종 더빙, 캐릭터들), 사물궁이라는 유튜버가 있는데 그 방식과 굉장히 흡사해서 재미있게 볼 수 있음.

   

• 저같은 경우는 익숙하지가 않아서 한번 본다고 머리에 잘 들어오진 않아서, 대중교통 타거나 심심할때마다 반복해서 보면 자연스럽게 조금씩 이해가 되는거같아서 좋았습니다.