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

지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블정렬시간복잡도: O(n²)장점 구현이 쉽고 단순해서 이해하기 편함단점 속도 느림선택정렬시간복잡도: O(n²)장점 구현이 쉽고 단순해서 이해하기 편함단점 속도 느림삽입정렬시간복잡도: O(n²)장점 구현이 쉽고 단순해서 이해하기 편함단점 속도 느림병합정렬시간복잡도: O(n logn)장점 속도 빠름단점 어렵다퀵정렬시간복잡도: O(n logn)장점 속도 빠름단점 어렵다 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다.여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션(상향식) 방식이 더 적합하다.메모이제이션은 재귀 호출을 하는 하향식 방식이기 때문에 스택 메모리를 사용해야 한다타뷸레이션은 반복문만 사용해서 추가 메모리를 사용하지 않는다

[인프런 워밍업 클럽 스터디 3기] 3주차 미션 - 운영체제

메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터휘발성 메모리CPU는 레지스터에 있는 값을 가져와서 메인메모리에 저장가장 빠른 메모리 용량은 매우 작음 (몇 바이트)캐시휘발성 메모리CPU와 RAM 사이의 속도 차이를 줄이는 역할L1, L2, L3 캐시로 구분RAM휘발성 메모리매우 빠른 메모리메인 메모리로, 현재 사용하는 프로그램이 올라감보조저장장치비휘발성 메모리파일 등 저장 (영구 저장 가능)속도 느림 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변분할방식 = Segmentation용도별로 메모리를 나누기 때문에 관리가 용이프로세스 크기에 따라 동적으로 메모리를 분할할 수 있음외부 단편화 발생고정분할방식 = Paging페이지를 일정한 크기로 미리 나눠두는 거기 때문에 구현이 단순하고 관리가 용이내부 단편화 발생 CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱 HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 이유를 함께 적어주세요.운영체제 구동을 위해 필수적이다운영체제 파일을 저장가상메모리의 스왑 공간으로 활용사용자의 데이터를 영구 저장하기 위해 필요하다 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일 관리 시스템에서 삭제를 해도 실제로 삭제를 하는게 아닌 주솟값만 지우기 때문에

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

