[그림으로 쉽게 배우는 자료구조와 알고리즘] 배열 연결리스트 스택 큐 덱 해시테이블 셋

* 해당 포스팅은 그림으로 쉽게 배우는 자료구조와 알고리즘- by 감자 멘토님 강의를 수강후 작성하는 글 입니다. KEYWORD배열설명(한줄로): 연속된 메모리 공간에 데이터를 저장하는 선형 자료구조.시간복잡도:접근: O(1)삽입/삭제: O(n) (중간/앞에서), O(1) (끝에서)탐색: O(n) (정렬되지 않은 경우), O(log n) (정렬된 경우)유리한 케이스: 인덱스를 통해 데이터를 빠르게 접근할 때, 데이터 크기가 고정되어 있고 삽입/삭제가 자주 일어나지 않는 경우.연결리스트 (Linked List)설명(한줄로): 각 노드가 데이터와 다음 노드를 가리키는 포인터로 연결된 선형 자료구조.시간복잡도:접근: O(n)삽입/삭제: O(1) (노드를 알고 있을 때)탐색: O(n)유리한 케이스: 크기가 동적이고, 삽입/삭제가 빈번하게 일어나는 경우. 특히, 중간에 데이터가 삽입되거나 삭제될 때.스택 (Stack)설명(한줄로): 후입선출(LIFO, Last In First Out) 방식으로 데이터를 처리하는 자료구조.시간복잡도:접근: O(n)삽입/삭제: O(1) (top에서)탐색: O(n)유리한 케이스: 함수 호출 스택, 되돌리기 기능 등 후입선출 방식이 필요한 경우.큐 (Queue)설명(한줄로): 선입선출(FIFO, First In First Out) 방식으로 데이터를 처리하는 자료구조.시간복잡도:접근: O(n)삽입/삭제: O(1) (front와 rear에서)탐색: O(n)유리한 케이스: 주문 처리 시스템, 프린터 대기열 등 선입선출 방식이 필요한 경우.덱 (Deque, Double-Ended Queue)설명(한줄로): 양쪽 끝에서 삽입과 삭제가 가능한 자료구조.시간복잡도:접근: O(n)삽입/삭제: O(1) (양쪽 끝에서)탐색: O(n)유리한 케이스: 양방향에서 삽입/삭제가 자주 일어나는 경우. 예를 들어, 양쪽에서 데이터를 넣고 빼야 하는 데크나 스케줄링 시스템.해시테이블 (Hash Table)설명(한줄로): 해시 함수를 이용해 키를 인덱스로 변환하여 데이터를 저장하는 자료구조.시간복잡도:접근: O(1) (평균), O(n) (최악의 경우)삽입/삭제: O(1) (평균), O(n) (최악의 경우)탐색: O(1) (평균), O(n) (최악의 경우)유리한 케이스: 키-값 쌍으로 데이터를 저장하고 빠르게 검색할 때. 특히, 데이터의 크기가 클 때 빠른 검색이 필요할 경우.셋 (Set)설명(한줄로): 중복되지 않는 고유한 값들을 저장하는 자료구조.시간복잡도:접근: O(1) (해시셋인 경우)삽입/삭제: O(1) (평균), O(n) (최악의 경우)탐색: O(1) (평균), O(n) (최악의 경우)유리한 케이스: 중복이 없는 고유한 데이터를 관리할 때, 또는 값이 존재하는지 빠르게 확인할 때.

[미션] 인프런 워밍업 클럽 2기 CS - 1주차

