인프런 워밍업 클럽 스터디 3기 - 자료구조와 알고리즘 -3주차 미션-

지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블정렬서로 인접한 두 요소를 비교하여 정렬하는 알고리즘. 인접한 2개의 요소를 비교해서 교환한다. 일반적으로 데이터의 교환이 이동 작업보다 복잡하다. 시간 복잡도 : O(n^2) 공간 복잡도 : O(1) : 한 개의 임시 변수 필요 안정적 정렬 방식(안정적 정렬이란 중복 된 값을 가진 요소의 순서가 정렬 후에도 유지되는 것을 말한다.) 배열이 거의 정렬 된 상태라면 향상된 버블정렬 알고리즘으로 최선의 시간 복잡도는 O(n)이 된다. 선택정렬 배열에서 최솟값을 찾아 맨 앞부터 둔다. 일반적으로 데이터의 교환이 이동 작업보다 복잡하다.시간 복잡도 : O(n^2)공간 복잡도 : O(1) : 한 개의 임시 변수 필요서로 떨어져 있는 요소를 교환하기 때문에 안정적 정렬 방식이 아니다.(중복 값이 있을 시 원소의 순서가 바뀜) 삽입정렬삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 알고리즘삽입 하려고 선택한 값을 임시변수에 저장한다.내부 반복문은 삽입 위치를 찾을 때까지 임시 변수의 값과 비교한다.삽입 정렬의 시간 복잡도는 O(n^2)로 버블 정렬과 같지만, 실제 성능은 버블 정렬보다 조금 낫다.카드 게임에서 카드를 배열하는 방법과 비슷하다.시간 복잡도 : 최악의 경우 -> O(n^2), 최선의 경우 -> O(n)공간 복잡도 : O(1) : 한 개의 임시 변수 필요안정적 정렬 방식(안정적 정렬이란 중복 된 값을 가진 요소의 순서가 정렬 후에도 유지되는 것을 말한다.) 위 버블 / 선택 / 삽입 정렬은 이해와 구현이 쉽다는 장점을 가지고 있지만 시간 복잡도가 O(n²)으로 성능이 좋지 않다는 단점을 가지고 있습니다. 퀵정렬퀵 정렬은 가장 빠른 정렬 알고리즘 중 하나로 널리 사용된다. 그룹을 나누는 기준을 피벗(pivot)이라 한다.피벗은 마음대로 선택할 수 있으며, 피벗은 어느 그룹에 속해도 상관없다. 퀵정렬은 배열을 나누어 해결하는 과정을 반복하기 때문에 시간 복잡도는 O(n log n)이다.피벗의 선택에 따라 최악의 경우(예를 들어 1:9)로 나눠지는 경우 시간 복잡도는 O(n^2)이다.퀵정렬을 피벗을 기준으로 파티션을 나누기 위해 재귀 호출해서 코드를 작성한다. 퀵 정렬/ 병합 정렬은 재귀의 개념을 이용하기 때문에 이해와 구현이 비교적 어렵다는 단점을 가지고 있으나 시간 복잡도가 O(nlogn)으로 성능이 좋다는 장점을 가지고 있습니다. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.메모이제이션은 순수 함수 호출을 최적화하고 중복 계산을 줄이며 성능을 향상시키는 방법을 제공함으로써 연산 속도는 빠르고 하향식 접근 문제에 대해 빠르게 풀이할 수 있다는 장점이 있지만, 캐시를 유지하면 이전의 모든 입력과 출력을 유지해야 하므로 메모리 사용량도 증가한다. 그러므로 메모리 부족한 시스템에서는 적절치 않다.타뷸레이션은 문제를 부분 문제로 나눈 다음 작은 문제부터 차례대로 그 결과를 테이블에 저장하는 방식을 말한다. 이렇게 저장된 테이블을 기반으로 큰 문제의 해결을 단계적으로 구축한다.상향식 계산 방식으로 계산에 필요하지 않을 수도 있는 값도 미리 계산해 테이블에 저장한다. 계산되어 저장된 값을 필요할 때 사용해 빠르게 계산한다.메모이제이션은 재귀로 쉽게 구현이 가능한 문제에 대해 이점을 가지고 있지만 메모리의 사용이 크다는 단점이 있기 때문에, 결국 메모리가 부족한 시스템에서 적절치 않다고 생각한다.

인프런 워밍업 클럽 스터디 3기 - CS 전공지식(운영체제) -3주차 미션-

운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.1. 휘발성 메모리✔ 레지스터CPU 내부에서 처리할 명령어나 연산의 중간 결과값 등을 일시 저장하는 임시 기억장치.범용 레지스터, 세그먼트 레지스터, 포인터 레지스터, 인덱스 레지스터, 플래그 레지스터가 있음.CPU가 연산해야 할 데이터를 RAM에서 가져와 여기에 저장한 후에 연산을 시작함. ✔ 캐시 메모리(Cache Memory)메인 메모리(RAM)은 레지스터보다 속도 면에서 느리기 때문에 메인 메모리에서 필요할 것 같은 데이터를 미리 캐시에 저장성능의 이유로 여러 개를 둔다.✔ 메인 메모리(RAM)실제 운영체제와 프로세스들이 올라가는 공간이자 실행중인 프로그램만 올린다.2 비휘발성 메모리✔ 보조저장장치(HDD, SSD) 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?사용자 영역이 운영체제 영역으로 침범하는 것을 막기 위해 메모리 관리자는 사용자가 작업을 요청할 때마다 경계 레지스터의 값을 벗어나는지 검사하고, 만약 경계 레지스터를 벗어나는 작업을 요청하는 프로세스가 있으면 그 프로세스를 종료함 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?1. 가변 분할 방식(세그멘테이션)프로세스가 크면 메모리도 크게 할당한 프로세스가 메모리에 연속된 공간에 할당되기 때문에 연속 메모리 할당이라 부른다.✔ 장점내부 단편화 현상 없음.✔ 단점외부 단편화 발생3MB 프로그램과 2MB 프로그램이 종료되어 공간이 발생되어도 5MB 프로그램이 들어가지 못한다.2. 고정 분할 방식(페이징)프로세스의 크기와는 상관없이 메모리를 정해진 방식으로 할당한 프로세스가 메모리에 분산되어 할당되기 때문에 비연속 메모리 할당이라 부른다.(5MB 프로그램을 2MB 고정 분할 메모리에 저장 시키려면 2/ 2/ 1 로 분리해야함)✔ 장점구현이 간단하고 오버헤드가 적음✔ 단점작은 프로세스도 큰 영역에 할당되어서 공간이 낭비되는 내부 단편화가 발생 CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱물리 메모리 공간이 한정되어 있기 때문에 일어나는 현상입니다. 물리 메모리 크기를 늘려서 해결할 수 있고, 프로세스 실행시간 내에 page fault의 발생빈도에 따라 페이지 크기를 조정하거나 워킹셋을 활용하여 해결할 수 있습니다.워킹셋은 지역성 이론에 따라 최근 가장 많이 조회된 페이지들의 집합을 저장하는 기법이다. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?하드 디스크가 없으면 운영체제는 실행시키지 못하고 컴퓨터의 기본적인 부팅만 가능하다.부팅을 시킬 순 있지만, 운영체제를 실행시키지 못하기 때문에 작업을 수행할 수는 없다. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일 시스템은 효율적 관리를 위해 빈 공간을 모아둔 free block list를 가지며 파일 삭제시 파일 시스템은 파일의 모든 정보를 지우는 것이 아닌, 파일 테이블의 헤더만을 삭제하고 블럭을 free block list에 추가한다.이를 통해 사용자는 파일이 삭제된 것 처럼 느끼지만 사용했던 블록의 데이터는 그대로 남아 있어, 새로운 파일이 해당 블록을 덮어쓰기 전까지는 이전 데이터를 포렌식으로 복구할 수 있다.

인프런 워밍업 클럽 스터디 3기 - 3주차 발자국