운영체제가상메모리메모리 공간이 부족해서 프로그램을 실행하지 못하는 문제를 해결물리 메모리 크기랑 위치를 생각하지 않고 0번지에서 시작한다고 생각하면 됨프로세스(사용자) > 가상 메모리 (메모리 관리자) > 물리 메모리가상 메모리의 크기: 물리 메모리의 크기와 CPU 비트 수에 따라 결정됨 동적 주소 변환(Dynamic Address Translation, DAT)프로세스가 메모리 접근을 시도 할 때마다 발생CPU가 가상 주소 생성 > MMU(Memory Management Unit)가 변환 작업 시작 > 페이지 테이블 참조 > 물리적 주소로 변환 > 실제 메모리 접근메모리 부족 상황에서는 Swap 영역으로 페이지를 이동 (Swap Out)스왑 대상 페이지 선정 > 페이지 테이블 엔트리 수정 > 수정된 페이지라면 디스크 쓰기 > 물리 메모리에서 해제 이런 메모리 할당/비할당을 어떻게 관리하는지는 아래의 정책 별로 나뉨Segmentation (가변 분할 방식)메모리를 어떻게 구분하나: 메모리의 역할에 따라 구분(코드, 데이터, 라이브러리, 스택, 힙)어떻게 바꾸나: 세그멘테이션 테이블을 이용해서 변환CPU에서 받은 논리주소와 Bound Address의 크기를 비교논리주소 논리주소 + Base Address = 물리주소논리주소 > Bound Address > 메모리 침범 에러 발생 Paging (고정 분할 방식)메모리를 어떻게 구분하나: 구분하지 않음어떻게 바꾸나: 정해진 크기의 페이지로 나눠둠논리주소 공간 = 페이지 / 물리주소 공간 = 프레임페이지, 오프셋을 통해서 프레임 번호를 알아내서 물리주소로 변환 Paged Segmentation (Segmentation + Paging)위 2개의 장점을 취한 방식현대의 운영체제는 페이징과 페이지드 세그멘테이션을 적절히 섞어서 사용 Demand Paging (가져오기)필요한 모듈만 메모리에 올라가서 실행조만간 쓸 것 같은 데이터만 메모리에 두고 안 쓰는 거 같은 거는 스왑에 저장해둔다스왑영역 = 보조저장장치어떻게 안쓰는거 같은거를 구분하나?접근비트/변경비트/유효비트를 통해 구분페이지 교체 알고리즘을 이용Page Fault > 스왑영역에서 메모리로 불러들이기 (= 공간을 만들어줘야 함) > 교체정책을 통해 어떤 애를 스왑으로 옮길지 결정RandomFIFOOptimum: 앞으로 가장 오랫동안 쓰이지 않을 페이지 선택 > 구현 불가LRU: 최근 가장 사용 적은 페이지 (실제로 Optimum과 성능 비슷)2차 기회 페이지 교체 알고리즘: 자주 사용하는 페이지한테 기회를 한 번 더 줌입출력장치주변장치: 그래픽카드, HDD, SSD, 키보드, 마우스 등이 주변장치들은 메인보드에 있는 버스로 연결된다.레지스터를 이용해서 장치의 상태와 데이터를 보관해서 저장하고, CPU가 이 값을 사용하기도 한다 캐릭터 디바이스데이터의 전송 단위가 캐릭터(글자)마우스/키보드/직병렬포트/사운드카드상대적 크기가 작음블록 디바이스데이터의 전송 단위가 블록하드디스크/SSD/그래픽카드크기가 큼 파일시스템파일은 하드디스크/SSD 같은 저장장치에 저장파일관리자가 파일테이블을 이용해서 파일 정리운영체제는 파일을 관리하기 위헤 정보를 관리하는 파일 디스크럽터를 갖고 있음 자료구조와 알고리즘선택정렬1번째 원소부터 마지막 원소까지 비교 후 가장 작은 값을 1번째 원소로 가져옴삽입정렬정렬되지 않은 영역에서 하나씩 빼서 정렬된 영역의 적절한 위치에 원소 삽입병합정렬Divide and Conquer(분할 정복) 사용배열의 원소를 1개가 될 때까지 배열을 반으로 쪼갠 다음 거기서부터 하나씩 정렬을 하며 병합 하는 것재귀를 사용퀵정렬Divide and Conquer(분할 정복) 사용재귀를 사용정렬하기 전에 배열에 있는 숫자 중 하나를 피벗으로 설정각각 왼쪽 오른쪽에서 이동하면서 피벗보다 큰/작은 수를 만나면 멈추고 둘을 스왑성능만 보면 병합정렬이 더 좋다고 생각할 수 있지만 퀵정렬이 메모리 공간을 덜 차지해서 더 좋다고 평가됨추가적인 배열을 생성하지 않음 (제자리 정렬)동적프로그래밍메모이제이션피보나치 수열재귀로 구현했더니 중복계산이 많이 발생이를 해결하기 위해 계산 결과를 저장해서 여러번 같은 계산을 하지 않도록 하는 기법 == 메모이제이션 타뷸레이션메모이제이션 = 하향식 / 타뷸레이션 = 상향식미리 계산에 필요한 모든 값을 계산 후 테이블에 저장 12586269025 fibonacci 함수 실행 시간 : 86590ms 12586269025 enhanced fibonacci 함수 실행 시간 : 0ms 12586269025 tabulation Fibonacci fibonacci 함수 실행 시간 : 1ms재귀가 더 직관적이라면 메모이제이션을 사용하는 것이 유리아니라면 타뷸레이션 사용 회고👏 칭찬하고 싶은 점일이 정말 더 바빴는데 한번도 강의를 밀리지 않았다 😅 아쉬웠던 점너무 일이 바빠서 강의 들면서 졸거나 해서 대충 넘어간 부분이 있는거 같다..

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