운영체제1. 아래 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요? while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }폴링 방식 대신 인터럽트 방식을 사용하면 성능을 개선할 수 있습니다. 인터럽트는 특정 조건이 발생했을 때, CPU가 그 일을 처리하게 만드는 방식이기 때문에 예를 들어, 플레이어가 스킬을 사용했을 때만 인터럽트가 발생하도록 해서 CPU가 불필요하게 1초마다 체크하지 않도록 할 수 있습니다.2. 프로그램과 프로세스가 어떻게 다른가요?프로그램 : 저장된 명령어의 집합, 실행 파일 형태로 하드디스크나 메모리에 존재하지만 실행되지 않은 상태.프로세스 : 실행 중인 프로그램으로, 운영체제가 관리하는 실행 단위. CPU 시간과 메모리 같은 자원을 차지하며 활동 중임.3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍: 메모리에 여러 프로그램을 올려두고, CPU가 한 번에 하나의 프로그램을 처리하지만 빠르게 교체하며 실행하는 방식.멀티프로세싱: 여러 CPU 또는 코어가 동시에 여러 프로세스를 병렬로 실행하는 방식으로, 물리적으로 병렬 처리가 이루어짐.4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?운영체제는 프로세스 제어 블록(PCB, Process Control Block)을 사용해서 프로세스를 관리합니다. PCB는 운영체제가 각 프로세스의 상태와 관련된 중요한 정보를 저장하는 자료구조이며, 운영체제는 이 정보들을 기반으로 CPU 스케줄링, 메모리 관리, 입출력 관리를 수행합니다.5. 컨텍스트 스위칭이란 뭔가요?컨텍스트 스위칭은 운영체제가 한 프로세스의 실행 상태를 저장하고, 다른 프로세스의 상태를 복구해 CPU에서 실행을 전환하는 과정입니다. 이때 프로세스의 레지스터, 메모리, 스케줄링 정보를 저장하고 복구합니다.자료구조와 알고리즘1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.해시테이블 : 해시테이블은 학생의 고유한 식별자(예: 학번, 이름 등)를 키로 사용하여 해당 학생 정보를 저장하고 빠르게 검색할 수 있습니다. 평균적으로 O(1)의 시간 복잡도로 접근이 가능해서 대규모 학생 정보를 빠르게 처리할 수 있다는 장점이 있기때문에, 학번이나 이름으로 학생을 조회하는 작업에 적합하다고 생각합니다.2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐 : 주문은 들어온 순서대로 처리되기 때문에 FIFO(First In, First Out) 방식이 필요하기 때문에 FIFO 로 데이터가 처리되는 큐가 주문처리를 위한 자료구조 적합하다고 생각합니다.

[그림으로 쉽게 배우는 운영체제] 운영체제 프로세스 쓰레드 CPU 스케줄링(1)