운영체제1⃣ 개요프로그래머는 프로세스가 메로리에 어느 위치에 올라가는지 신경쓰지 않고 0X0번지에 들어간다고 생각하고 프로그래밍 하면 된다.프로세스(사용자)는 메모리 관리자를 통해 메모리에 접근가상 메모리는 물리 메모리 크기와 CPU 비트수로 결정( 만약 32bit CPU인 경우, 2³² 주소값이 되고 4GB 정도 된다.)32bit CPU를 가진 가상 메모리(4GB)가 4GB 프로세스 5개를 실행시키려면 어떻게 해야할까?물리 메모리 내용의 일부를 하드디스크에 스왑영역으로 옮기고 처리가 필요할 때 물리 메모리로 가져와 실행시키기 때문에 이를 다 실행시킬 수 있다.메모리 관리 기법의 하나로 컴퓨터가 실제로 이용 가능한 메모리 자원을 추상화하여 이를 사용하는 사용자들에게 큰 메모리로 보이게 하는 것이다.✔ 동적주소할당 (Dynamic Address)메모리 관리자는 메모리와 하드디스크 내 스왑영역을 합쳐 가상주소 대신 물리주소로 변환하는 것을 동적주소할당이라 한다.이를 통해 프로세스는 사용자 데이터를 물리 메모리에 배치할 수 있다.2⃣ 세그멘테이션(배치 정책)의미 단위인 세그먼트(Segment)로 나누어 메모리에 할당하는 방법이다. 이 때 세그먼트는 크기가 가변적이고 논리적인 단위인데, 이 방식은 프로그램의 크기가 달라지는 경우 유연하게 대처가 가능하다.사용자, 프로세스 CPU가 바라보는 주소는 논리주소3⃣ 페이징(배치 정책)메모리를 할당할 때 정해진 크기의 페이지로 나눈다.일정한 크기로 나누었기 때문에 관리도 쉽고, 외부 단편화 현상이 발생하지 않는다. (✳ 내부 단편화 발생)✔ 페이지사용자, 프로세스가 바라보는 주소공간인 논리주소공간을 일정한 크기로 나눈 것.✔ 프레임메모리에 실제 주소공간인 물리주소공간을 일정한 크기로 나눈 것.3.1 세그멘테이션과 페이징의 차이점세그멘테이션은 프로세스마다 크기가 달라 크기를 표현하는 Bound Address를 가지고 있지만페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 것이 필요하지 않다,이 때문에 페이징은 내부 단편화가 발생하고, 세그멘테이션은 외부단편화가 발생한다.정해진 페이지의 크기보다 프로세스의 크기가 작으면 그만큼 공간이 낭비되는데 이를 내부 단편화라고 한다.논리적인 영역으로 나눌 수 없다.세그멘테이션은 논리적인 영역인 코드, 데이터, 힙, 스택 영역으로 나눌 수 있지만페이징은 정해진 크기인 페이지로 나누기 때문에 논리적인 영역을 나눌 수 없다. 3.2 메모리에 여러 개의 프로세스가 올라오는 멀티 프로그래밍 환경에서는 어떻게 동작하는가(1) 가변 분할 방식(세그멘테이션)프로세스가 크면 메모리도 크게 할당한 프로세스가 메모리에 연속된 공간에 할당되기 때문에 연속 메모리 할당이라 부른다.✔ 장점내부 단편화 현상 없음.✔ 단점외부 단편화 발생3MB 프로그램과 2MB 프로그램이 종료되어 공간이 발생되어도 5MB 프로그램이 들어가지 못한다.(2) 고정 분할 방식(페이징)프로세스의 크기와는 상관없이 메모리를 정해진 방식으로 할당한 프로세스가 메모리에 분산되어 할당되기 때문에비연속 메모리 할당이라 부른다.(5MB 프로그램을 2MB 고정 분할 메모리에 저장 시키려면 2/ 2/ 1 로 분리해야함)✔ 장점구현이 간단하고 오버헤드가 적음✔ 단점작은 프로세스도 큰 영역에 할당되어서 공간이 낭비되는 내부 단편화가 발생(3) 버디 시스템(가변 + 고정)2의 승수로 메모리를 분할하여 메모리를 할당하는 방식전체 메모리 영역을 하나의 프로세스가 올라갈 수 있을 정도로 2의 승수로 나눠서 분할최소한의 내부 단편화, 간단한 메모리 합치기가 가능4⃣ 페이지드 세그멘테이션(배치 정책)세그멘테이션은 보호와 공유에 효율적이고, 페이징은 외부 단편화 문제를 해결할 수 있다. 이 두 가지를 합쳐서 나온게 세그먼트를 페이징 기법으로 나누는 페이지드 세그멘테이션이다.4.1 메모리 접근 권한메모리의 특정 번지에 부여된 권한코드 영역프로그램 그 자체이기 때문에 읽기/실행 권한이 가능하다.데이터 영역일반변수, 전역변수, 상수로 선언한 변수가 저장한다. 읽기(쓰기) 권한은 있으나 실행 권한은 없다.힙 영역읽기/쓰기 권한 O / 실행 권한 X스택 영역읽기/쓰기 권한 O / 실행 권한 X메모리 접근 권한에 대한 검사 가상주소 → 물리주소로 변환될 때 마다 일어나는데, 만약 권한을 위반한다면, 에러를 발생 시키고 종료시킨다.2. 페이지드 세그멘테이션세그멘테이션 테이블은 세그먼트의 번호, 시작 주소, 세그먼트의 크기를 엔트리로 갖는다.세그멘테이션 테이블에서권한 비트 추가Base Address → 페이지 넘버 : 이름 변경Bound Address → 페이지 개수 : 이름 변경논리 주소 0x12300번지 접근 요청시,논리 주소를 이용해 몇 번 세그먼트인지 알아냄.세그멘테이션 테이블에서 1번 인덱스를 참조해당 세그먼트가 메모리 접근 권한을 위반하는지 검사 ✔ 접근 권한 위반할 시, 프로세스가 종료 ✔ 위반 하지 않으면, 페이지 넘버와 페이지 개수 가져옴페이지 넘버로 페이지 테이블에 접근해서 프레임 번호 가져옴논리 주소에서 오프셋을 알아내고오프셋 + 프레임 번호 위치 = 물리 주소물리 메모리에 해당 프레임이 없다면, 스왑 영역에서 물리 메모리로 가져온다.✔ 단점물리 메모리에 접근 하기 위해서 메모리에 접근을 2번 해야한다.세그멘테이션 테이블 참조할 때페이지 테이블 참조 할 때 알고리즘삽입정렬개념배열을 정렬된 영역과 정렬되지 않은 영역으로 나눈다.삽입정렬은 정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내 적절한 위치에 삽입하는 알고리즘이다.가장 첫 번째 숫자 3은 정렬되어있고, 나머지 숫자들은 정렬되지 않았다고 가정하면먼저 정렬되지 않은 영역의 첫 번째 원소인 7을 정렬된 영역에 삽입합니다.삽입할 원소인 숫자 7과 정렬된 영역의 마지막 원소(숫자 3)를 비교합니다.이 때, 숫자 3과 숫자 7을 비교하는데, 7은 3보다 크므로 바뀌지 않고 그대로 유지됩니다.그 다음 (b)에서 다시 정렬된 영역 3,7 그리고 나머지 정렬되지 않은 영역을 나눕니다.이제 정렬되지 않응 영역의 첫 번째 원소인 2를 정렬된 영역의 가장 뒤에 있는 원소 (숫자 7)부터 역순으로 비교합니다.7은 2보다 크기 때문에 7을 오른쪽 인덱스(숫자 2의 인덱스)에 덮어써줍니다. 그리고 숫자 2를 인덱스 1번째에 삽입합니다. ( 3 2 7 5 1 4 )그 다음 2를 정렬된 영역의 그 다음 원소인 3과 비교해줍니다.3은 2보다 크기 때문에 3을 오른쪽 인덱스(인덱스 1번째)에 덮어써줍니다. 그리고 숫자 2를 인덱스 0번째에 삽입합니다. (2 3 7 5 1 4) 운영체제1⃣디멘드 페이징(가져오기 정책)1. 지역성 이론공간의 지역성현재 위치와 가장 가까운 데이터에 접근할 확률이 높은 것시간 지역성최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높은 것지역성 이론은 조만간 쓰일 데이터만 메모리에 올리고 당분간 사용하지 않을 데이터는 하드디스크의 스왑 영역에 보내 성능을 향상 시키는 것, 이를 디멘드 페이징이라 한다.2. 메모리 계층 구조✔ 레지스터(CPU 한 사이클)같은 방에 상자를 가지러 가는 것✔ 캐시( n ~ nnn 사이클)같은 건물에 있는 상자를 가지러 가는 것✔ 메인메모리(RAM) (nnn 사이클)같은 동네에 있는 상자를 가지러 가는 것✔ 보조기억장치(HDD, SSD) (nnnnnn 사이클)상자를 가지러 달나라까지 가는 것디멘드 페이징은 스왑영역을 보조저장장치에 저장하는데 성능향상을 위해선 스왑영역으로 데이터를 이동시키는 것을 최소화 해야한다.✳ 스왑인(Swap in)가상 메모리의 크기는 물리 메모리 크기에 스왑영역을 합친 것스왑영역에서 물리 메모리로 데이터를 가져오는 것을 스왑인이라한다.스왑아웃(Swap out)물리 메모리에서 스왑영역으로 데이터를 보내는 것✔ 페이지 테이블 엔트리(PTE)가상주소가 주어지면 메모리 관리자는 페이지 테이블을 참조해서 스왑영역의 위치를 알아낸다.이를 위해 페이지 테이블에는 여러가지 비트가 존재한다.이 페이지 테이블의 한 행을 이루고 있는 것이 페이지 테이블 엔트리(PTE)이다.유효 비트(Valid Bit)현재 해당 page에 접근 가능한지 여부를 알려준다항상 모든 page가 물리 메모리에 존재하는 것은 아니고, 대부분 보조기억장치의 스왑영역에 존재한다.그래서 유효 비트는 현재 page가 메모리에 적재되어있는지, 보조기억장치에 있는지 알려주는 bit이다.만약 메모리에 적재되어있다면 유효 비트가 1, 그렇지 않다면 0으로 표기된다.보호 비트 ( Protection Bit )보호 비트는 해당 page가 읽기.쓰기가 모두 가능한 page인지, 혹은 읽기 전용인지를 나타낸다.보호 비트가 0인 경우, 해당 page는 읽기 전용이고, 1일 경우 읽기.쓰기가 모두 가능하다.참조 비트(Reference Bit)CPU가 page에 접근한 이력이 있는지의 여부를 나타낸다.메모리 적재 이후의 CPU가 읽기 또는 쓰기를 한 page는 참조 비트가 1로 설정되고, 적재 이후 한 번도 읽기.쓰기 한 이력이 없는 page는 0으로 유지된다. 알고리즘병합 정렬개념 대표적인 분할 정복(Divide and Conquer) 알고리즘 중 하나로, 리스트를 반으로 나눈 뒤 각각을 재귀적으로 정렬하고, 정렬된 두 개의 리스트를 합쳐서 정렬된 하나의 리스트를 만드는 알고리즘이다. 분할(Divide)입력 리스트를 같은 크기의 두 개의 부분 리스트로 분할합니다. 이때 분할은 리스트의 중간 지점에서 수행됩니다.정복(Conquer)각 부분 리스트를 재귀적으로 병합정렬을 이용해 정렬합니다. 이 과정은 입력 리스트의 크기가 충분히 작아질 때까지 반복됩니다.병합(Merge)정렬된 두 부분 리스트를 하나의 정렬된 리스트로 병합합니다.0개 요소, 1개 요소 배열이 이미 정렬되어 있다는 점을 활용합니다.배열을 더 작은 배열 나누는 방식입니다.분할 정복 알고리즘이라 알려진 방식이고, 더 큰 배열을 나누고, 더 작은 하위 배열로 정렬합니다.배열의 요소가 0 또는 1개가 될 때까지 반복합니다.계속 분할한 다음 다시 병합시킵니다. 장점앞선 정렬들 보다 성능이 훨씬 좋다단점이해와 구현이 어렵다. 운영체제 1. 페이지 교체프로세스는 데이터 접근을 위해 메모리를 참조하는데 해당 데이터가 메모리에 없으면 Page Falut가 발생한다.필요한 페이지를 물리 메모리에 적재해야할 때, 만약 물리 메모리가 가득 차 있는 상태라면 특정 페이지는 page out 해야한다.대표적인 페이지 교체로는 FIFO 페이지 교체, 최적 페이지 교체, LRU 페이지 교체, LFU 페이지 교체, MFU 페이지 교체 등이 있다.1.1 FIFO 페이지 교체가장 간단하고 직관적인 페이지 교체 방법.먼저 물리 메모리에 들어온 순으로 페이지 교체가 이루어진다.이해하기 쉽고 구현도 쉽지만, 단순히 먼저 들어온 페이지가 더 이상 사용되지 않는다는 것은 아니기 때문에, 활발하게 사용되는 페이지를 교체해서 page fault를 발생 빈도를 높힐 수도 있다.✳ 빌레이디의 모순 (Belady’s Anomaly)FIFO에서만 발생하는 역설이다.일반적으로 페이지의 frame의 수를 늘리면, 메모리에 적재될 수 있는 페이지의 수가 늘어나기 때문에, page fault 발생 확률이 감소한다.그러나, FIFO 페이지 교체에서는 단순히 오래된 페이지를 교체하기 때문에, 산술적으로 오히려 더 많은 page fault가 발생하게 된다.즉, 성능 개선을 위해 frame의 수를 늘렸지만, 반대로 page fault가 더 자주 발생하여 성능이 악화되는 일이 일어난다.1.2 최적 페이지 교체(Optimal Page Replacement)앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식.이론적으로 최적 성능을 보장하지만, 실제로는 알고리즘 구현이 어려워 대체로 사용되지 않는다.1.3 LRU 페이지 교체 (LRU Page Replacement)LRU : Least Recently Used가장 오랫동안 사용되지 않을 페이지를 찾는 것이 아니라, 결과적으로 가장 오랫동안 사용되지 않은 페이지를 찾는 것.지역성 이론의 시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높으므로, 최근에 사용되지 않은 데이터가 앞으로도 사용될 확률이 적다는 결론이 나온다.최적 페이지 교체와 근접한 성능을 보인다.그러나 시간을 기록하려면 비트가 많이 필요한데 많은 비트의 사용은 어렵기 때문에 접근 비트를 사용한다.✳ LRU의 시간 기록 문제 해결 방법1.4 Clock 또는 Second-ChanceFIFO와 LRU를 결합한 방식일정 시간 간격 마다 모든 페이지의 접근 비트를 0으로 초기화한다.접근 비트의 초기값은 0 만약 페이지가 참조되었다면 1로 설정일정 시간마다 페이지가 사용되었는지 확인 가능하다. 알고리즘퀵 정렬은 in place 방법과 in place가 아닌 방법 2가지가 있는데 실제로 많이 쓰이는 방법은 메모리 사용량이 적은 in place 방법이다. In Place정렬되지 않은 데이터에서 가운데 원소를 pivot으로 설정하고 가장 왼쪽 요소와 가장 오른쪽 요소가 시작점이다. 가장 왼쪽부터 값을 pivot값을 비교하여 pivot보다 큰 값이 나타날 때까지 칸을 오른쪽으로 이동한다.가장 오른쪽부터 값을 pivot값을 비교하여 pivot보다 작은 값이 나타날 때까지 칸을 왼쪽으로 이동한다.pivot보다 큰 왼쪽 값과 pivot보다 작은 오른쪽 값을 서로 교환한다. 왼쪽 인덱스가 오른쪽 인덱스보다 커지면 이동을 멈추고 그 자리에서 두 배열로 갈라서각 배열에 위와 같은 방식으로 재귀 호출하여 정렬한다. 이 방법은 추가적인 공간을 필요로하지 않기 때문에 메모리 공간이 절약된다는 장점이 있으나, 왼쪽과 오른쪽 값을 교환하는 과정에서 중복값의 위치가 바뀔 수 있으므로 unstable한 정렬 방법이다.(+추가내용)Not In Place퀵 정렬은 병합 정렬과 같이 Divide and Conquer 전략을 사용한 알고리즘이다. 즉, 정렬하는데 가장 간단한 배열은 바로 요소가 없거나 하나만 있는 배열이므로 모든 배열이 기본 배열이 될 때까지 큰 배열을 나눠야한다.이 때 퀵 정렬에서는 요소 하나를 기준 원소인 pivot으로 설정한다. 그리고 기준 원소의 왼쪽에는 기준 원소보다 작은 값의 배열을 놓고 오른쪽에는 기준 원소보다 큰 값을 놓는다.pivot 왼쪽에 놓여진 기준 원소보다 작은 배열에서 위와 같은 방법으로 다시 pivot을 설정하고 배열을 pivot을 기준으로 나눈다. 이 방법을 반복하면 결국 기본 단계인 원소가 하나만 있는 배열이 남는다. 기준 원소를 고른다.배열을 기준 원소보다 작은 원소의 배열과 기준 원소보다 큰 원소의 배열, 이렇게 2개의 하위 배열로 분할한다.하위 배열에 대해 재귀적으로 퀵 정렬을 호출한다. 운영체제1⃣ 주변장치(I/O 디바이스, 저장장치)주변장치에는 그래픽 카드, HDD, SSD, 키보드, 마우스 등 여러가지가 있다.1.1 주변장치의 내부 구조각 하드웨어에 맞게 외부 인터페이스가 존재레지스터입출력 작업 시 데이터를 저장하며 CPU가 필요로 할 때 메모리로 이동메인보드에 있는 버스를 통해 연결I/O 버스는 Address, Data, Control 이 세 가지 버스를 따로 받을 수 있다.1.2 캐릭터 디바이스와 블록 디바이스데이터의 전송단위가 캐릭터(글자)인지 블록인지로 나눈 것✔ 캐릭터 디바이스마우스, 키보드, 사운드카드, 직렬/병렬 포트 등이 있다.상대적으로 적은 양의 데이터를 전송✔ 블록 디바이스하드디스크, SSD, 그래픽카드 등이 있다.상대적으로 많은 양의 데이터를 전송1.3 입출력 버스 구조초기의 입출력 버스버스 하나에 주변 장치를 모두 연결해서 사용했는데, CPU가 작업을 진행하다가 입출력 명령을 받으면 직접 입출력장치에서 데이터를 가져오는 폴링방식을 이용했다. 이는 CPU 사용률을 감소시킨다.2⃣ 마우스와 키보드광학 마우스의 작동원리마우스 밑면에 작은 카메라 탑재, 초당 1500회가 넘는 사진을 찍어 디바이스 컨트롤러 내 DSP(Digital Signal Processor)로 보낸다.DSP는 사진을 분석해 마우스의 x축 좌표와 y축 좌표 움직임 분석디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해 데이터를 읽는다.⭐여기서 잠깐!⭐인터럽트를 복습해보자면CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치나 예외상황이 발생하여 처리가 필요할 경우에 마이크로프로세서에게 알려 처리할 수 있도록 하는 것을 말한다.마우스 드라이버는 운영체제에게 이벤트 신호를 보내고 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달해당 애플리케이션은 받은 마우스 이벤트 처리, 해당 동작 수행키보드의 작동원리사용자가 키 입력디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄CPU에게 인터럽트를 보냄키보드 드라이버는 운영체제에 이벤트를 보내고 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달해당 애플리케이션은 받은 키보드 이벤트 처리, 해당 동작 수행3⃣ 하드디스크하드디스크의 구조스핀들(spindle)플래터의 중심 축 막대플래터(platter)자기화된 원판으로 구성. 여러개의 트랙(track)으로 구성되어 있으며 표면에 자성이 있어 표면이 N극을 띄면 0, S극을 띄면 1로 인식디스크암(Disk Arm)플래터쪽을 향한 끝부분에 있는 읽기/쓰기 헤드(read/write head)로 플래터의 표면을 읽는다. 이 헤드들은 항상 같이 움직인다.실린더(cylinder)여러 개의 플래터에 있는 같은 트랙의 집합섹터(sector)하드디스크의 가장 작은 단위 알고리즘메모이제이션(memoization)은 값비싼 함수 호출의 결과를 캐싱하고 동일한 입력이 다시 발생할 때 불필요하게 다시 계산하는 대신 캐싱된 결과를 반환하는 프로그래밍 기술로, 동일한 입력으로 여러 번 호출되는 함수 또는 컴포넌트가 있을 때 유용합니다.메모이제이션은 메모리에 특정한 값을 저장하는 것이기 때문에, 정말 필요하지 않은 경우에도 남용하면 오히려 성능을 저하시킬 수 있습니다.함수형 프로그래밍과 메모이제이션함수형 프로그래밍과 메모이제이션은 밀접하게 관련된 개념이다. 메모이제이션은 순수 함수의 실행을 최적화하기 위해 함수형 프로그래밍에서 일반적으로 사용된다.불변성 함수형 프로그래밍은 불변 데이터를 선호하여, 값이 할당되면 변경할 수 없다. 원본 데이터를 수정하는 대신 복사본을 사용하여 새 데이터 구조를 만든다. 순수 함수동일한 입력에 대해 동일한 출력을 생성한다.외부 상태를 수정하거나 변경 가능한 데이터에 의존하지 않는다(no side effect). 고차 함수 다른 함수를 인수로 사용하거나 함수를 결과로 반환할 수 있다. 이를 통해 강력한 추상화가 가능하고 보다 일반적이고 재사용 가능한 코드를 작성할 수 있다. 재귀 함수형 언어의 반복은 재귀에 의해 구현된다. 재귀 함수는 종료 조건이 충족될 때까지 수정된 매개변수로 자신을 호출한다. 기능 구성 기능적 프로그래밍은 기능을 함께 연결하여 보다 복잡한 작업을 형성함으로써 기능을 구성한다. 이를 통해 한 함수의 출력이 다음 함수의 입력이 되는 파이프라인을 구성할 수 있다.함수형 프로그래밍과 메모이제이션의 관계는 순수 함수가 참조적으로 투명하다는 사실에서 발생한다. 함수형 프로그래밍은 동일한 입력에 대해 동일한 출력을 생성하고 부작용(side effect)이 없는 함수인 순수 함수의 사용을 강조하는 프로그래밍이다.그리고 메모이제이션은 함수를 다시 평가하는 대신 캐싱된 결과를 반환하여 함수의 성능을 향상시킨다. 이때 부작용이나 변경 가능한 상태를 고려하지 않기 때문에 함수형 프로그래밍의 원칙과 부합한다. 순수한 함수 호출의 결과가 프로그램의 정확성에 영향을 주지 않고 안전하게 캐싱될 수 있는 것이다.따라서 메모이제이션을 사용하면 기능적 프로그래머가 참조 투명성을 희생하거나 부작용을 일으키지 않고 코드를 최적화할 수 있다. 즉, 메모이제이션은 순수 함수 호출을 최적화하고 중복 계산을 줄이며 성능을 향상시키는 방법을 제공함으로써 함수형 프로그래밍 패러다임을 보완하는 강력한 기술이다.운영체제1⃣ 파일과 파일 시스템파일들은 하드디스크나 SSD같은 저장 장치에 저장되는데, 사용자가 직접 저장하면 손상시킬 수 있어 운영체제가 안전하게 저장한다.✔ 파일시스템운영체제가 파일을 관리하기 위해 둔 파일 관리자로, 파일테이블을 이용한다.1.1 파일 시스템 기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권한 관리(다중 사용자 환경)무결성 보장백업 및 복구파일 암호화로 파일 보호파일은 하드디스크나 Flash Memory같은 블록 디바이스에 저장되기 때문에 전송 단위는 블록인데, 바이트 단위로 접근해야하는 사용자를 위해 파일 시스템이 중간에서 바이트 단위로 변환1.2 파일의 구조헤더해당 파일의 속성 기록(파일 이름, 식별자, 유형, 크기, 시간, 저장 위치, 접근 권한, 소유자 등)데이터✔ 파일 디스크립터(File Descriptor)운영체제가 파일을 관리하기 위해 정보를 보관하는 파일 제어 블록(File Control Block). 각 파일마다 독립적으로 존재하고, 저장장치에 존재하다 파일이 오픈되면 메모리로 이동한다.사용자는 직접 참조할 수 없고, 파일시스템이 건내준 파일 디스크립터로 파일에 접근할 수 있다.파일은 데이터의 집합으로 이루어지는데, 이 집합을 어떻게 구성하느냐에 따라 종류가 나뉜다.1.3 파일의 분류순차 파일 구조파일의 내용이 연속적으로 이어지는 구조작동 원리사용자가 파일을 열기 위해 open()함수를 사용하면 파일 시스템은 파일 디스크립터를 사용자에게 전달한다. 파일 디스크립터는 파일의 맨 앞에 위치해 사용자가 읽기/쓰기를 시작하면 처음부터 진행한다. 다른 영역으로 가고싶다면 lseek() 함수를 이용해 파일디스크립터의 위치를 옮긴다.장점모든 데이터가 순서대로 기록되어 공간의 낭비가 없고 구조가 단순단점특정지점으로의 이동이 어려워 데이터 삽입, 삭제를 위한 탐색 시간 소요직접 파일 구조저장하려는 데이터를 해시함수를 통해 저장 위치를 결정하는 구조예) 해시 테이블 자료구조, json장점해시함수 이용으로 데이터 접근 속도 빠름단점알맞은 해시함수를 잘 골라야하고 저장공간이 낭비될 가능성 존재인덱스 파일구조순차접근과 직접접근 방식의 장점을 취해 두 가지 모두 가능하게 한 구조예) 재생목록재생목록은 전부 순차 데이터로 저장되어있으며, 재생을 누르면 앞에서부터 뒤로 순차적 재생을 한다. 사용자가 듣고 싶은 노래를 클릭하면 인덱스 테이블의 해당 노래가 저장된 행에 접근해 블록 번호를 알아낸다. 순차 데이터의 해당 블록번호로 이동해 클릭한 노래가 재생될 수 있도록 한다.2⃣ 디렉토리디렉토리(Directory)디렉토리는 파일과 다른 디렉토리를 포함할 수 있는 컨테이너로, 파일을 주제나 유형별로 그룹화하여 조직화할 수 있다. 디렉토리도 하나의 파일로, 파일이 데이터를 저장한다면 디렉토리는 파일 정보를 저장한다.디렉토리 헤더디렉토리 정보가 시작하는 위치를 가리킨다.디렉토리에 점 한 개(.)와 점 두 개(..)가 있는데 이는 현재 디렉토리와 상위 디렉토리를 가리킨다.루트 디렉토리의 경우 상위 디렉토리가 없기 때문에 점 두 개(..)도 자기 자신을 가리킨다.디렉토리 구조계층적 구조: 최상위에 루트 디렉토리(/)가 존재초기루트 디렉토리에만 디렉토리가 존재할 수 있고 다른 디렉토리에서는 하위 디렉토리를 만들 수 없는 구조현재다단계 디렉토리 구조로, 모든 디렉토리가 하위 디렉토리를 만들 수 있는 트리구조3⃣ 파일과 디스크파일과 디스크전체 디스크 공간을 일정한 크기로 나누고 그 공간에 주소를 할당해 관리한다.일정한 크기로 나눈 공간을 파일시스템에선 블록이라고 부른다.디스크는 블록(1~8kb)으로 나뉘어있다.파일 시스템은 파일 정보를 파일 테이블로 관리하며 파일 테이블엔 파일이 시작하는 블록 위치 정보도 기록되어있다.1.1 파일의 할당 방식하나의 파일은 여러 개의 블록으로 이루어지는데, 이 블록들을 연결하는 방식에 따라 할당 방식 결정연속 할당파일을 구성하는 블록들을 디스크에 연속적으로 저장파일의 시작 부분만 알면 파일의 전체를 찾을 수 있다.외부 단편화가 발생해 실제로 쓰이지 않는다.불연속 할당파일을 구성하는 블록들을 디스크의 비어있는 공간에 분산 저장이 분산된 블록은 파일시스템이 관리연결 할당파일에 속한 데이터를 연결리스트로 관리파일 테이블에는 시작 블록에 대한 정보만 저장하고 다른 블록은 연결리스트를 통해 접근인덱스 할당(i-node 방식)파일 테이블의 블록 포인터가 데이터 블록에 직접 연결하는것이 아닌, 데이터들의 인덱스를 가지고 있는 인덱스 블록에 연결데이터가 많아 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기 때문에 테이블 확장 가능파일 크기가 작다면 데이터를 바로 참조하는 블록 포인터 이용, 파일 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근 가능블록 크기에 따른 문제점디스크를 구성하는 블록의 크기가 너무 작을 경우공간 낭비는 줄지만 관리해야 할 블록의 수가 많아진다.디스크를 구성하는 블록의 크기가 너무 클 경우관리해야하는 블록의 수는 적지만 내부단편화로 낭비되는 공간이 많아진다.파일 저장, 삭제 방식블록을 저장하려 할 때 마다 디스크의 빈 공간을 찾는 방식은 비효율적이다.파일 시스템은 효율적 관리를 위해 빈 공간을 모아둔 free block list를 가지며 파일 삭제시 파일 시스템은 파일의 모든 정보를 지우는 것이 아닌, 파일 테이블의 헤더만을 삭제하고 블럭을 free block list에 추가사용자는 파일이 삭제된 것 처럼 느끼지만 사용했던 블록의 데이터는 그대로 남아 있어 포렌식을 통해 데이터를 복구할 수 있다. 알고리즘