재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?재귀함수가 계속 본인을 호출하면서 콜 스택이 가득 차게 되어 StackOverFlow가 발생할 수 있다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if(n === 0) { return 0; } if(n 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.function traverseDirectory2(directory){ if(directory) { console.log('디렉토리: ', directory); const files = fs.readdirSync(directory); for( const file of files){ const filePath = path.join(directory, file); const fileStatus= fs.statSync(filePath); if(fileStatus.isFile()){ console.log('파일: ', filePath); } else { traverseDirectory2(filePath); } } } } traverseDirectory2("..");

[인프런 워밍업 클럽 스터디 3기] 2주차 미션 - 운영체제

FIFO 스케줄링의 장단점이 뭔가요?First In First Out먼저 들어온 프로세스를 먼저 처리한다는 것인데, 먼저 들어온 프로세스가 아주 길 경우에 뒤에 들어온 프로세스가 정말 빨리 끝나는 프로세스 임에도 불구하고 한참 기다려야 하는 단점이 있다.반면에 장점은 단순하고 직관적이라는 장점이 있다. SJF를 사용하기 여러운 이유가 뭔가요?Shortest Job First가장 짧은 프로세스를 먼저 실행한다는 건데 가장 짧은 프로세스를 예측하기가 힘들다.짧은 프로세스들이 계속 치고 들어오면 긴 프로세스는 영영 실행되지 못하고 계속 기다려야 하는 상황이 발생해서 사용하기가 어렵다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?Round Robin타임 슬라이스가 아주 작으면 컨텍스트 스위칭이 빈번하게 일어나 오버헤드가 많이 발생하게 되어서 속도가 오히려 느려질 수 있다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?Multi Level Feedback Queue배정 받은 타임 슬라이스를 모두 사용하는지를 관찰한다.CPU Bound: 대부분 타임 슬라이스를 모두 사용한다.I/O Bound: 타임 슬라이스가 끝나기 전에 I/O를 요청한다. 공유자원이란무엇인가요?여러 프로세스들이 공유하는 자원을 말한다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호배제자원은 한 프로세스에만 할당됨비선점먼저 차지한 자원을 다른 프로세스가 강제로 빼앗을 수 없음점유와 대기이미 사용 중인 자원을 사용하려고 프로세스가 대기함원형 대기점유와 대기를 하는 프로세스들이 원형을 이룸

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

운영체제프로세스 동기화프로세스 간 통신한 컴퓨터 내에서 프로세스 간에 통신은 어떻게 할까?운영체제가 만든 파이프를 통해 통신한 프로세스 안에서 쓰레드 간 통신네트워크를 이용한 통신소켓 통신 (운영체제가 제공)RPC 통신 (다른 컴퓨터에 있는 함수를 호출 - 원격 프로시저 호출)공유자원과 임계구역공유자원여러 프로세스가 공유하는 변수나 파일여러 프로세스가 공유하기 때문에 순서에 따라서 값이 다를 수 있음컨텍스트 스위칭으로 실행되기 때문에 누가 먼저 실행되는지 알수가 없거나 어렵다따라서 연산 결과를 예측하기 어렵다여기서 발생하는 문제가 동기화 문제임계구역여러 프로세스가 동시에 사용하면 안되는 구역이 문제를 해결하려면 상호 배제 매커니즘이 필요 상호 배제 매커니즘임계구역에는 동시에 하나의 프로세스만 접근한다동시에 여러 요청이 와도 하나의 프로세스만 접근한다임계구역에 들어간 프로세스는 최대한 빠르게 나와야 한다 세마포어열쇠 관리자가 열쇠를 가지고 있고 열쇠를 한 명한테만 준다프린터: 공유자원프린터를 사용하려는 지원들: 프로세스프로세스들이 기다리는 공간: 대기 큐열쇠 관리자: 운영체제열쇠: 세마포어 실제로 세마포어는 정수형 변수로 여러 개의 열쇠를 가질 수 있다.예를 들어 공유자원이 2개라면 열쇠도 2개다.단, 열쇠 제공과 반납을 이상하게 호출해서 잘못 사용할 수도 있다는 단점이 있다. // 임계 영역 진입 전 semaphore.wait(); try { // 임계 영역 코드 } finally { // 임계 영역 퇴출 시 semaphore.signal(); }이런식으로 항상 wait()과 signal() 은 쌍으로 호출되어야 하는데 연속으로 각각의 것을 호출하면 안된다.연속으로 wait()를 호출한 경우 > 데드락 발생연속으로 signal()를 호출한 경우 > 자원 낭비 모니터세마포어의 단점을 해결한 상호배제 매커니즘운영체제가 아닌 프로그래밍 언어에서 자체 지원한다. 명시적으로 wait()과 signal() 를 호출하지 않아도 자동으로 됨Java에서는 synchronized 키워드를 통해 모니터를 구현한다.public class BoundedBuffer { private final int[] buffer = new int[5]; private int count = 0; private int in = 0; private int out = 0; // synchronized 키워드로 상호배제 보장 public synchronized void produce(int item) throws InterruptedException { // 버퍼가 가득 찼다면 대기 while (count == buffer.length) { wait(); // 다른 스레드가 notify할 때까지 대기 } buffer[in] = item; in = (in + 1) % buffer.length; count++; notify(); // 대기 중인 소비자에게 알림 } public synchronized int consume() throws InterruptedException { // 버퍼가 비었다면 대기 while (count == 0) { wait(); // 다른 스레드가 notify할 때까지 대기 } int item = buffer[out]; out = (out + 1) % buffer.length; count--; notify(); // 대기 중인 생산자에게 알림 return item; } } 데드락공유자원을 서로 차지하려다가 발생하는 교착 상태식사하는 철학자 문제5명의 철학자가 원형 테이블에 앉아있고 각 철학자 사이에 포크가 1개씩 있다철학자는 양쪽의 포크 (2개)가 필요하다포크는 한 번에 한 사람만 사용할 수 있다.모든 철학자가 동시에 왼쪽 포크를 잡으면 > 오른쪽 포크를 집으려고 모두가 대기 > 아무도 식사를 시작할 수 없는 교착상태가 발생 교착상태의 필요조건상호배제: 먼저 리소스를 차지했다면 다른 프로세스가 사용할 수 없음비선점: 한번 차지한 리소스는 다른 프로세스가 빼앗을 수 없음점유와 대기: 리소스를 가진 상태에서 다른 리소스를 기다림원형 대기: 점유와 대기를 하는 프로세스들이 원형을 이룬다이 중 한가지라도 충족되지 않으면 교착상태가 발생하지 않는다 해결하는 법교착상태 회피 어느 정도 할당해야 교착상태가 발생하지 않는지 파악해서 할당전체 자원의 수, 할당된 자원의 수로 안정상태와 불안정 상태를 나눔불안정 상태에 있더라도 무조건 교착상태인 것은 아니지만 교착상태가 될 확률이 높다 교착상태 검출가벼운 교착상태 검출프로세삭 일정시간 동안 진행되지 않으면 교착상태라고 간주일정 시점마다 체크포인트를 만들어서 저장하고 타임아웃이 나면 롤백무거운 교착상태 검출자원 할당 그래프를 이용운영체제가 어떤 프로세스를 쓰는지 지켜보다가 문제가 발생하면 해결계속 지켜봐야 하기 때문에 오버헤드가 발생함억울하게 종료되는 프로세스는 발생하지 않음 컴파일코드를 기계어로 바꿔서 실행파일로 만드는 것컴파일을 할 때 타입, 문법을 검사한다속도가 빠르다C, C++, C#코드 > 전처리기 > 컴파일러 > 어셈블러 > 링커 > 실행파일 완성! 인터프리터컴파일 과정이 없고 코드를 한 줄 씩 해석해서 실행하는 것미리 검사를 하지 않기 때문에 에러가 발생할 수 있음속도가 느리다JavaScript, Python, Ruby 메모리레지스터휘발성 메모리32bit, 64bit == 레지스터의 크기CPU는 레지스터에 있는 값을 가져와서 메인 메모리에 저장한다CPU가 사용하는 메모리로 엄청나게 빠르다캐시휘발성 메모리RAM이 너무 느려서 미리 데이터를 가져다 둘 곳이 필요해서 생김가장 속도가 빠른 순서로 나열하면 L1 캐시 > L2 캐시 > 메인메모리메인메모리 (RAM)휘발성 메모리가장 중요한 메모리로 실제 운영체제 및 다른 프로세스들이 올라가는 곳가격이 매우 비싸서 데이터를 저장하는 게 아닌 실행 중인 프로그램만 올라간다보조저장장치 (HDD, SSD) 비휘발성 메모리게임, 파일 등을 저장할 때 사용한다왜 다른데에 저장 안하냐? > 너무 비싸서 다른애들은 가성비가 좋지 않음메모리와 주소RAM을 관리하려고 운영체제가 메모리를 1바이트씩 나누고 구역에 이름을 매김 == 주소논리주소프로세스가 바라보는 메모리 주소0번지로 시작하는 연속된 메모리 공간으로 보임 (가상)각 프로세스마다 독립된 주소 공간을 가짐물리주소실제 RAM의 하드웨어 주소모든 프로세스가 공유하는 실제 메모리 공간절대주소고정된 메모리 위치재배치가 불가상대주소재배치가 가능한 상대적인 주소경계 레지스터레지스터 공간에서 운영체제가 있는 공간(커널 공간)이랑 사용자 공간을 나누었는데이 경계를 지키는게 경계 레지스터메모리 접근 과정프로세스의 논리주소 > 재배치 레지스터로 주소 변환 > 물리 메모리에 접근 메모리 할당 방식유니 프로그래밍 방식[시스템 메모리 구조] 물리 메모리(RAM) ┌─────────────┐ │ Process A │ ├─────────────┤ │ Process B │ ↔️ [스왑 영역(디스크)] ├─────────────┤ ┌─────────────┐ │ Process C │ │ Process D │ └─────────────┘ └─────────────┘메모리 오버레이 > 큰 프로그램을 메모리에 올릴 때 일부만 메모리에 올리고 일부는 하드디스크에 저장했음메모리에 올릴 때는 하드디스크 내부 스왑 영역에 올림스왑 과정이 있기 때문에 실제 메로리가 큰 컴퓨터 보다는 느리게 동작한다 멀티 프로그래밍 방식가변 분할 방식 (Segmentation)프로세스의 크기에 따라 메모리를 나누는 방법 > 연속된 메모리를 할당연속된 공간에 딱 맞게 할당 되어서 내부 단편화가 없음대신 외부 단편화가 발생 - 외부 단편화란?메모리의 빈 공간들이 있지만 프로세스의 크기보다 각각 작아서 할당되지 못하는 문제해결하려면 메모리 조각 모음을 하면 되는데 조각 모음을 할 때는 실행 중인 프로세스들을 일시 중지 시켜야 해서 오버헤드가 발생한다- 내부 단편화란?프로세스의 크기보다 큰 메모리에 프로세스가 할당되어서 낭비 공간이 발생하는 것 고정 분할 방식 (Paging)프로세스의 크기와 상관없이 메모리를 할당 > 한 프로세스가 메모리에 분산되어서 할당됨 > 비연속 할당구현이 간단하고 오버헤드가 적음작은 프로세스도 큰 메모리에 할당 되기 때문에 낭비공간이 생김 > 내부 단편화 현상 있음 버디 시스템가변 분할 방식과 고정 분할 방식을 혼합해서 단점을 최소화 한 방식2의 승수로 메모리를 분할해서 메모리를 할당각 분할된 영역은 "버디(짝)"를 가지며, 인접한 두 버디가 모두 가용 상태면 합칠 수 있다.가변 분할 방식처럼 프로세스 크기에 따라 메모리의 크기가 달라지면서 외부 단편화를 방지하기 위해서 메모리를 확보하는 것이 간단왜 간단할까?원래는 메모리 빈 공간 크기가 제각각이어서 이동 위치 계산이나 주소 재배치가 복잡했음버디 시스템에서는 조각들이 모두 2의 승수 크기이기 때문에 버디끼리만 합치면 된다 내부 단편화가 발생하긴 하지만 그 공간이 매우 작음 자료구조와 알고리즘재귀자기 자신을 참조하는 것으로 꼭 종료 조건(기저 조건)이 있어야 한다.콜스택 First In Last out함수를 호출하면 콜스택에 올라가고 종료되는 콜스택에서 제거됨isStackOverflowError 는 기저 조건 없이 실행되어 콜 스택이 꽉 차서 오류난 것재귀적으로 생각하기재귀함수를 쉽게 작성하려면 재귀함수가 이미 구현되어있다고 생각하고 하위 문제의 결과를 기반으로 현재 문제의 계산을 구성한다. > 하향식 계산 (가장 큰 문제에서 시작하여 작은 문제로 나누어 해결하는 방식)return number * factorial(number - 1); // 이 부분은 이미 구현되어있다고 생각한다상향식 계산과 하향식 계산function factorial2(number, i = 1, sum = 1) { if(i > number) return sum; return factorial2(number, i + 1, sum * 1) } // 상향식 계산 (재귀)재귀를 이용한다고 해서 모두 하향식 계산인 것은 아니다.이렇게 재귀를 사용해서도 상향식 계산을 할 수 있지만 하향식은 재귀로만 가능함상향식 재귀는 성능이 좋지 않으므로 하향식으로 하는게 좋다. 정렬버블정렬구현이 쉽지만 성능이 그렇게 좋지 않음두 개를 비교해서 큰 애를 뒤로 보내는 방식한 번 순회가 끝나면 마지막 원소는 이미 끝났으니 제외해야 한다구현function BubbleSort(arr) { for(let i = 0; i arr[j+1]) { let temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }성능바깥 쪽 For문이 돌 때마다 가장 큰 원소가 하나씩 정렬된다.안쪽 For문은 그 갯수가 하나씩 줄어든다.자연수는 버리고 가장 높은 차수를 선택하면 Big(O)는 O(n²)가 된다.대강 For문 2개가 중첩이면 O(n²)라고 생각하면 된다. 선택정렬 이해와 구현이 간단하지만 성능이 떨어짐첫 번째 원소에서 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져온다 구현function selectionSort(arr) { for (let i = 0; i 처음에 직접 써봤는데 let j를 i 부터 시작해서 계속 원하는 결과가 나오지 않았음한 번 순회를 돌면 최소값은 찾아진 것이므로 걔를 제외하고 해야한다!성능똑같이 시간 복잡도는 O(n²) 회고👏 칭찬하고 싶은 점일이 많이 바빴는데 밀리지 않고 듣고 정리해 두었다구현을 직접 해보고 오류가 나면 스스로 해결해 보았다 😅 아쉬웠던 점바빠서 운영체제 같은 경우에는 완벽하게 이해를 하지 못했는데 넘어간 부분이 좀 있었다 🔄 보완하고 싶은 점강의를 한 번 듣고 바로 한 번 복기를 하면 이해가 더 잘될 것 같아서 그렇게 해봐야 겠다 🎯 다음주의 목표강의 한 번 듣고 바로 복기하면서 한 번 더 이해해보기들으면서 드는 질문 정리해서 해보기

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

자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요?이유를 함께 적어주세요.Key 값으로 출석번호를 쓰고 Value로 이름을 저장하여, HashMap을 사용할 것 같습니다. 왜냐하면 본인의 출석번호는 대부분 알고 있기 때문에 출석번호를 알면 O(1)으로 학생의 이름을 찾을 수 있기 때문입니다. 또한 학생이 추가, 제거, 수정되었을 때도 직관적으로 출석번호를 알면 데이터를 수정할 수 있으므로 확장성에 용이하다고 생각합니다.여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다.주문은 들어온 순서대로 처리됩니다.이 때 여러분이라면 어떤 자료구조를 선택하실 건가요?이유를 함께 적어주세요.First In First Out의 Queue를 사용할 것 같습니다.들어온 순서대로 처리되는 구조가 큐와 똑같기 때문입니다. 순서가 완벽하게 보장되기 때문에 규칙에 맞게 공정하게 주문을 처리할 수 있을 것이라 생각합니다.우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다.반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요. import { LinkedList } from "./LinkedList.mjs"; class Stack { constructor() { this.list = new LinkedList(); } push(data) { this.list.insertLast(data); } pop() { return this.list.deleteLast(); } peek() { try { return this.list.getNodeAt(this.list.count - 1); } catch (error) { return null; } } isEmpty() { return this.list.count == 0; } } export { Stack };해시테이블의 성능은 해시 함수에 따라 달라집니다.수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다.이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요.hashFunction(name){ // 이름의 모든 글자의 유니코드를 더해서 7로 나누기 let sum = 0; for (let index = 0; index

[인프런 워밍업 클럽 스터디 3기] 1주차 미션 - 운영체제

운영체제while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다.이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다.이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?스킬을 사용했는지 1초마다 체크를 하는게 아닌, 스킬을 사용하면 인터럽트를 발생하여스킬을 사용했다고 알려줄 수 있도록 해야 합니다.프로그램과 프로세스가 어떻게 다른가요?프로그램은 처리 하는 코드를 꺼내 사용할 수 있도록 저장해 둔 정적인 단위를 프로그램이라고 하며,프로세스는 이 프로그램이 처리를 위해서 메모리로 올라와서 처리되는 처리 단위를 프로세스라고 합니다. 프로세스는 코드, 데이터, 스택, 힙, 그리고 PCB를 포함합니다.멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 복수의 프로그램을 메모리에 올려두고 번갈아 처리하면서 마치 프로그램 여러 개가 동시에 실행되고 있는 것처럼 보이도록 작동하는 것입니다.반면에 멀티프로세싱은 프로그램이 아닌 프로세스를 복수 개 올려두고 복수의 CPU가 시분할로 나뉘어 프로세스를 처리하는 것으로 병렬로 실행되는 것처럼 보이는게 아닌 진짜로 병렬 처리를 구현 한 것을 멀티프로세싱이라고 합니다.운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?운영체제는 프로세스를 CPU에 할당했다가 해제해다가 하면서 프로세스를 처리할 수 있도록 하는데, 이 할당/해제 작업을 효율적으로 하기 위해서 CPU 스케줄링 기법을 사용합니다. 또한 복수 개의 프로세스를 할당/해제 하기 위해서 PCB라는 단위를 두고 여기에 프로세스 처리에 필요한 것들을 저장해둡니다. PCB에는 프로세스의 상태, 레지스터, 스케줄링 정보, 메모리 관련 정보들을 저장합니다.컨텍스트 스위칭이란 뭔가요?컨텍스트 스위칭이란 프로세스가 CPU가 할당되었다가 해제되었다가 하는 것으로 처리되는 내용이 바뀌는(Switching) 것입니다. 현재 프로세스 상태를 저장하고, 현재 프로세스의 PCB에 정보들을 젖아합니다. 그리고 새 프로세스의 PCB를 불러와서 이전 상태를 복원합니다. 컨텍스트 스위칭은 인터럽트가 발생했을 때나 할당된 타임 슬라이스가 종료되었을 때 발생합니다. 이 때, 컨텍스트 스위칭이 너무 빈번하게 발생하면 오버헤드가 많이 발생하여 처리 속도가 오히려 느려질 수 있습니다.

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

1주차 학습 내용 운영체제운영체제의 역사50년대 이전(출처: IBM - The punched card)시대별 발전1940s: ENIAC - 최초의 범용 컴퓨터, 펀치카드 사용 1950s: 스위치 배선작업, 배치 시스템, CPU-입출력 분리1960s: 멀티프로그래밍, 파일시스템, 터미널, UNIX 등장1970s: 개인용 컴퓨터, Apple/MS-DOS, GUI 도입 기본 구조하드웨어폰 노이만 구조: 메모리에 프로그램 내장 메인보드: 하드웨어 연결 허브CPU: 연산장치, 제어장치, 레지스터로 구성메모리: RAM(휘발성), ROM(비휘발성) 운영체제커널: 프로세스/메모리/저장장치 관리인터페이스: CLI, GUI 주요 개념부팅: ROM(BIOS) → 하드웨어 점검 → 부트로더 → OS 실행인터럽트: CPU 대기 없이 입출력 처리프로세스와 쓰레드컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하려고 교체하는 작업PCB의 내용이 변경 됨다시 이전작업으로 돌아갈 수 있도록 값을 저장해야 함!입출력 요청 / 너무 오래 CPU를 점유 / 기타 인터럽트가 발생했을 때 생김 쓰레드원래는 프로세스만 있었는데 작업을 처리할 때마다 프로세스를 생성하니까 성능 이슈로 인해 생겨남프로세스 안에 있는 처리 단위로 프로세스의 CODE, DATA, HEAP을 공유함 CPU 스케줄링운영체제가 프로세스들에게 CPU를 할당했다가 해제했다가 하는 행위어떻게 하면 최대한 효율적으로 이를 할 수 있는지를 고민한 것이 스케줄링스케줄링 알고리즘에는 FIFO , SJF , RR , MLFQ 등이 있고 현대에는 MLFQ 를 가장 많이 사용한다. 자료구조와 알고리즘자료구조: 데이터가 어떤 구조로 저장되고 사용되는지알고리즘: 어떤 문제를 해결하기 위한 확실한 방법자료구조에 따라서 필요한 알고리즘도 달라지며 한가지 자료구조에 따라서도 알고리즘은 여러가지가 있을 수 있다시간복잡도특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간실제로 시간을 재는 것이 아닌 코드에서 성능에 많은 영향을 주는 부분을 찾아 예측한 것이 많은 영향을 주는 부분 == 반복문 빅 오메가 (Big-Ω): 최선의 경우 (Best Case)빅 오 (Big-O): 최악의 경우 (Worst Case)빅 세타 (Big-Θ): 평균의 경우 (Average Case) 빅오를 가장 많이 사용(출처: https://qc-at-davis.github.io/QCC/Classical-Computation/Computational-Complexity/big-O-chart.png)초록색 (Excellent): O(1), O(log n) - 가장 효율적연두색 (Good): O(n) - 좋은 효율성노란색 (Fair): O(n log n) - 보통 효율성주황색 (Bad): O(n²) - 나쁜 효율성빨간색 (Horrible): O(2ⁿ), O(n!) - 최악의 효율성 자료구조스택First In Last Out계속 쌓인다고 생각하면 됨 (수직으로)연결리스트에서 무조건 첫번째 인덱스에 인서트 큐First In First Out먼저 줄을 선 손님이 먼저 계산 → 큐!운영체제 프로세스의 작업요청 → 큐! (CPU가 순서대로 꺼내서 처리 → FIFO 스케줄링)연결리스트에 head에다가 인서트제거할때는 가장 뒤에서부터 하면됨 덱데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 자료구조덱을 이용하면 스택과 큐를 다 구현할 수 있음 해시테이블Hash / Map / HashMap / Dictionary해시함수로 테이블의 인덱스를 새로 만드니까 해시테이블Key만 알면 Value에 O(1)의 성능으로 할 수 있음해시함수 로직에 따라 충돌이 날 수 있음→ 연결리스트로 구성해서 데이터들을 연결이렇게 연결리스트로 연결되어있을때는 O(n)의 성능 (처음부터 찾아가야 하니깐) 해시함수의 성능이 매우 중요→ 데이터들을 골고루 분산 시켜줄 수 있는 함수가 좋은 함수 셋중복을 허용하지 않는 자료구조 / HashSet 회고👏 칭찬하고 싶은 점꾸준히 점심시간과 퇴근시간 이후를 사용하여 강의를 듣고 구현을 직접 해봤다. 😅 아쉬웠던 점구현을 할 때 직접 생각보다는 따라쓰고 그 후에 이해하기 바빴던 것 같다. 🔄 보완하고 싶은 점앞으로는 구현을 할 때는 먼저 생각해서 구현을 해보고 다음에 강의를 들으면서 확인하고 수정하는 방향으로 하면 좋을 것 같다. 🎯 다음주의 목표밀리지 않고 지금처럼 강의를 듣고 정리하기스스로 구현 해보면서 깨닫기