* 해당 포스팅은 그림으로 쉽게 배우는 운영체제 - by 감자 멘토님 강의를 수강후 작성하는 글 입니다. KEYWORD- 운영체제: 하드웨어 자원을 관리하고 사용자와 시스템 간 인터페이스를 제공하는 소프트웨어.- 프로세스: 실행 중인 프로그램으로, CPU에서 작업이 진행되는 단위.- 프로그램: 실행 가능하지만 실행되지 않은 상태의 명령어 집합.- 쓰레드: 프로세스 내에서 실행되는 작은 작업 단위.- CPU: 명령어를 해석하고 연산을 수행하는 컴퓨터의 중앙 처리 장치.- 메모리: 데이터를 저장하고 프로세스가 작업을 수행할 때 사용되는 공간.- 애니악: 최초의 범용 전자 디지털 컴퓨터.- 펀치카드: 데이터를 입력하기 위해 구멍을 뚫어 정보를 표현하던 초기 입력 장치.- I/O 디바이스 컨트롤러: 입출력 장치와 시스템 간의 통신을 제어하는 장치.- 싱글스트림 배치시스템: 작업을 순차적으로 처리하는 초기 컴퓨터 운영 방식.- 시분할 시스템: 여러 사용자가 시스템을 동시에 사용할 수 있도록 자원을 할당하는 시스템.- 파일시스템: 데이터를 파일 형태로 저장하고 관리하는 시스템.- 유닉스: 멀티태스킹, 멀티유저 환경을 지원하는 운영체제.- 유니프로그래밍: 한 번에 하나의 프로그램만 실행하는 방식.- 멀티프로그래밍: 메모리에 여러 프로그램을 동시에 올려서 CPU가 번갈아 가며 처리하는 방식.- 멀티프로세싱: 여러 CPU가 동시에 여러 프로세스를 처리하는 방식.- 시분할처리: CPU 시간을 여러 작업에 나누어 사용하는 처리 방식.- 스와핑: 메모리에서 프로세스를 내보내고 다시 불러오는 과정.- 베이스 레지스터: 프로세스의 메모리 시작 주소를 저장하는 레지스터.- 커널: 운영체제의 핵심 부분으로 하드웨어와 소프트웨어 자원을 관리함.- 인터페이스: 시스템과 사용자 또는 다른 시스템 간의 상호작용을 위한 접점.- GUI: 그래픽을 통해 사용자와 컴퓨터가 상호작용하는 방식.- CLI: 명령어를 통해 사용자와 컴퓨터가 상호작용하는 방식.- 시스템 콜: 응용 프로그램이 운영체제의 기능을 요청할 때 사용하는 함수.- 드라이버: 하드웨어와 운영체제가 통신할 수 있도록 돕는 소프트웨어.- 그래픽카드: 그래픽 처리와 관련된 연산을 담당하는 하드웨어.- 폰노이만 구조: 프로그램과 데이터를 메모리에 저장하고 처리하는 컴퓨터 구조.- 메인보드: CPU, 메모리, I/O 장치가 연결된 컴퓨터의 중심 회로 기판.- 제어장치: CPU 내부에서 명령어의 실행을 제어하는 장치.- 산술논리 연산장치: CPU 내부에서 산술 및 논리 연산을 수행하는 장치.- 레지스터: CPU 내에서 데이터와 명령어를 일시적으로 저장하는 고속 메모리.- 프로그램 카운터: 다음에 실행할 명령어의 주소를 저장하는 레지스터.- 메모리 주소 레지스터: 메모리 내 데이터의 주소를 저장하는 레지스터.- 메모리 버퍼 레지스터: 메모리에서 읽거나 쓸 데이터를 임시 저장하는 레지스터.- 명령어 레지스터: 현재 실행 중인 명령어를 저장하는 레지스터.- RAM: 휘발성 메모리로, 데이터를 일시적으로 저장함.- ROM: 비휘발성 메모리로, 데이터를 영구적으로 저장함.- 바이오스: 컴퓨터 부팅 시 하드웨어 초기화와 운영체제 로딩을 관리하는 펌웨어.- 폴링방식: CPU가 장치의 상태를 주기적으로 확인하는 방식.- 인터럽트: 외부 신호로 CPU의 작업을 중단하고 다른 작업을 처리하게 하는 신호.- 인터럽트 서비스 루틴: 인터럽트 발생 시 실행되는 코드.- Code 영역: 프로그램의 명령어가 저장되는 메모리 영역.- Data 영역: 초기화된 전역 변수와 정적 변수가 저장되는 메모리 영역.- Heap 영역: 동적으로 할당된 메모리 공간.- Stack 영역: 함수 호출 시 생성되는 지역 변수와 함수 정보가 저장되는 메모리 영역.- 컴파일: 고급 프로그래밍 언어를 기계어로 번역하는 과정.- 어셈블리어: 기계어와 1:1 대응하는 저급 프로그래밍 언어.- 기계어: CPU가 직접 실행할 수 있는 이진 코드.- 링커: 여러 목적 파일을 결합해 실행 가능한 프로그램으로 만드는 도구.- 연결리스트: 노드가 서로 연결된 데이터 구조로, 각 노드는 데이터와 다음 노드의 참조를 포함함.- PCB: 프로세스 제어 블록으로, 프로세스에 대한 정보를 저장하는 데이터 구조.- 포인터: 메모리 주소를 가리키는 변수.- 컨텍스트 스위칭: CPU가 한 프로세스에서 다른 프로세스로 전환할 때 발생하는 작업.- 프로그램 카운터: 현재 실행 중인 명령어의 다음 명령어 주소를 가리키는 레지스터.- 부모프로세스: 다른 프로세스를 생성하는 프로세스.- 자식프로세스: 부모 프로세스에 의해 생성된 프로세스.- fork 함수: 새로운 프로세스를 생성하는 시스템 호출.- exit 함수: 프로세스가 실행을 종료할 때 호출하는 함수.- 좀비 프로세스: 실행이 종료되었으나 부모 프로세스가 회수하지 않은 프로세스.- IPC: 프로세스 간 통신으로, 프로세스 간 데이터를 주고받는 방법.- TCB: 쓰레드 제어 블록으로, 쓰레드의 실행 상태를 저장하는 데이터 구조.- 프로세스와 쓰레드 차이: 프로세스는 독립된 메모리 공간을 갖고, 쓰레드는 프로세스 내 자원을 공유함.- CPU Burst: 프로세스가 CPU를 사용하는 시간.- I/O Burst: 프로세스가 I/O 작업을 수행하는 시간.- 큐 자료구조(Queue): FIFO 방식으로 데이터를 저장하고 처리하는 자료구조.- CPU 스케줄링: 여러 프로세스 간에 CPU 시간을 배분하는 방식.- 생성상태: 프로세스가 생성된 초기 상태.- 준비상태: 프로세스가 실행 준비가 된 상태.- 대기상태: 프로세스가 입출력 작업을 기다리는 상태.- 실행상태: 프로세스가 CPU에서 실행 중인 상태.- 완료상태: 프로세스가 실행을 완료한 상태.- 스케줄러: CPU 자원을 프로세스에 할당하는 운영체제의 구성 요소.- 오버헤드: 시스템 자원 사용 시 발생하는 추가 비용.- 스케줄링 알고리즘: CPU 시간을 프로세스에 할당하는 방법을 결정하는 알고리즘.- FIFO (First In, First Out): 먼저 들어온 데이터가 먼저 나가는 방식으로, 큐 자료구조에서 사용하는 원칙.