인프런 워밍업 클럽 스터디 3기 - 자료구조와 알고리즘 -2주차 미션-

1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?스택 오버플로가 발생합니다.콜스택에 스택 프레임이 쌓이는데, 기저조건을 만들지 않으면 함수가 무제한 호출되며, 스택 프레임도 무제한으로 쌓이게 됩니다.콜스택 메모리의 잉여 용량을 초과하면 프로세스가 OS에 의해 강제 종료되는데 이를 스택 오버플로라고 합니다. 2. 0부터 입력 n까지 홀수의 합을 더하는 재귀함수를 만들어보세요.function sumOdd(n) { if (n 3. 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요. const fs = require("fs"); // 파일을 이용하는 모듈 const path = require("path"); // 폴더와 파일의 경로를 지정해주는 모듈 function traverseDirectory1(directory){ const stack = [directory]; // 순회해야 할 디렉토리를 저장할 스택 while (stack.length > 0) { // 스택이 빌 때까지 반복 const currentDir = stack.pop(); // 현재 디렉토리 const files = fs.readdirSync(currentDir); // 인자로 주어진 경로의 디렉토리에 있는 파일 or 디렉토리들 for (const file of files) { // 현재 디렉토리의 모든 파일 or 디렉토리 순회 const filePath = path.join(currentDir, file); // directory와 file을 하나의 경로로 합쳐줌 const fileStatus= fs.statSync(filePath); // 파일정보 얻기 if (fileStatus.isDirectory()) { // 해당 파일이 디렉토리라면 console.log('디렉토리:', filePath); stack.push(filePath); } else { // 해당 파일이 파일이라면 console.log('파일:', filePath); } } } } traverseDirectory1("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력 const fs = require("fs"); // 파일을 이용하는 모듈 const path = require("path"); // 폴더와 파일의 경로를 지정해주는 모듈 function recursiveTraverseDirectory(directory) { const files = fs.readdirSync(directory); for (const file of files) { const filePath = path.join(directory, file); const fileStatus = fs.statSync(filePath); if (fileStatus.isDirectory()) { console.log('Directory:', filePath); recursiveTraverseDirectory(filePath); } else { console.log('File:', filePath); } } } recursiveTraverseDirectory("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력

인프런 워밍업 클럽 스터디 3기 - 2주차 발자국

[Day 6]운영체제1⃣ 프로세스 간 통신1.1 프로세스 간 통신(Inter Process Communication, IPC)프로세스 사이에 서로 데이터를 주고받는 행위, 방법, 경로를 IPC라한다.프로세스가 통신이 가능하다는 것은 서로 다른 프로세스가 데이터를 주고 받을 수 있다는 것이다.이는 컴퓨터 내부에서의 프로세스 간 소통일수도 있고, 다른 컴퓨터 간에 프로세스 간 소통일 수도 있다.1.2 프로세스 통신의 종류한 컴퓨터 내의 프로세스(운영체제영역)간의 방식과 다른 컴퓨터 간 프로세스(네트워크 이용)간의 방식으로 나뉜다.✔ 운영체제에서 지원하는 방식파일파이프✔ 네트워크를 사용하는 방식소켓(tcp, udp 등)RPC(Remote Procedure Call) - 원격 프로시저 호출1.2.1 프로세스 통신의 종류 상세내용 (+추가내용)파이프통신을 위한 메모리 공간을 생성하여 프로세스가 데이터를 주고 받게끔 한다.한 프로세스가 쓰고 다른 프로세스가 읽는 선입선출(FIFO) 형태의 큐라고 할 수 있다. 이는 단방향 통신이 가능한 파이프의 특징 때문에 반이중(Half-Duplex) 통신이라고 부르기도 한다.익명 파이프와 네임드 파이프 두 종류로 나뉜다.익명 파이프(Anonymous Pipe)✅부모-자식, 형제 등 통신 대상이 정해진 두 프로세스가 단방향 통신(Half Duplex)할 때 사용한다.✅양방향 통신(Full duplex)을 위해선 익명 파이프가 두 개 필요한데, 이는 구현이 복잡하다.네임드 파이프(Named Pipe)✅Anonymous Pipe가 확장된 형태로, 파일 시스템에 이름이 부여된 파이프를 말함.✅FIFO라는 통신을 위한 파일을 만들고, 이를 통해 양방향 통신이 가능하다. 소켓네트워크 소켓 통신을 통해 데이터를 공유한다.양쪽 PC에서 각각 임의의 포트를 정하고 해당 포트 간의 대화를 통해 데이터를 주고받는 형식이다.양방향 통신이 가능하다. 2⃣ 공유자원과 임계구역한정된 자원을 가지고 프로세스가 동시에 작업할 경우 동기화에 문제가 생길 수 있다.2.1 공유자원으로의 접근공유 자원은 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다.이는 각 프로세스 접근 순서에 따라 그 결과가 달라질 수 있다.2.2 경쟁 조건(Race Condition)경쟁 조건은 2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황을 말하며, 공유 자원 접근 순서에 따라 실행 결과가 달라지는 상황을 말한다.2.3 임계구역여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근(Access)할 수 있도록 하는 프로그램 코드 부분이다.여러 프로세스가 동일 자원을 동시에 참조하며 값이 바뀔 위함 가능성이 있는 영역이다.2.3.1 임계구역 해결 조건상호 배제(Mutual exclusion)한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없다.2.4 세마포어에츠허르 다익스트라가 제안한 교착상태(DeadLock)에 대한 해법으로 두 개의 원자적(Atomic) 함수로 제어되는 정수 변수로 멀티프로그래밍 환경에서 공유자원에 대한 접근 제어를 하는 방법으로 사용된다.1개의 공유되는 자원에 제한된 개수의 프로세스 또는 쓰레드만 접근할 수 있도록 한다.2.4.1 작동 원리세마포어의 작동 원리는 상호 배제 알고리즘에 기반한다. 💡상호 배제 알고리즘(Mutual Exclusion Algorithm)동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘, 임계 구역에서 구현된다.일반적으로 세마포어의 값이 0이면 자원에 접근할 수 없도록 블럭하고 0보다 크면 접근함과 동시에 세마포어의 값을 1 감소시킨다.반대로 종료하고 나갈 때에는 세마포어의 값을 1 증가시켜 다른 프로세스가 접근할 수 있도록 한다. 알고리즘1⃣ 재귀(Recursion)어떠한 것을 정의하는 과정에서 자기 자신을 참조하는 것1.1 특징재귀함수를 구현할 때 탈출 조건(기저 조건)을 정의하지 않으면, 콜스택에 계속 쌓이게 된다.스택 오버플로우(Stack Overflow) - 콜스택에 메모리 용량을 초과하여 프로세스가 강제 종료되는 현상팩토리얼(Factorial) - 재귀함수를 사용하면 쉽게 해결 가능한[ Day 7 ]운영체제1⃣ 교착상태두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태를 말한다.즉, 무한히 다음 자원을 기다리게 되는 상태이다.시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.1.1 교착상태의 발생 이유✔ 공유자원 1.2 교착상태의 필요조건한 가지라도 충족하지 않는다면 교착상태는 발생하지 않는다.상호배제한 프로세스가 리소스를 점유했다면 그 리소스는 다른 프로세스에게 공유되면 안된다.비선점사용하고 있는 리소스를 다른 프로세스가 뺏을 수 없다.점유와 대기원형대기점유와 대기 상태가 원형 상태인 것을 의미한다.2⃣ 교착상태 회피전체자원의 수와 할당된 자원의 수를 기준으로 안정상태와 블안정상태로 나뉜다.불안정상태에 있더라도 무조건 교착상태에 빠지는 것은 아니다.2.1 은행원 알고리즘교착상태(DeadLock)를 방지하는 자원 할당 알고리즘이다.은행의 대출 방식에서 유래되었는데, 은행이 고객에게 대출을 해줄 때 보유 잔고를 고려하듯, 프로세스에 자원을 할당할 때 시스템이 안정상태를 유지할 수 있는지 판단하는 방식이다. 알고리즘1⃣ 재귀적으로 생각하기재귀함수는 하위 문제를 기반으로 현재 문제를 해결하는 하향식 계산을 주된 방식으로 사용한다.1.1 배열의 합1.2 문자열 길이 계산// 구하려는 문저열 마지막 원소를 제외한 나머지 function strlength(arr){ if(arr[0] == null) return 0; return strlength(arr.slice(0, -1)) +1);1.3 지수함수function power(x, n) { if(n==0) return 1; return power(x, n-1) * x;[ Day 8 ]운영체제1⃣ 컴파일1.1 프로그래밍 언어컴파일 언어개발자가 코드를 작성하고 컴파일하여 0과 1로 된 기계어로 실행파일을 만든다.개발자가 문법 오류를 일으켰는지 검사를 한다.인터프리터 언어개발자가 작성한 코드를 미리 기계어로 만들지 않고 실행 시 코드를 한 줄 씩 해석해 실행한는 언어미리 검사를 하지 않기 때문에 실행할 때 오류가 날 수도 있고 속도도 컴파일과 비교하면 느리다.1.2 프로세스의 메모리 구조코드, 데이터, 힙, 스택으로 나뉜다.코드실행해야 할 코드가 들어가는 영역데이터전역변수나 배열이 들어가는 영역스택과 힙 영역은 프로세스가 실행될 때 할당되는 메모리로스택지역변수와 함수 관련 값들이 들어감힙실행 중에 메모리 공간을 할당할 수 있는 유동적인 공간이다.1.3 컴파일 과정✔ 컴파일 과정전처리헤더파일 혹은 매크로를 치환하여 .i파일로 저장 (#include, #define 등)컴파일어셈블리어로 컴파일 후 .s 파일로 저장 ( c, c++ )어셈블어셈플리어를 링커가 읽을 수 있는 목적파일로 변환하여 .o 파일로 저장 (기계어로 최종 번역)링킹목적파일들을 하나로 묶어 실행파일 알고리즘하노이의 탑1883년 프랑스의 수학자 Édouard Lucas가 처음으로 발표한 게임으로, 재귀함수 예제로 활용된다. [ Day 9 ]운영체제메모리의 종류✔휘발성 메모리정보를 일회성으로 저장하고 삭제하는 메모리를 말한다. 1.1 RAM휘발성 메모리의 대표적인 형태, CPU와의 빠른 데이터 교환을 위해 사용된다.프로그램 실행, 작업 데이터를 임시로 저장하여 CPU가 빠르게 접근할 수 있게 하는 역할을 한다. 1.2 레지스터CPU 내부에 위치한 가장 빠른 메모리로, 데이터나 명령어의 임시 저장소 역할을 한다.CPU에서 바로 처리하는 데이터, 즉 명령어 실행 중에 필요한 데이터를 빠르게 저장하고 불러오는데 쓰인다. 1.3 캐시 메모리(Cache memory)CPU와 주 메모리(RAM)간의 속도 차이를 줄이기 위해 사용되는 고속 메모리자주 사용되는 데이터를 미리 저장하여 CPU의 처리 속도를 향상시키는 역할을 한다. ✔ 가상 메모리RAM + HDD 알고리즘✔정렬 알고리즘(Sorting Algorithm)정렬이란 데이터를 오름차순이나 내림차순으로 배치하는 것을 말한다.정렬 시 데이터를 순서에 맞게 배치에 보다 더 쉽고 빠르게 검색할 수 있다. 1.1 버블 정렬서로 인접한 두 요소를 비교하여 정렬하는 알고리즘인접한 2개의 요소를 비교해서 교환하는 형태이다.0(n^2)의 시간복잡도를 가진다.1.2 선택 정렬배열에서 최솟값을 찾아 맨 앞부터 둔다.일반적으로 데이터의 교환이 이동 작업보다 복잡하다.O(n^2)의 시간복잡도를 가진다. 2주차를 회고하며..어떻게 따라가고 있는지도 모르게 주말이 다가왔고 솔직히 내용들을 완벽히 이해한 것 같지는 않다.발자국을 작성하며 다시 복습을 함으로써 조금은 머릿속에 정리되는 듯 하다.그러나 신기한게 감자님의 강의가 그림으로 쉽게 알려주시다 보니 당시에 강의해주셨던 그림들이 스쳐지나가며 생각이 난다.재귀와 하노이의 탑 등 다시 스스로 코드를 작성하며 복기해봐야겠다.

인프런 워밍업 클럽 스터디 3기 - CS 전공지식(운영체제) -2주차 미션-

1. 선입선출(FIFO)의 장단점장점스케쥴링의 이해와 구현이 단순하다.자원의 효율성이 높다.단점실행시간이 긴 프로세스가 앞에서 장시간 독점하는 경우 다른 프로세스들이 오래 대기해야한다.평균 응답 시간이 길어질 수 있다.2. 최소작업 우선 - SJF(Shortest Job First)을 사용하기 어려운 이유준비큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식이다.그러므로 실행 시간이 긴 프로세스들이 무한정 대기하는 현상이 발생한다.3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?라운드 로빈 스케줄링준비 큐에 가장 먼저 삽입된 프로세스부터 시작하여순서대로 프로세스에 CPU자원을 할당해서 실행실행할 때마다 일정하게 정해진 시간만큼만(time slice) 실행하고 다음 프로세스로 CPU자원을 넘겨주는데, 이 정해진 시간을 너무 작게(짧게) 설정하면 프로세스 간의 CPU 사용 교체가 빈번해져 실행 프로세스 교체에 소요되는 리소스가 과도해짐에 따라 오버헤드가 발생한다.4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?일반적으로 연산이 많이 필요한 로직은 CPU Bound로컬 파일 시스템 혹은 네트워크 통신이 많은 로직은 I/O Bound 라고 한다.여기서 프로세스 수행과정 중에 CPU burst , I/O burst가 계속 변경, 수행되며 프로세스 작업의 종류에 따라 각자가 일어나는 시간이 달라진다.이 때 CPU burst가 많이 일어나는 작업을 CPU Bound Process라고 하고 I/O burst가 많이 일어나는 작업을 I/O Bound Process라고 한다. 버스트 여기서 버스트란 연속된 신호 또는 데이터의 모임, 어떤 현상이 짧은 시간에 집중적으로 일어하는 현상을 뜻하거나 주기억 장치의 내용을 캐시 기억 장치에 블록 단위로 한꺼번에 전송하는 것을 뜻한다.CPU BoundCPU Bound는 프로세스가 진행될 때, CPU 사용 시간이 I/O Waiting 보다 많은 경우이다. 그러므로 CPU의 성능에 의해 작업 속도가 결정된다.I/O Bound프로세서가 진행될 때 I/O Waiting이 많은 경우이다.파일 쓰기, 디스크 작업, 네트워크 통신을 할 때 주로 나타나며5. 공유자원이란 무엇인가요?시스템 내에서 여러 프로세스나 스레드가 함께 접근할 수 있는 자원이다.메모리, 파일, 데이터 등을 말한다.공유자원은 공동으로 이용되기 때문에 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있다.6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?교착상태는 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다리는데 무한 대기 상태에 빠지는 상황을 일컫는다.즉, 한정된 자원을 여러 곳에서 사용하려고 함으로써 다음 처리를 하지 못하는 상태이다.요약멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁한 프로세스가 자원을 점유하고 있다면 동시에 다른 자원이 사용할 수 없는 상황 발생이 때 점유하지 못한 다른 프로세스는 대기 상태로 들어감.대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때, 교착 상태 발생발생 조건상호 배제자원 하나 당 한 프로세스만 사용할 수 있다.점유 대기다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존대비선점할당된 자원은 사용이 끝나서 반납될 때까지 강제로 빼앗을 수 없다.순환대기프로세스들의 집합이 점유대기 상태를 순환하는 것

인프런 워밍업 클럽 스터디 3기 - 자료구조와 알고리즘 -1주차 미션-

1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. 해시테이블을 이용할 것입니다.해시테이블은 해시 함수를 통해 입력값으 key를 받아 고유한 값을 index로 변환시켜 테이블에 저장하는 자료구조이다.O(1)의 시간 복잡도를 가지며, 삽입 삭제 조회가 가능하기 때문에 효율적으로 학생의 정보를 관리할 수 있다.2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐(Queue)를 사용할 것입니다.이유는 주문은 먼저 들어온 순서대로 처리되기 때문에 이는 큐의 특징인 FIFO(First In First Out)와 같기 때문입니다. 3. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.class revStack { constructor() { this.list = new LinkedList(); } push(data){ this.list.insertTail(data); } pop() { try { return this.list.deleteTail(); } catch (error) { return null; } } peek() { return this.list.getNodeAt(this.list.count-1) } isEmpty() { return this.list.count === 0; } printAll() { this.list.printAll() } } revStack.push(1); revStack.push(2); revStack.push(3); revStack.push(4); reverseStack.printAll(); console.log(revStack.pop().data); console.log(revStack.pop().data); console.log(revStack.pop().data); console.log(revStack.pop().data);4. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요.hashFunc(name){ return name.charCode(0) }function hashFunc(name, size = 100) { let hashValue = 0; for(let i = 0; i 회고이번 주차는 내용을 이해하기 바빠 미션을 수행하는데 있어 조금은 힘겨웠던 것 같다.남은 시간 내용을 복습하며 제대로 이해하도록 해야할 것 같고 다음주는 좀 미리미리 준비해야할 것 같다.

인프런 워밍업 클럽 스터디 3기 - CS 전공지식(운영체제) -1주차 미션-

아래 코드는 1초마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링 방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요? while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 } 스킬을 사용했는지 아닌지 주기적으로 확인해야하므로 폴링방식은 효율이 떨어집니다.그러므로 폴링방식 대신 인터럽트 방식을 사용하여 인터럽트 서비스 루틴을 실행시켜 작업을 완료시키는 것이 낫습니다. 프로그램과 프로세스는 어떻게 다른가요?둘의 차이는 메모리에 할당되어 있는가입니다.프로그램은 저장장치에 코드가 들어있고, 실행되기를 기다리므로 다소 수동적입니다.이후 사용자가 exe등 파일을 실행하면 프로세스가 생성되어 메모리 할당 PCB 할당 등 작업을 거쳐 CPU를 할당받게 되고 이를 능동적으로 처리합니다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?둘의 차이는 메모리 상에 프로세스를 여러개 동작시키는지와 CPU를 여러개 동작시키느냐의 차이입니다.멀티프로그래밍은 메모리 위에 여러 프로세스를 동시에 올려 동작하는 방식이며, 멀티 프로세싱은 CPU여러개로 (= 멀티 프로세서) 작업하는 방식을 말합니다.운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?해당 프로세스의 정보를 가지고 있는 PCB 를 활용합니다.생성된 프로세스를 연결리스트 형태인 PCB 형태로 저장합니다. 컨텍스트 스위칭이란 뭔가요?프로세스의 전환을 위해 프로세스 상태값을 PCB 형태로 저장하는 것을 말합니다.이는 컨텍스트 스위칭이 너무 자주 일어나는 환경에서 오버헤드가 발생할 수 있습니다.

인프런 워밍업 클럽 스터디 3기 - 1주차 발자국

모든 내용은 감자님의 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 강좌를 정리한 내용입니다.자료구조와 알고리즘 1일차1⃣ 자료구조자료구조는 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냅니다.대표적인 예 1) → 변수숫자나 문자열 저장하기 위해 변수 사용let a = 87; 예2) 배열숫자나 문자열 등을 연속적으로 저장접근 → 인덱스let arr = [87, 70, 100]; arr[1] ✅ 일반 변수와 배열의 처리방법의 차이? 🤔let a = 87; let b = 70; let c = 100; let average = (a + b + c) / 3; let arr = [87, 70, 100]; // 평균 변수 초기화 let average = 0; for(let i = 0; i 4개의 숫자의 평균을 구한다고 가정하고 각자의 방법으로 처리하면// 변수를 추가하고 평균 구한 코드도 수정해야함 let a = 87; let b = 70; let c = 100; // 변수 추가 let d = 55; // 평균 구하는 코드 수정 let average = (a + b + c + d) / 4; // 배열에 데이터만 입력하면 평균이 구해진다. let arr = [87, 70, 100, 55]; // 평균 변수 초기화 let average = 0; for(let i = 0; i ✔ 배열의 처리 방법이 유지/보수가 변수의 처리 방법보다 편리하다.2⃣ 알고리즘어떤 문제를 해결하기 위한 확실한 방법배열의 모든 숫자를 더하고 원소의 개수만큼 나눠라데이터가 어떤 자료구조를 하고 있는지에 따라 평균을 구하는 방식이 달라졌다.즉, 자료구조에 따라서 알고리즘이 달라진다.앞서 배열 자료구조의 평균을 구하는 방법에서 여러가지의 알고리즘이 있을 수 있다.✔” 배열의 모든 숫자를 더하고 원소의 개수만큼 나눠라 “✔” 배열의 첫 번째 원소와 두 번째 원소, 세 번째 원소를 더하고 3을 나눠라 “즉, 같은 자료구조에 대해서도 알고리즘은 여러가지가 있을 수 있다.시간복잡도1⃣ 더 좋은 알고리즘의 기준문제를 해결할 때 더 좋은 알고리즘을 사용하는 것이 당연하다.사용자의 요구에 따라 다르지만, 일반적으로 알고리즘의 속도가 성능의 척도가 된다. 이를 시간 복잡도라 부른다.✔ 시간 복잡도란?특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간컴퓨터에 성능에 따라 알고리즘을 처리하는데 걸리는 시간이 다르므로, 알고리즘을 평가할 때는 시간을 측정하는 것이 아닌 코드에 성능에 많은 영향을 주는 부분을 평가한다.이는 반복문이다.반복문이 많으면 느려지기 때문이다.예제)// 주어진 배열에서 5를 찾으시오 let arr = [1, 3, 5, 7]; // 최선의 경우 한 번에 찾음 -> Big-오메가 // 최악의 경우 배열의 길이만큼 걸림 -> Big-O // 평균의 경우 배열 길이의 중간만큼 걸림 -> Big-세터 빅오표기법최악의 경우 찾는 데이터가 배열의 끝에 있을 때배열의 길이가 n이라면 최악의 경우 n번 만에 찾을 수 있다. 이를 O(n), 선형시간 알고리즘이다.✔ 입력이 늘어날 때 계산량이 늘어나는 척도를 나타내기 위한 것운영체제가 하는 일1⃣ 프로세스 관리브라우저를 켜 놓고 노래도 들으며 게임을 해도 전부 동시에 실행이 된다.운영체제가 프로세스를 관리하지 않는다면 이 중 한 가지만 실행될 것입니다.2⃣ 메모리 관리3⃣ 하드웨어 관리운영체제는 사용자의 하드웨어에 대한 직접적인 접근을 막는다.특정 영역에 다른 중요한 데이터가 있을 수도 있고 공격을 막기 위해서이다.4⃣ 파일 시스템 관리운영체제의 역사1⃣ 1940년대애니악세계에서 가장 큰 스케일의 전자디지털 계산기입출력 속도가 느리고 입출력 도중에는 계산을 할 수 없음.인력으로 cpu를 대체2⃣ 1950년도 초반직접 회로(IC) 개발CPU, 메모리는 존재했지만 키보드와 모니터는 없었다. 대신 펀치카드를 이용하여 구멍을 뚫어 컴퓨터가 계산을 하게 하고 이를 라인프린터로 출력하는 방식을 사용3⃣ 중후반컴퓨터의 처리속도보다 오퍼레이터가 카드를 넣고 전달하는 과정이 느리게 느껴짐.오퍼레이터의 오버헤드가 큼이를 해결하기 위해 싱글스트림 배치시스템을 도입함.프로그래머가 펀치 카드를 여러 개를 가지고 오면 이를 한 번에 컴퓨터에 전달해주고 컴퓨터는 여러 개의 프로그램을 순서대로 실행해서 결과를 한 번에 확인할 수 있게 하는 시스템이다.1960년대시분할 시스템(시간 분할 시스템)유닉스 운영체제를 개발했는데 이는 멀티 프로그래밍과 다중 사용자와 파일시스템을 개발한 운영체제이다.✔ 문제점메모리 침범 문제70년대개인 컴퓨터 시대애플의 매킨토시 마이크로소프트의 MS-DOS 사용운영체제의 구조✅ 커널프로세스와 메모리, 저장장치를 관리하는 기능 담당사용자는 인터페이스를 통해서만 커널에 접근 가능✔ GUI(Graphic User Interface)그래픽으로 커널과 상호작용(마우스를 이용)✔ CLI(Command-Line Interface)텍스트를 이용해 커널과 상호작용(직접 텍스트 입력)사용자와 어플리케이션은 커널과의 인터페이스로 시스템 콜을 사용, 하드웨어와 커널의 인터페이스로는 드라이버 사용컴퓨터 하드웨어와 구조1⃣ 폰 노이만 구조프로그램 내장 방식애니악과 같이 하드웨어로 프로그램을 만들었기 때문에 프로그램이 달라질 때마다 매번 스위치와 배선을 다시 조정을 해야했다.이를 해결하기 위해 CPU와 메모리(RAM) 사이에 버스(데이터를 전달하는 통로)를 둔다.프로그램은 메모리에 올려서 실행시키는데 프로그램을 메모리에 내장했다고 해서 프로그램 내장방식이라고 한다.2⃣ 컴퓨터 하드웨어메인보드다른 하드웨어를 연결하는 장치3⃣ CPU 구조CPU(Central Processing Unit)는 중앙처리장치라고 부른다.이를 구성하는 장치는 세 가지로 나뉜다.산술논리 연산장치(Arithmetic and Logic Unit, ALU)제어장치 (Control Unit) - 모든 장치들의 동작을 지시하고 제어하는 장치레지스터(변수)4⃣ 메모리 종류메모리는 크게 RAM과 ROM으로 구별할 수 있다.RAM(Random Access Memory)은 랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 읽는 속도가 같습니다. 전력이 끊기면 데이터도 같이 끊긴다.ROM(Read Only Memory)전력이 끊겨도 데이터를 계속 보관할 수 있지만 데이터를 한 번 쓰면 수정이 불가능주로 부팅과 관련된 바이오스를 저장하는 데 주로 쓰임.3⃣ 중후반컴퓨터의 처리속도보다 오퍼레이터가 카드를 넣고 전달하는 과정이 느리게 느껴짐.오퍼레이터의 오버헤드가 큼이를 해결하기 위해 싱글스트림 배치시스템을 도입함.프로그래머가 펀치 카드를 여러 개를 가지고 오면 이를 한 번에 컴퓨터에 전달해주고 컴퓨터는 여러 개의 프로그램을 순서대로 실행해서 결과를 한 번에 확인할 수 있게 하는 시스템이다.1960년대시분할 시스템(시간 분할 시스템)유닉스 운영체제를 개발했는데 이는 멀티 프로그래밍과 다중 사용자와 파일시스템을 개발한 운영체제이다.✔ 문제점메모리 침범 문제70년대개인 컴퓨터 시대애플의 매킨토시 마이크로소프트의 MS-DOS 사용컴퓨터 부팅과정✅ ROM에 저장된 바이오스 실행주요 하드웨어에 이상이 없는지 체크이상이 있으면 부팅이 되지 않고, 이상이 없다면 하드디스크에 있는 마스터 부트 레코드에 저장된 부트로더를 메모리로 가져와서 실행한다.윈도우나 리눅스 둘 중 하나의 운영체제를 선택하면 부팅이 완료됨.인터럽트1⃣ 폴링(Polling)CPU가 입출력 장치에 데이터를 읽거나 쓰려고 하는 상황을 생각해보면CPU가 입출력 장치에 명령을 내리고CPU관점에서 입출력 명령이 언제 완료될 지 알 수 없기 때문에 주기적으로 학인해줘야한다.이를 폴링방식이라고 한다.이는 성능이 좋지 않다는 단점을 가지고 있다.2⃣ 인터럽트폴링 방식의 단점을 해결한 방식입출력 관리자는 입출력이 완료됐을 때 CPU에게 신호를 주고 CPU는 그 신호를 받아 인터럽트 서비스 루틴(ISR)을 실행시켜 작업을 완료한다.하드웨어 인터럽트입출력 등과 같은 인터럽트가 있다.소프트웨어 인터럽트2⃣ 컴퓨터 하드웨어메인보드다른 하드웨어를 연결하는 장치3⃣ CPU 구조CPU(Central Processing Unit)는 중앙처리장치라고 부른다.이를 구성하는 장치는 세 가지로 나뉜다.산술논리 연산장치(Arithmetic and Logic Unit, ALU)제어장치 (Control Unit) - 모든 장치들의 동작을 지시하고 제어하는 장치레지스터(변수)4⃣ 메모리 종류메모리는 크게 RAM과 ROM으로 구별할 수 있다.RAM(Random Access Memory)은 랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 읽는 속도가 같습니다. 전력이 끊기면 데이터도 같이 끊긴다.ROM(Read Only Memory)전력이 끊겨도 데이터를 계속 보관할 수 있지만 데이터를 한 번 쓰면 수정이 불가능주로 부팅과 관련된 바이오스를 저장하는 데 주로 쓰임.3⃣ 중후반컴퓨터의 처리속도보다 오퍼레이터가 카드를 넣고 전달하는 과정이 느리게 느껴짐.오퍼레이터의 오버헤드가 큼이를 해결하기 위해 싱글스트림 배치시스템을 도입함.프로그래머가 펀치 카드를 여러 개를 가지고 오면 이를 한 번에 컴퓨터에 전달해주고 컴퓨터는 여러 개의 프로그램을 순서대로 실행해서 결과를 한 번에 확인할 수 있게 하는 시스템이다.1960년대시분할 시스템(시간 분할 시스템)유닉스 운영체제를 개발했는데 이는 멀티 프로그래밍과 다중 사용자와 파일시스템을 개발한 운영체제이다.✔ 문제점메모리 침범 문제70년대개인 컴퓨터 시대애플의 매킨토시 마이크로소프트의 MS-DOS 사용자료구조와 알고리즘 2일차 1⃣ 배열메모리의 특정 크기의 연속된 공간을 미리 할당받는 자료구조JavaScript의 배열은 C언어에서의 배열과는 달리 객체를 가지는 형태이다.2⃣연결리스트불연속적인 메모리 위치에 저장하며, 노드를 생성하여 이 안에 데이터와 다음 노드를 가리키는 포인터를 저장하여 연결하는 자료구조이다. class Node { constructor(data, next = null) { // this.변수 -> 프로퍼티 this.data = data; this.next = next; } } class LinkedList { constructor() { this.head = null; this.count = 0; } printAll() { let currentNode = this.head; let text = "["; while (currentNode != null) { text += currentNode.data; currentNode = currentNode.next; if (currentNode != null) { text += ", "; } } text += "]"; console.log(text); } // 리스트의 모든 원소를 제거하는 함수 clear() { this.head = null; this.count = 0; } insertAt(index, data) { if (index this.count) { throw new Error("범위를 벗어났습니다."); } let newNode = new Node(data); if (index == 0) { newNode.next = this.head; this.head = newNode; } else { let currentNode = this.head; for (let i = 0; i this.count) { throw new Error("범위를 벗어났습니다."); } let currentNode = this.head; if (index == 0) { let deleteNode = this.head; this.head = this.head.next; this.count--; return deleteNode; } else { for (let i = 0; i 3⃣Operating System프로그램은 수동적(코드가 실행되기를 기다림), 프로세스는 능동적(메모리, CPU등 사용)이다.프로세스는 Code, Data, Heap, Stack 영역으로 이루어져있다.생성된 프로세스를 연결리스트 형태인 PCB로 저장한다.자료구조와 알고리즘 3일차1⃣스택FIFO의 특징을 가지는 자료구조이다.2⃣큐FIFO의 특징을 가지는 자료구조로 작업 스케쥴링 등에 활용된다. 3⃣ 해시 테이블 (Hash Table) Key-Value 형태로 데이터를 저장하는 자료구조빠른 검색(O(1))이 가능하지만, 해시 충돌이 발생할 수 있다. 4⃣트리 (Tree) 계층 구조를 이루는 자료구조. 이진 탐색 트리 (BST): O(log n)의 탐색 속도를 가진다.힙 (Heap): 우선순위 큐 구현에 사용된다.트라이 (Trie): 문자열 검색 최적화.5⃣ 그래프 (Graph) 정점(Vertex)과 간선(Edge)으로 구성된 자료구조.최단 경로 탐색 (Dijkstra), 최적 경로 찾기 (A*) 등에 활용된다.\ 자료구조 FCFS 먼저 도착한 순서대로 실행 (대기 시간 증가 가능) SJF 실행 시간이 가장 짧은 프로세스부터 실행 SRTF 남은 실행 시간이 가장 짧은 프로세스부터 실행 RR 일정 시간(Time Quantum)마다 프로세스를 교체 Priority Scheduling 혼합 우선순위가 높은 프로세스부터 실행