블로그 모아보기 - 인프런

인프런 워밍업 클럽 - CS 2주차 과제

운영체제FIFO 스케줄링의 장단점이 뭔가요?장점구현이 간단하고 이해하기 쉽다공정성이 보장된다 - 모든 프로세스가 동등하게 처리된다.기아 현상이 발생하지 않는다.기아 현상 : 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태단점긴 대기 시간을 초래할 수 있다.CPU 사용률이 낮아질 수 있다Burst Time이 짧은 프로세스가 Burst Time이 긴 프로세스 보다 늦게 들어온 경우에 Busrt Time이 짧은 프로세스가 오래 기다려야 한다. SJF를 사용하기 여러운 이유가 뭔가요?어떤 프로세스가 얼마나 실행될지 예측하기 힘들다.→ 예측하는 것이 거의 불가능하다.Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다.→ Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스에게 계속해서 우선순위가 밀린다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?Time Slice를 작게 만드는 경우 Context Switching이 빈번하게 발생된다.→ CPU에서 프로세스가 실행되는 것보다 Context Switching이 빈번하게 발생함에 따라 성능이 떨어진다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하는 경우 CPU 사용률이 낮음→ I/O Bound Process일 확률이 높음CPU를 사용하는 프로세스가 실행하다가 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황인 경우 CPU 사용률이 높음→ CPU Bound Process일 확률이 높음 공유자원이란 무엇인가요?공유자원 : 여러 프로세스나 스레드가 동시에 접근하고 사용할 수 있는 컴퓨터 자원여러 프로세스가 공유하기 때문에 각 프로세스의 접근 순서에 따라서 결과가 달라질 수 있다.컨텍스트 스위칭으로 시분할 처리를 하기 때문에 프로세스간의 실행 순서를 예측하기 어렵다.⇒ 동기화 문제가 발생할 수 있다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호 배제 : 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있다.비선점 : 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없다.점유와 대기 : 프로세스가 이미 자원을 보유한 상태에서 다른 자원을 요청하며 대기한다.원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형이다.자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?무한 재귀가 발생하여 스택 오버플로우 오류가 발생할 수 있다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if (n < 1) { return 0; } if (n % 2 != 0) { return n + sumOdd(n - 2) } return sumOdd(n - 1) } console.log(sumOdd(10)) // 25

알고리즘 · 자료구조･워밍업클럽･CS전공지식･2주차미션

1

인프런 워밍업 클럽 스터디 2기 - CS 전공지식<10월 둘째주 미션>

운영체제1. FIFO 스케줄링의 장단점이 뭔가요?FIFO : 먼저들어간 작업이 먼저 나온다.- 프로세스가 작업이 다 끝나야 비로소 다른 프로세스가 작업할 수 있기 때문에 직관적이고 쉽지만 비효율적이다. 입출력 작업이 들어올 땐 cpu가 그 작업이 끝났다는 메시지만 기다리고 있기 때문에 cpu가 낭비된다.- 먼저 들어간 프로세스의 작업시간이 길수록 오래걸리고 다음에 오는 프로세스들의 대기 시간이 길어진다.그렇게 되면 평균적인 대기시간이 길어지는데 효율이 낮다고 볼 수 있다.짧은 작업시간을 가진 프로세스 먼저 실행하게 되면 뒤에 있는 프로세스들의 대기 시간이 짧아지면서 평균 대기시간도 줄고, 전체적인 효율도 높아진다.단점을 보안하기위해 sjf 이라는 짧은 작업시간 먼저 실행하도록 하는 알고리즘이 생겼다. 2. SJF를 사용하기 여러운 이유가 뭔가요?짧은 평균 대기 시간을 갖을 수 있다. 하지만 대기 중인 프로세스 중에서 계속 짧은 작업시간을 가진 프로세스가 들어온다면 아주 예전부터 대기하던 긴 작업시간을 프로세스들이 무한히 기다리게 될 수있는 상황이 생기게 된다.그렇게 되면 작업수행을 하지 못하는 프로세스들이 생길 수 있게 된다. 또한 프로세스 중에 어떤 것이 짧은 작업시간을 갖는지 구분하기 불가능하기 때문에 SJF 을 사용하기 어렵다. 3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?RR : Round Robin 타임슬라이스를 부여해서 순서대로 온 프로세스들을 스케줄링한다.타임슬라이스 길이를 초과하는 작업이라면 그때까지 한 작업을 강제로 멈추고 프로세스들 중 맨 뒤로 보낸다. 그 후 그 다음 프로세스가 타임슬라이스 동안 작업한다.> 타임 슬라이스가 너무 작을 경우에는 컨텍스트 스위칭이 실행시간보다 더 많이 생겨서 오버헤드가 생긴다.적절한 타임슬라이스로 작업하여 사용자가 사용했을 때 동시에 이용하고 있다는 느낌을 주어야한다.(타임 슬라이스 크기가 크면 FIFO 이랑 똑같이 된다. 오히려 RR 알고리즘이 컨텍스트 스위칭이 일어나 더 비효율적이게 된다.) 4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?MLFQ : 멀티 레벨 피드백 큐. 여러 큐를 준비하고 큐마다 타임슬라이스와 우선순위를 준다.우선순위가 낮을수록 타임슬라이스 값이 커진다.작은 타임 슬라이스를 이용해서 프로세스들을 처리하게 된다. -> 긴 대기 시간을 가진 프로세스 오버헤드🔼 불리함.긴 대기시간을 가진 프로세스도 불이익 없게 하기 위해서는 어떻게 해야할까?-> MLFQ 알고리즘 사용 > CPU Bound Process는 cpu에 할당되어 작업할 것이 많을 텐데 그렇게되면 타임 슬라이스에 비해 오래 걸리기 때문에 자주 cpu를 뺏길 것이다. I/O Bound Process는 cpu 보다 입출력 작업을 더 많이 한다. 그렇게 된다면 분명 cpu를 자주 혹은 빨리 cpu 돌려줄 것이다. 이것을 보고 I/O bound Process 인 것을 예상할 수 있다. 5. 공유자원이란무엇인가요?> 프로세스들간에 작업을 할 때 같이 공통으로 쓰이게 되는 자원.공유자원을 한 프로세스가 사용할 때 다른 프로세스가 차지하지 않도록해야한다.-> 세마포어, 모니터 상호배제 알고리즘이 있다. 6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?> 총 4가지 조건을 충족해야 한다.상호배제 : 작업 중인 프로세스가 공유자원을 사용하는데, 다른 프로세스가 공유자원을 사용비선점 : 프로세스가 하는 작업을 다른 프로세스가 와서 뺏지 않는다.점유와 대기 : 프로세스가 a작업을 하는 중에 다른 b작업을 하려고 대기하는 상태환형대기 : 점유와 대기 모습이 원형 모습으로 서로서로 대기하는 상태 자료구조와 알고리즘1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?기저 조건에 따라 다르지만 프로그램이 멈추지 못하고 영원히 재귀함수를 호출하거나 원하지 않는 결과가 나올 수있다. 2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ // 재귀 로직 if(n < 0) return ;//기저조건 return n+ sumOdd(n-1); } console.log(sumOdd(10)) // 25

알고리즘 · 자료구조･워밍업클럽스터디2기･운영체제･알고리즘

1

[인프런 워밍업 클럽 CS 2기] 2주차 발자국 - 자료구조/알고리즘

운영체제 FIFO 스케줄링의 장단점이 뭔가요? 장점:알고리즘 구현이 간단하다.단점: 프로세스의 Burst Time이 긴 프로세스가 먼저 대기 큐에 들어온다면, 평균 대기 시간이 길어지게 된다.프로세스의 도착 순서에 따라 성능의 편차가 크다. SJF를 사용하기 여러운 이유가 뭔가요?Burst Time이 짧은 프로세스를 우선 실행하는 알고리즘이다. 하지만 운영체제 입장에서 각 프로세스의 실행 예상시간을 파악하기가 어렵다.또한 Burst Time이 긴 프로세스의 경우 CPU 스케줄링에 의하여 CPU 사용 우선수위가 계속 후순위로 밀려서 영원히 실행되지 않는 차별을 겪을 수 있다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?Robin Round는 CPU 스케줄링에 의하여 타임 슬라이스에 따라 인터럽트를 발생하여 각 프로세스 별로 일정시간 동안 CPU 사용권한을 준다. 이때 타임슬라이스가 매우 작으면 CPU에서 프로세스의 코드를 실행시키고 작업하는 것보다 컨텍스트 스위칭을 수행하는 비용이 커져서 overhead가 발생할 수 있다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU 스케줄러는 우선순위 별로 여러 queue를 생성한다. 우선순위가 높은 queue의 타임슬라이스는 짧다.CPU Bound Process의 경우 I/O Bound Process 보다 CPU 점유 시간이 길다. 이때 해당 프로세스가 현재 우선수위 큐의 타임슬라이스 시간까지 작업을 마치지 못하고 CPU 스케줄러에 의해 인터럽트가 발생한다면, 해당 프로세스는 우선순위가 낮은 queue에 포함이 되고 CPU Bound Process일 확률이 높아진다.I/O Bounde Process는 CPU 사용 시간 보다 I/O 작업이 끝나길 기다리는 시간이 많기 때문에 대체적으로 CPU 점유 시간이 짧다. 따라서 MLFQ에서는 다양한 우선순위 큐를 바탕으로 I/O Bound Process와 CPU Bound Process를 구분한다. 공유자원이란무엇인가요?공유자원은 한 프로세스 내의 스레드에서 공통으로 사용하는 자원 혹은 프로세스가 공통으로 접근가능하고 활용할 수 있는 자원을 의미한다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호배제: 먼저 자원을 차지하면 다른 프로세스는 해당 자원을 사용하지 못한다. 비선점: 다른 프로세스가 차지한 자원을 다른 프로세스에서 가져갈 수 없다. 점유와 대기: 어떤 프로세스가 리소스 A를 가진 상태에서 다른 리소스 B를 기다리는 상태이다. 원형 대기: 점유 대기를 하는 프로세스의 관계가 원형을 이룬다. 자료구조와 알고리즘 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?스택 overflow 문제가 발생한다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n) { if (n <= 0) { return 0; } if (n % 2 === 0) { return n - 1 + sumOdd(n - 3); } else { return n + sumOdd(n - 2); } } console.log(sumOdd(10)); // 25 회고가장 인상 깊은 부분은 재귀함수를 설명하는 부분입니다. 재귀함수의 특징으로 하위 문제의 결과를 기반으로 상위 문제를 해결 이라는 설명이 가장 와 닿았고 이후 재귀를 이해하고 활용하는 것에 큰 도움이 되었습니다!

1

[Gen AI 인사이트] GPT 성능을 극대화하는 프롬프트 엔지니어링 전략 (3)

똑똑하게 업무를 처리하는 방법, 마소캠퍼스가 알려드릴게요!최신 AI 기술로 더욱 효율적이고 스마트하게 일해보세요.GPT 활용의 모든 것,프롬프트 엔지니어링으로 성능을 극대화하세요!프롬프트 엔지니어링은 AI 모델에서 원하는 결과를 얻기 위한 핵심 전략입니다.이 가이드를 통해 GPT의 성능을 극대화하는 방법을 알아보세요.모델에게 시간을 주면 더 나은 결과를 얻을 수 있습니다.예를 들어, 복잡한 계산 문제를 바로 풀기보다는 시간을 주고 해결하도록 유도해보세요.이렇게 하면 더 정확한 답변을 얻을 수 있습니다.먼저 AI 모델에게 스스로 해결책을 찾도록 한 후, 그 결과를 평가하세요.이렇게 하면 문제 해결 능력을 키우고 더 나은 성과를 기대할 수 있습니다.추론 과정을 숨기고 바로 정답만을 얻고 싶을 때 이 전략을 사용하세요.필요에 따라 중요한 정보를 제외한 나머지 과정을 생략할 수 있습니다.복잡한 작업을 할 때, 가끔 놓친 부분이 있을 수 있습니다.특히, 여러 질문과 답변이 이어질 때는 더 그렇죠.이럴 때는 이전 단계에 놓친 내용이 있는지, 또는 필요한 모든 정보가 포함되었는지 확인하는 과정이 중요해요.AI 모델의 약점을 보완하기 위해 외부 도구를 활용하세요.예를 들어, 코드를 실행하여 더 정확한 계산을 하거나,임베딩 기반 검색으로 원하는 정보를 쉽게 찾을 수 있습니다.프롬프트를 수정한 후에는 반드시 성능이 향상되었는지 테스트하세요.정답을 명확히 할 수 있는 질문을 통해 결과를 분석하고 최적의 답변을 찾는 것이 중요합니다.오늘 확인한 프롬프트 엔지니어링 전략을 직접 적용해보세요.생산성 향상은 물론, 더 효율적인 업무 환경을 조성할 수 있습니다.GPT는 끊임없이 발전하고 있습니다.이를 최대한 활용하기 위해서는 꾸준한 학습과 적용이 필요합니다.최신 정보를 지속적으로 업데이트하여 업무에 반영하세요.📌 관련 강의 <ChatGPT 고급 활용법 - 남들보다 100배 더 잘 쓰는 ChatGPT 비법 클래스>쉽고 확실한, 최고의 GPT 강의!고급 활용법까지 단계별로 배우기만 하면 내 연봉의 숫자가 달라집니다.>> https://bit.ly/4dJEGbW <<

AI · ChatGPT 활용･gpt활용･챗gpt･It전략･생성AI･AI트렌드･업무효율화･비즈니스･프로그래밍･업무팁･AI기술

1

인프런 워밍업 클럽 - CS Day 6

AlgorithmRecursion(재귀)어떠한 것을 정의할 때 자기 자신을 참조하는 것을 의미한다.재귀함수 : 재귀적으로 정의된 함수재귀함수는 콜스택이라는 메모리 가득차게 되는 경우 자동으로 종료된다.기저 조건 : 재귀함수가 종료될 수 있는 탈출 조건기저 조건이 반드시 있어야 정상적으로 수행할 수 있다.재귀함수는 함수를 호출할 때마다 Call Stack이라는 메모리 공간에 호출정보가 저장된다.→ 재귀함수는 Loop문보다 더 많은 메모리 공간을 차지한다.Call Stack(= Stack)함수가 호출되면서 올라가는 메모리 영역함수가 종료되면 콜스택에서 제거된다.FILO(First-In Last-Out)재귀함수를 사용하는 이유Loop를 대신한다기 보다는 더 복잡한 문제를 쉽게 해결하기 위해 사용된다.ex) Factorial재귀함수를 쉽게 작성하는 방법재귀함수 내에서 자기 자신을 호출할 때 해당 함수가 벌써 구현이 되어있다고 가정한다.5! = 5 * 4 * 3 * 2 * 1 5 * factorial(4) 4! = 4 * 3 * 2 * 1 4 * factorial(3) → factorial(number) = number * factorial(number - 1) OSCPU Scheduling AlgorithmSJF(Shortest Job First)Burst Time이 짧은 작업부터 CPU를 할당한다.문제점어떤 프로세스가 얼마나 실행될지 예측하기 힘들다.→ 예측하는 것이 거의 불가능하다.Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다.→ Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스에게 계속해서 우선순위가 밀린다.⇒ 사용되지 않는다.RR(Round Robin)하나의 프로세스에게 일정 시간만 CPU를 할당하고 할당된 시간이 지나면 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당하는 방식→ 강제로 CPU를 뺏긴 프로세스는 Queue의 가장 마지막으로 밀려난다.Time Slice(=Time Quantum) : 프로세스에게 할당하는 일정 시간Time Slice에 따라서 RR의 성능이 좌지우지된다.Time Slice를 작게 만드는 경우 Context Switching이 빈번하게 발생된다.→ Context Switching이 빈번하게 발생함에 따라 성능이 떨어진다.Time Slice가 큰 경우 FIFO와 동일하게 동작한다.Time Slice 예시Window Time Slice : 20msUnix Time Slice : 100ms단점Context Switching이 존재한다.→ 평균 대기시간이 FIFO와 동일하다면 FIFO가 더 성능이 좋다.MLFQ(Multi Level Feedback Queue)RR의 업그레이드 버전주로 사용되는 CPU 스케줄링 알고리즘CPU Bound Process : CPU를 할당받은 시간을 대부분 CPU 연산을 수행하는 프로세스CPU 사용률과 처리량이 중요I/O Bound Process : 대부분의 시간을 I/O 작업에 수행하고 적은 시간만 CPU 연산을 하는 프로세스- 응답시간이 중요MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 Time Slice를 사용한다.CPU Bound Process에게는 CPU 사용률을 높이기 위해 Time Slice를 높게 할당한다.I/O Bound Process에게는 I/O 사용률을 높이기 위해 Time Slice를 낮게 할당한다.OS는 어떻게 CPU Bound Process와 I/O Bound Process를 구분할까?CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하는 경우 CPU 사용률이 낮음→ I/O Bound Process일 확률이 높음CPU를 사용하는 프로세스가 실행하다가 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황인 경우 CPU 사용률이 높음→ CPU Bound Process일 확률이 높음구현 방법우선순위를 갖는 큐를 여러개 준비한다.우선순위가 높으면 Time Slice가 작다.우선순위가 낮아질수록 Time Slice가 커진다.

알고리즘 · 자료구조･워밍업클럽･CS전공지식･DAY6

1

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

1. 전반적인 학습내용운영체제의 역사부터 전반적인 흐름, 프로세스와 CPU 스케줄링에 대해서 배웠고, 자료구조 및 알고리즘 파트에서는 일반적인 배열(+Js 배열)과 스택, 연결리스트, 큐, 해시테이블 등에 대해서 배웠다. 2. 일주일 간의 회고사실 난 강의 수집가다 ^00^,, 초반엔 잘 듣다가도 금방 흐지부지되는 경우가 되게 많았었는데, 강제적으로 스터디 클럽에 들어가서 어떻게서든 강의를 수강해야 하는 과정이 일단 너무 좋았다. 물론 간혹가다가 일정이 발생해서 강의가 조금씩 밀리는 경우가 생기긴 했지만,, 그럼에도 이번주 목표하는 바를 다 학습했다. 특히 자료구조 학습 시에는 강의를 보고 코드를 그냥 따라치지 않고 먼저 구현해본 후에 강의를 재생했다. 게다가 그림자료가 너무 친절해서 자료구조를 그냥 먹기 쉽게 다 으깨서 떠먹여주는 것 같았다 ,, 강의 하나 수강할 때마다 이해가 너무 잘 돼서 되게 짜릿했음그리고 너무 부끄럽지만 자료구조나 운영체제 등을 제대로 공부해본 적이 없다. 자료구조나 알고리즘은 .. 그냥 코딩테스트를 위해서 하는 거 아닌가라는 안일한 생각을 했었다. 이번주 강의를 들으면서 소프트웨어 개발을 위해서 기본 CS 지식은 진짜 너무 당연한 것이라는 걸 뼈저리게 느껴서 반성과 부끄러움을 많이 느낀 한 주였다. 그래도 간만에 강의 들으면서 의욕이라는 게 확 올라온 듯, 처음 개발을 배우기 시작할 때로 돌아간 것 같아서 좋았다. 수료할 때까지 쭉 꾸준하게 달려야겠다. 3. 다음주 목표학습한 내용 바탕으로 1일 1커밋 꼭 해보기

1

첫번째 발자국

'그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)'수강생 여러분께 하고 싶은 말외우려 하지 말고 이해해라 어렵다면 그림으로 풀어서 이해해라당장 이해하기 어렵다면 특징만 외우고 나중에 다시 공부하기이해를 했다면 기억도 오래 남고 특징들을 유추할 수 있다자료구조와 알고리즘이란?자료구조는 데이터가 어떤 구조로 저장되고 사용되는지를 나타낸다. (ex. int, float, 정적배열, 동적배열, 연결리스트 등)알고리즘은 어떤 문제를 해결하기 위한 확실한 방법이다.자료구조에 따라 알고리즘이 달라진다.어떤 구현을 할 때 하나의 자료구조가 하나의 알고리즘만을 사용할 수 있는건 아니다. 상황에 맞는 적절한 자료구조와 알고리즘을 적용할 수 있어야 한다.시간복잡도더 좋은 알고리즘이란 무엇일까? 이는 사용자의 요구에 따라 변한다. 보통 메모리, 속도로 구분되며 일반적으로 알고리즘의 속도를 성능의 척도로 사용시간복잡도란 특정 알고리즘이 어떤 문제를 해결할 때 걸리는 시간이며 사용자의 PC성능에 따라 시간 측정은 달라질 수 있으므로 코드에서 성능에 많은 영향을 주는 것을 찾아 실행 시간을 예측하는 것이다.시간복잡도는 최악의 경우를 표현하는 빅 오 표기법을 사용한다.빅 오 표기법은 가장 큰 영향을 미치는 항으로만 표현한다.보통 자료구조의 시간복잡도는 평균, 최악의 경우를 생각한다.자료구조배열연속된 메모리 공간을 할당 받는다.운영체제는 배열의 시작 주소만 기억한다.순차적으로 메모리가 적재되고 운영체제가 배열의 시작 주소를 알기에 인덱스를 통해 접근 가능하다.삽입, 삭제 시 공간이 부족하거나 중간에 있는 요소를 삭제 시 데이터에 대한 이동이 필요해서 오버헤드가 많이 발생한다.인덱스 참조 O(1) / 삭제, 삽입 성능 O(n)연길리스트배열의 단점을 해결하기 위해 만들어진 자료구조저장하려는 데이터들을 메모리 공간에 분산하여 할당하고 이 데이터들을 서로 연결이는 노드라는 것을 만들어 수행노드의 구조는 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나이러한 노드끼리 연결시킨것을 연결리스트라 한다.연결리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근 가능.삽입, 삭제시 다음 가리키는 노드만 바꿔주면 된다. / 삽입, 삭제 O(1)메모리 공간이 분산되어 있기에 인덱스 참조가 불가능 즉, 모든 노드 순회해야함 / 참조 O(n)스택First In Last Out (FILO)먼저 들어간 데이터가 나중에 나오는 자료구조삽입, 삭제, 참조 O(1) / 맨 위에 요소만 가능연결리스트, 배열 등으로 구현 가능사용 예제명령 / Undo, Redo문법 괄호 검사큐와 병행하여 회문 검사큐First In First Out (FIFO)먼저 들어간 데이터가 먼저 나오는 자료구조삽입, 삭제, 참조 O(1) / 맨 앞에 요소만 가능이중 연결리스트, 배열등으로 구현 가능사용예제대기열 / 마트 계산대, 게임 큐, 식당 줄 등운영체제 프로세스 작업 요청 / FIFO 스케줄링덱데이터의 삽입과 제거를 Head와 Tail 양쪽에서 자유롭게 할 수 있는 자료구조양방향 끝 삽입 삭제, 참조 O(1) / 가운데 O(n)해시테이블Key와 Value로 이루어진 자료구조Key를 이용한 해시함수를 통해 데이터를 저장만약 해시 충돌이 발생할 경우, 해당 인덱스의 연결리스트에 삽입해시함수의 구현에 따라 공간의 낭비가 극대화될 수도 최적화될 수도 있다.최고의 효율 : 참조, 삽입, 삭제 O(1)최악의 효율 : 참조, 삽입, 삭제 O(n)셋데이터의 중복을 허용하지 않는 자료구조해시 테이블을 활용하기에 해시 셋이라고도 불린다.셋은 헤시 테이블의 Value값은 사용하지 않고 Key만 사용해 구현한다.Key가 Key인 동시에 데이터로 사용하는 것'그림으로 쉽게 배우는 운영체제'운영체제 개요프로세스 관리 메모리 관리 하드웨어 관리 파일 시스템 관리운영체제의 구조운영체제의 핵심 커널은 프로세스와 메모리, 저장장치를 관리한다.사용자는 커널에 직접 접근할 수 없고 인터페이스를 통해 접근 가능하다. (GUI, CLI)어플리케이션은 시스템 콜을 통해 커널에 접근 가능하며, 이를 통해 메모리를 사용할 수 있다.하드웨어는 드라이버를 통해 커널에 접근 가능하다. 컴퓨터 하드웨어와 구조하드웨어로 프로그램을 만들었기에 프로그램이 달라질 때마다 매번 스위치와 배선을 다시 조정해야 했다.폰 노이만은 이를 해결하기 위해 CPU와 메모리를 두고 이들 사이는 버스로 연결한다.버스는 데이터를 전달하는 통로이다.메모리에 올라간 프로그램은 명령에 따라 처리된다.컴퓨터 하드웨어메인보드다른 하드웨어를 연결하는 장치장치 간에 데이터를 전송하는 건 메인보드의 버스가 담당.CPU메모리하드디스크그래픽카드마우스, 키보드, 사운드, 모니터 입출력 장치 CPU(Central Processing Unit)산술논리연산장치(Arithmetic and Logic Unit, ALU) : CPU 에서 실제로 데이터 연산을 담당제어장치 : 모든 장치들의 동작을 지시하고 제어레지스터 : CPU 내에서 계산을 위해 데이터를 임시로 보관하는 장치 메모리 종류RAM(Random Access Memory)랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 읽는 속도가 같다.전력이 끊기면 데이터를 잃는다(휘발성) / 메인 메모리로 사용ROM(Read Only Memory)전력이 끊겨도 데이터를 계속 보관 가능데이터를 한 번 쓰면 수정 불가능컴퓨터의 부팅과 관련된 바이오스를 저장하는데 사용컴퓨터의 부팅과정ROM에 저장된 BIOS 실행BIOS는 전원, CPU, 메모리, 키보드, 마우스, 하드디스크 등 주요 하드웨어에 이상이 없는지 확인하드디스크에 있는 마스터 부트 레코드에 저장된 부트로더를 메모리에 가져와 실행설치된 운영체제 실행, 메모리에 불러온다.바탕화면이 나오고 실행되는 모든 응용 프로그램은 메모리에 올라가 운영체제가 관리인터럽트입출력 처리 방식폴링CPU가 주기적으로 입출력 장치의 상태를 확인하는 방식효율성이 떨어지고 자원 낭비 심함인터럽트폴링 방식을 개선한 현재 사용되는 방식입력이나 출력이 발생하면 CPU에 인터럽트를 발생CPU는 현재 작업을 중단하고, 이 인터럽트를 처리하기 위해 인터럽트 처리 루틴(Interrupt Service Routine, ISR)로 이동 및 처리완료 후 다른 작업 수행프로세스와 쓰레드프로그램과 프로세스프로그램은 저장장치에 저장된 명령문의 집합체프로세스는 프로그램이 메모리에 올라가 실행중인 프로그램을 의미멀티프로그래밍과 멀티프로세싱멀티프로그래밍은 메모리에 여러 개의 프로세스가 올라간 것.멀티프로세싱은 CPU를 시분할로 여러 개의 프로세스를 처리하면서 동시에 실행되는 것처럼 보이게 하는 것.과거에는 메모리가 작기에 멀티프로그래밍이 불가하여 다른 저장장치에 있는 프로그램을 메모리에 올리는 스와핑을 통해 멀티프로세싱을 처리했다.PCB프로세스가 생성될 때 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB(Process Control Block)를 만들어 저장한다.운영체제는 PCB들을 연결리스트로 관리한다.PCB의 구조포인터 : 부모와 지식 프로세스에 대한 포인터 / 할당된 자원에 대한 포인터 / 프로세스 상태 전환시 저장하는 포인터프로세스 상태 : 생성, 준비, 실행, 대기, 완료프로세스 ID : 식별자프로그램 카운터 : 다음에 실행될 명령어의 주소 저장 / 프로세스가 실행되던 지점 저장레지스터 정보 : 프로세스가 실행될 때 사용했던 레지스터 값들메모리 관련 : 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기 위한 경계레지스터 값등 저장CPU 스케줄링 정보 : CPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간 등이 저장등등프로세스 상태운영체제는 시분할 시스템을 활용하여 여러 개의 프로세스를 빠르게 전환하며 실행시킨다.시분할 처리를 위한 다섯가지 상태생성(New) : PCB를 생성하고 메모리에 프로그램 적재를 요청한 상태준비(Ready) : CPU를 사용하기 위해 기다리는 상태대기(Waiting) : 프로세스가 입출력 요청을 하면 입출력이 완료될 때 까지 기다리는 상태 / CPU는 굉장히 빠르고 입출력 작업은 상당히 느리다. 입출력 요청을 하는 프로세스가 완료될 때 까지 CPU를 기다리게 하는 것은 비효율적이기에 대기 상태가 만들어졌다.실행(Running) : CPU 스케줄러에 의해 CPU를 할당받아 실행되는 상태 / 실행상태에 있는 프로세스의 수는 CPU의 개수만큼 존재할 수 있다.완료(Terminated) : 프로세스가 종료된 상태 / 프로세스가 사용했던 데이터를 메모리에서 제거하고 PCB도 제거 컨텍스트 스위칭컨텍스트 스위칭은 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업을 의미.컨텍스트 스위칭이 일어날 때 PCB의 내용이 변경된다.실행중인 프로세스의 작업내용을 PCB에 저장하고 실행될 프로세스의 PCB의 내용대로 CPU가 다시 세팅된다.컨텍스트 스위칭이 일어날 때 PCB에 변경되는 값들은 아래와 같다.프로세스 상태프로그램 카운터레지스터 정보메모리 관련 정보 프로세스의 CPU 점유시간을 초과하거나 입출력 작업요청 등이 들어오면 인터럽트가 발생하며 컨텍스트 스위칭이 일어난다.프로세스 생성과 종료실행파일이 실행되면 운영체제는 해당 프로그램의 코드영역과 데이터영역을 메모리에 로드하고빈 스택과 빈 힙을 만들어 공간을 확보하며 이 프로세스를 관리하기 위한 PCB를 만들어서 값을 초기화해준다.해당 프로세스 생성 과정은 운영체제가 부팅되고 0번 프로세스가 실행될 때 딱 한번 실행된다.그 이후에 프로세스는 새로 생성하지 않고 0번 프로세스를 복사(fork함수)해서 사용한다.새로 생성하는 것 보다 복사를 하는 게 더 빠르다.exec함수를 통해 부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓴다.exit함수는 자식 프로세스가 부모 프로세스에게 정상 종료를 알리는 함수이다. / 부모 프로세스의 경우 종료부모 프로세스는 자식 프로세스의 Exit Status를 읽고 자식 프로세스를 정리한다.만약 부모 프로세스가 자식 프로세스보다 먼저 종료 되거나 자식 프로세스가 비정상적으로 종료되어 exit()신호를 주지 못해서 Exit Status를 읽지 못해 메모리에 계속 살아 있는 상태를 좀비 프로세스라고 한다.컴퓨터를 오래 켜두면 느려지는 현상이 발생하곤 하는데 메모리에 많은 프로세스가 올라오는 경우거나 좀비 프로세스가 메모리를 차지하기 때문이다.컴퓨터를 껏다키면 메모리가 초기화 되기에 다시 빨라진다.쓰레드사용자가 운영체제에게 작업을 요구하면 그만큼 프로세스 수가 증가프로세스는 메모리에 코드, 데이터, 스택, 힙영역, PCB를 할당해준다.프로세스끼리의 통신은 IPC(Inter Process Comunication)를 이용 / 해당 작업은 비용이 많이 든다.이러한 단점들을 해결하기 위해 고안된 것이 쓰레드이다.쓰레드는 프로세스 내에 존재하는 것으로 1개 이상이 있을 수 있다.쓰레드는 프로세스의 PCB, 코드, 데이터, 힙영역을 공유한다.스택은 공유하지 않고 쓰레드 마다 고유하다.한 프로세스 내에 쓰레드가 여러개 존재하기에 쓰레드 ID, TCB(Thread Control Block)가 생겼다.이제 운영체제가 작업을 처리하는 단위는 프로세스 내에 쓰레드이다.특징안전성 : 프로세스는 서로 독립적이기에 하나의 프로세스가 문제가 있더라도 다른 프로세스는 영향을 받지 않는다.반면 쓰레드는 하나의 프로세스 내에 존재하기에 해당 프로세스에 문제가 생기면 그 안에 모든 쓰레드에 문제가 생긴다.속도, 자원 : 각각의 프로세스는 서로 고유한 자원을 가진다 / 코드, 데이터, 힙, 스택영역을 전부 따로 둔다. 프로세스간의 통신을 하려면 IPC를 이용해야해서 오버헤드가 크고 속도가 느리다.반면 쓰레드는 한 프로세스내에서 스택영역을 제외한 영역은 모두 공유하기에 오버헤드가 굉장히 작다. 쓰레드간의 통신은 데이터를 공유할 수 있으니 쉽게 가능하지만 공유되는 공간에서 문제(공유자원 문제)가 발생할 수 있다. CPU 스케줄링CPU 스케줄링 개요CPU 스케줄링은 운영체제가 모든 프로세스에게 CPU를 할당/해제하는 방식을 의미한다.CPU 스케줄링에서 스케줄러(운영체제)가 고려해야할 사항은어떤 프로세스에게 CPU 리소스를 줘야하는가?CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?두 가지이다.이 두 가지 고려사항이 컴퓨터의 성능에 굉장히 큰 영향을 미친다.이 고려사항을 통해 여러 CPU 스케줄링 방식이 만들어진다.CPU를 할당받아 실행하는 작업을 CPU Burst라 부른다.입출력 작업을 I/O Burst라고 부른다.다중큐해당 프로세스의 우선순위를 보고 준비큐에 넣는다.CPU 스케줄러는 준비상태의 다중큐에 들어있는 프로세스들 중에 적당한 프로세스의 정보(PCB)를 선택해서 실행상태로 전환시킨다프로세스 정보를 담고 있는 PCB가 준비상태의 다중큐에 들어가서 실행되기를 기다리고 있고CPU 스케줄러에의해 실행상태로 전환된다.이때 CPU 스케줄러는 준비상태의 다중큐를 참조해서 어떤 프로세스를 실행시킬지 결정.스케줄링 목표리소스 사용률 : CPU 사용률을 높이는 것, I/O 디바이스 사용률 높이는 것오버헤드 최소화 : 스케줄링을 위한 계산, 컨텍스트 스위칭 오버헤드 비용 최소화공평성 : 모든 프로세스에게 스케줄링 기법에 맞춰 공평하게 CPU가 할당되어야 한다.처리량 : 같은 시간 내에 더 많은 처리를 할 수 있는 방법을 목표로 한다.대기시간 : 작업을 요청하고 실제 작업이 이루어지기 전까지 대기하는 시간이 짧은 것을 목표로 한다.응답시간 : 응답시간이 짧은 것을 목표로 한다.모든 목표를 만족할 수 없기에 사용자가 사용하는 시스템에 따라서 목표를 다르게 설정해야 한다.특별한 목적이 없을 경우, 밸런스를 유지하는게 중요.FIFO먼저 들어온 작업이 먼저 처리되는 스케줄링 방식스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식 / 해당 방식은 프로세스가 완전히 끝나야만 다음 프로세스가 실행될 수 있다.단점실행중인 프로세스가 완전히 끝나야 다음 프로세스가 실행되는데, 만약 현재 실행중인 프로세스 작업이 길고, 다음 프로세스가 엄청 짧아도, 다음 프로세스는 대기해야 한다. / 효율성(처리량, 대기시간)이 떨어진다.I/O 작업이 있다면 해당 작업이 끝날때까지 CPU가 쉬게되어 CPU 사용률이 떨어진다.스케줄링의 성능은 평균 대기 시간으로 평가된다.평균 대기 시간은 프로세스들 모두가 실행되가끼지 대기시간의 평균을 의미한다. Burst Time이 짧은게 먼저 실행되면 평균 대기 시간 짧아짐.Burst Time이 긴게 먼저 실행되면 평균 대기 시간 길어짐. FIFO알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나기에 현대 운영체제에서 잘 쓰이지 않고 일괄처리 시스템에 쓰인다.

감자･인프런강의･발자국

1

인프런 워밍업 클럽 스터디 2기 - CS 전공지식<10월 첫째 주 발자국>

⭐10월 첫 째주 회고배운 내용CS => 프로세스가 중심!운영체제란?, 운영체제와 프로세스와의 관계프로세스가 효율적으로 돌아가려면 필요한 것 - pcb, 인터럽트, 쓰레드cpu 스케줄링이란? 프로세스가 상황에 맞게 효율적으로 실행하는 방식 Algorithm배열을 기반으로 링크드 리스트, 큐, 스택, 덱, 해시테이블까지. 효율적이고 상황에 맞는 알고리즘이번주 수업은 어땠나알고리즘과 운영체제를 학과에서 수업하고 내용도 듣게 되면 다 알아듣고 무슨 내용인지 안다.그런데 항상 느꼈던 게 수업에서 들었던 내용이 내 것이라고 느껴지지 않았다.시험때문에 달달 외웠던 내용들. 왜 이렇게 되고 언제사용하는지 어떻게 사용하는지는 전혀 몰랐던 것 같다.내가 지금까지 대학교에서 공부한 건 뭐였지 이런 생각이 들면서 이것저것 해보기 시작했다.그래서 인프런 워밍업 스터디도 시작하게 되었다.시간에 쫓겨서 알맹이만 알아가려고 급하게 필기하기 보다는 내용을 이해하고 혼자서 수업을 정리할 수 있었으면 좋겠다. ⭐미션운영체제1.```Cwhile(true){wait(1); // 1초 멈춤bool isActivated = checkSkillActivated(); // 체크}```위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다.이 방식은 폴링방식입니다.1초마다 체크하기 때문에 성능에 좋지 않습니다.이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?인터럽트 방식으로 cpu가 입출력 신호만 기다리지 않고 자기 할 일하면서 신호가 왔을 때 명령을 실행한다. 2. 프로그램과 프로세스가 어떻게 다른가요?프로그램 - 저장장치만 사용하는 명령어프로세스 -저장장치뿐만아니라 입출력과 운영체제 cpu 스케줄링 등 모두 사용한다. 3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?관점에 따라 다르게 부르게 되었다. 멀티 프로그래밍은 메모리 관점에서, 멀티프로세싱은 cpu 관점에서 프로세스를 처리하는 방식이다. 4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?pcb를 사용한다. 프로세스에는 프로세스 정보를 가진 조그만한 애가 있다. 그걸 pcb라고 부르는데 아래 컨텍스트 스위칭에서 사용되는 것이다.프로세스가 생성될 때 같이 만들어지고 종료될 때 해당 프로세스의 pcb도 삭제되는 프로세스를 위해 있는 운명이다. 5. 컨텍스트 스위칭이란 뭔가요?프로세스를 실행할 때 모종의 이유로(할당된 시간이 끝났을 때 등) 다른 프로세스로 교체할 때가 생긴다.원래 실행하고 있던 프로세스를 어디까지 일을 했는지 저장하고(상태저장) 새로 들어온 프로세스는 상태저장된 것을 확인하고 그 상태부터 실행 시키는 일. 자료구조와 알고리즘1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요?이유를 함께 적어주세요.key 값과 hash 라는 인덱스번호가 부여되는데 key값을 학생의 정보인 이름으로 설정하게 된다. 배열이나, 큐, 스택과 다르게 이름을 찾을 때가지 참조하는 것과는 다르게 해쉬테이블은 참조하는 시간이 확연하게 줄어들 것이라고 예상된다. 2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다.주문은 들어온 순서대로 처리됩니다.이 때 여러분이라면 어떤 자료구조를 선택하실 건가요?이유를 함께 적어주세요.들어온 순서대로 처리되는 큐 자료구조를 선택할 것같다. 큐는 first in first out이다. 주문도 처음들어오는 순으로 주문에 해당하는 음식을 만들어서 보내고 그 다음 주문을 처리한다.

알고리즘 · 자료구조･알고리즘･운영체제

1

[스터디] 인프런 CS 전공지식 스터디 2기_(1주차)

자료구조와 알고리즘발자국Tistory linkhttps://narmhye.tistory.com/265 미션여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. 일반적인 배열인 Array 구조를 선택할 것이다.학생 수는 초기 구성 이후 일정 기간 동안 변동이 생길 경우가 드물기 때문에,정보 열람이 프로그램의 주 사용 기능이 될 것이다.따라서 삽입/삭제보다는 참조의 효율이 좋은 array를 선택하였다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.LinkedList로 구현한 Queue를 선택할 것이다.주문의 삽입/삭제의 처리가 주로 이루어져 효율적인 LinkedList를 기반으로,FIFO의 구조를 가지는 Queue를 선택하였다. 운영체제발자국Tistory linkhttps://narmhye.tistory.com/266 미션1.while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?인터럽트 프로그램과 프로세스가 어떻게 다른가요?프로그램은 명령문의 집합체로 수동적인 존재이다.프로세스는 실행중인 프로그램으로 메모리, CPU, 입출력 장치를 사용하는 능동적인 존재이다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 메모리의 관점에서 여러 개의 프로세스가 올라온 것,멀티프로세싱은 CPU 관점에서 여러 개의 프로세스를 처리한 것 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB를 연결리스트로 저장하여 사용. 컨텍스트 스위칭이란 뭔가요?기존 프로세스 실행 중, 다른 프로세스를 실행하기 위하여 기존의 프로세스 상태 저장 후, 다른 프로세스의 상태값으로 변경하는 것 - PCB 내용을 셋팅

알고리즘 · 자료구조

1

[인프런 워밍업 클럽 CS 2기] 1주차 발자국 - 자료구조/알고리즘

[ Section 1. 개요 ]1. 자료구조와 알고리즘이란?프로그램은 자료구조와 알고리즘으로 이루어진다.프로그램 작성 시 적절한 자료구조를 선택하여 데이터를 저장하고, 자료구조에 맞는 알고리즘을 사용해 데이터를 가공하여 원하는 결과를 도출한다.1) 자료구조자료구조란?데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타낸다.단순한 자료구조 : 변수, 배열자료구조에 따라 처리방법이 달라지며 데이터의 변경시 코드가 더 단순해질 수도 있다.2) 알고리즘알고리즘이란?어떤 문제를 해결하기 위한 확실한 방법데이터가 어떤 자료구조를 하고 있는지에 따라 알고리즘이 달라진다.알고리즘은 자료구조에 많은 영향을 받는다.한가지 자료구조에 대해서도 여러가지 알고리즘이 있을 수 있다. 2. 시간복잡도1) 시간복잡도특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간의 효율성을 나타내는 척도를 말한다.알고리즘의 성능을 평가할 때 처리 속도를 중요한 기준으로 사용하지만, 컴퓨터의 사양에 따라 실제 속도는 달라질 수 있다.따라서, 실제 시간을 측정하는 것보다 알고리즘에서 성능에 영향을 미치는 핵심 연산을 기반으로 실행 시간을 예측하는 방식으로 시간복잡도를 평가한다.2) 시간복잡도 평가시 점근 표기법(Asymptotic Notation)의 사용3가지 종류의 표기법이 사용된다.Big-Ω, Big-O, Big-Θ표기법중 Big-O와 Big-Θ를 주로 사용하며, 가장 많이 사용되는것은 Big-O 이다.1) 빅 오메가 표기법 (Big-Ω, Big-Omega Notation, Ω)최선의 경우를 나타내는 표기법2) 빅 오 표기법 (Big-O, Big-O Notation, O)최악의 경우를 나타내는 표기법3) 빅 세타 표기법 (Big-Θ, Big-Theta Notation, Θ)평균적인 경우 또는 정확한 시간 복잡도를 나타낸다.3) 시간복잡도 분류(1) 선형시간 알고리즘 O(n)입력량이 많아지는 경우 계산량이 증가하므로 O(n)의 알고리즘은 선형시간 알고리즘이라고 부른다.(2) 상수시간 알고리즘 O(1)입력량의 크기에 상관없이 상수의 시간이 걸린다는 의미로 계산량이 꼭 한 번일 필요는 없다.4) 빅 오(Big-O) 표기법의 특징빅 오(Big-O) 표기법은 입력의 크기에 따라 알고리즘의 계산량이 어떻게 변하는지를 나타내는 척도를 제공한다.빅 오(Big-O) 표기법에서는 성능에 가장 큰 영향을 미치는 항만 표기한다.ex) n**²** + 2n + 100 이라는 성능을 가진 알고리즘의 빅 오 표기법은 O(n**²**) 이다.빅 오(Big-O) 표기법에서 상수는 성능에 큰 영향을 미치지 않으므로 제거한다.ex) 3n**²** + 100n 성능의 알고리즘을 빅 오 표기법으로 나타내면 O(n**²**) 이다.[ Section 2. 자료구조 ]1. 배열(1) 배열의 특징일반적으로 프로그래밍 언어에서 배열을 선언할 때 크기를 지정해야 하며, 운영체제는 크기에 맞는 연속된 메모리 공간을 할당한다.운영체제는 배열의 시작 주소만 기억하며, 인덱스를 이용해 O(1)의 성능으로 데이터를 참조할 수 있다.배열을 읽기/쓰기 와 같은 참조에서 빠른 성능을 보인다.배열의 크기를 확장할 수 없기 때문에 데이터 추가/제거 시 성능 저하가 발생한다.배열을 확장하려면 새로운 메모리 공간을 할당하고 기존 데이터를 복사해야 함.배열을 미리 크게 선언하거나 사용하지 않는 공간이 있을 경우 메모리 공간이 낭비될 수 있다.(2) 배열의 장단점장점 : 인덱스 접근에서 빠른 성능(O(1))을 제공한다.단점 : 크기를 미리 정해야 하며, 삽입/삭제가 비효율적이고, 메모리 낭비 가능성이 있다. 2. 연결 리스트 (Linked List)연결 리스트 (Linked List)연결 리스트는 노드(Node)라는 것을 만들어서 수행한다.첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근할 수 있다.(1) 장점배열처럼 초기 크기를 알아야 하는 단점이 없다빈 메모리 공간 아무 곳에 데이터를 생성하고 연결만 해주면 됨데이터 삽입시 다음 가리키는 노드만 바꿔주면 되기 때문에 배열보다 작업이 간단함(2) 단점데이터를 찾을때 연속된 노드를 순회하여 데이터를 참조해야 함연결 리스트에서 데이터 참조는 O(n)의 성능3. 스택 (Stack)스택은 마지막에 삽입된 데이터가 먼저 제거(LIFO, Last In First Out)되는 구조를 가진다.데이터의 삽입과 제거는 항상 맨 앞(head/top)에서만 이루어진다.스택은 LIFO 규칙만 충족하면 어떤 자료구조로도 구현할 수 있다.FILO (First In Last Out)먼저 들어간 데이터가 나중에 나오는 규칙4. 큐 (Queue)먼저 들어온 데이터가 먼저 나가는(FIFO, First In First Out) 구조를 가진다.데이터의 삽입은 tail(rear)에서, 제거는 head(front)에서 이루어진다.FIFO (First In First Out)먼저 들어간 데이터가 먼저 나오는 규칙운영체제에서 FIFO 스케줄링이 사용된다.운영체제가 프로세스의 작업 요청을 들어온 순서대로 큐에 넣고 CPU가 순서대로 꺼내어 처리한다.5. 덱 (Deq)데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 자료구조덱을 이용하여 스택과 큐를 전부 구현할 수도 있다.덱 (Deq)의 추상 자료형printAll - 모든 데이터 출력addFirst - head에 데이터 삽입하는 함수 removeFirst - head에서 데이터 제거하는 함수 addLast - tail에 데이터 삽입하는 함수 removeLast - tail에서 데이터 제거하는 함수 isEmpty - 리스트가 비었는지를 알려주는 함수6. 해시테이블 (Hash Table)Key를 Hash 함수를 통해 특정 위치에 매핑하여 데이터를 저장하는 자료구조이다.해시와 테이블이 결합된 형태로, 해시 함수를 사용하여 테이블의 인덱스를 생성한다.프로그래밍 언어에 따라 다양한 이름으로 불린다.예 : 해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)데이터 읽기, 삽입, 수정, 삭제를 평균적으로 O(1)의 성능으로 처리할 수 있다.해시 테이블에서의 충돌 (Collision)여러 Key가 동일한 Hash 값으로 매핑될 경우 충돌이 발생한다.해시 테이블의 장단점(1) 장점빠른 데이터 읽기, 삽입, 삭제 성능을 제공한다.(2) 단점공간의 효율성이 떨어질 수 잇다.미리 할당해야 하는 메모리 공간이 많다.해시 함수에 따라 메모리 낭비가 발생할 수 있다.해시 함수의 품질에 따라 성능에 큰 영향을 미치므로 좋은 해시 함수의 구현이 필수적이다.7. 셋 (Set)데이터의 중복을 허용하지 않는 자료구조중복되지 않는 값 저장시 유용함해시 테이블을 이용하기 때문에 해시 셋(Hash Set) 이라고도 불리며 쉽게 구현 가능해시 테이블의 value 값은 사용하지 않고 key 만 사용해서 구현한다.key 가 key 임과 동시에 데이터로 사용됨셋 (Set)의 추상자료형add(data) - 셋에 데이터를 추가하는 기능매개변수로 전달되는 data는 key이자 데이터isContain(data) - 셋에 해당 데이터가 있는지 체크하는 기능해당 데이터가 셋에 있다면 true, 없다면 false를 리턴한다.remove(data) - 셋에 데이터를 제거하는 기능제거할 data를 매개변수로 전달하며 해시 테이블에서 해당 key를 제거clear() - 셋을 비우는 기능isEmpty() - 셋이 비었는지 검사하는 기능printAll() - 테스트를 위해 셋의 모든 데이터를 출력하는 기능

알고리즘 · 자료구조･인프런워밍업클럽･알고리즘･자료구조･CS

1

[1주차] 발자국

강의수강이번 1주차 강의를 수강하면서 자료구조들을 구현해보고 운영체제와 프로세스 쓰레드 등을 배웠다. 학교에서 강의를 들었을 때 제대로 이해하지 못했던 부분들을 다시 한번 더 되새겨 볼 수 있었다. 한번 더 배워보니 처음에 들었을 때보다 조금 더 이해가 되는 것 같았다. 하루 치 들어야 할 강의는 꼭 그 하루에 다 들어서 미션을 할 때에도, 강의를 이해하는 데에도 더 여유가 생기도록 해야겠다고 생각했다.미션미션을 하면서 강의를 들을 때는 이해를 했었는데 막상 미션의 질문들을 보니 바로 떠오르지는 않아서 봤었던 강의를 다시 한번 더 복습하게 되었다. 그래도 다시 한번 더 들으니 그리 어렵지 않게 미션을 해낼 수 있었던 것 같다.

알고리즘 · 자료구조

1

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

프로그래밍 언어만 배우다가 자료구조, 알고리즘, CS 등등 알아야될게 많아서 엄두도 안나고근데 등장은 자주해서 머리가 아팠는데 인프런에서 스터디를 모집하길래 냅다 결제를 갈겼다 처음 3일까지는 열심히했는데 그 뒤로 주말, 약속 등등으로 벌써부터 풀어져서 지금 이시간에 발자국을 남기게 되었다 ㅋㅋㅋ가이드를 읽어보니 공부한 내용을 자세히 올리지말라그래서 목차로 대신하고(노션에는 따로 정리하면서 공부함)회고 위주로 적어보려 한다. 학습기간1주차 2024-09-30(월) ~ 2024-10-04(금)연휴가 많아서 띄엄띄엄 공부했다..; 헬스장에서 트레드밀 위에 아이패드 올려놓고 공부함 (의지 ㄷㄷ)강의 수강학습내용 요약알고리즘섹션1자료구조와 알고리즘 개요시간복잡도자바 스크립트 실행환경 구축섹션2배열연결리스트스택큐덱해시테이블셋6개의 자료구조를 배웠고, 각각의 정의와 추상자료형, 구현, 테스트를 통해 익혔다. 운영체제섹션1운영체제 개요, 역사, 구조컴퓨터 하드웨어와 구조, 부팅과정, 인터럽트 섹션2프로그램과 프로세스멀티 프로그래밍과 멀티프로세싱PCB프로세스 상태컨텍스트 스위칭프로세스 생성과 종료쓰레드섹션3CPU 스케쥴링 개요다중큐스케쥴링 목표FIFO운영체제의 전반적인 구조와 프로그램, 프로세스, 스레드, CPU 등을 집중적으로 개념학습했다.학습내용 회고(칭찬, 아쉬움, 보완, 차주 목표 등)잘한점 : 그렇게 많이 나오던 운영체제의 내용을 쭉 훑어서 뿌듯하다. 평소에 스택, 큐, 연결리스트, 해시테이블은 한번씩 유튜브를 통해 익혀서 내용 이해에 많은 도움이 되었다.아쉬운점 : 평소에 한번 본 내용+ 짧은 강의시간 이라서 너무 만만하게 봤다.보완 : 일단 강의 다 들어보고 시간을 배분하자 .ᐟ

백엔드･CS스터디-발자국

1

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

* 해당 포스팅은 그림으로 쉽게 배우는 자료구조와 알고리즘- 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) (최악의 경우)유리한 케이스: 중복이 없는 고유한 데이터를 관리할 때, 또는 값이 존재하는지 빠르게 확인할 때.

알고리즘 · 자료구조･배열･연결리스트･스택･큐･덱･해시테이블･셋

1

[인프런 워밍업 클럽 CS 2기] 1주차 발자국 - 운영체제

[ Section 1. 운영체제 들어가기 ]1. 운영체제 개요운영체제가 사용되는 곳개인용 컴퓨터 : Windows, Mac OS스마트폰, 태블릿 : 안드로이드, iOS네비게이션, 스마트 워치, 냉장고, 세탁기 : 임베디드 시스템컴퓨터는 운영체제 없이 동작 가능할까?→ 가능하다. 그러나 운영체제가 없는 경우 기본적으로 세팅된 기능만 사용 가능하며 추가적인 기능을 사용할 수 없다.예시) ☎ : 전화기는 기본으로 제공되는 기능만 사용가능 📱 : 스마트폰은 운영체제가 내장되어 다양한 기능들을 추가적으로 사용할 수 있음운영체제가 하는 일프로세스 관리, 메모리 관리, 하드웨어 관리, 파일 시스템 관리 3. 운영체제의 구조커널프로세스, 메모리, 저장장치를 관리하는 운영체제의 핵심 기능사용자와 커널간의 인터페이스시스템 콜→ 시스템 콜은 사용자와 커널 간의 상호작용을 보호하기 위한 인터페이스이며, 사용자와 애플리케이션은 시스템 콜을 통해 커널과 소통한다.GUI/CLI 방식GUI (Graphical User Interface): Windows, Mac OS와 같이 그래픽 기반의 사용자 인터페이스를 제공한다.CLI (Command Line Interface): 텍스트를 사용하여 커널에 접근하며, 주로 Linux/Unix 시스템에서 사용한다.하드웨어와 커널의 인터페이스 하드웨어와 커널의 인터페이스드라이버→ 드라이버는 하드웨어와 커널 간의 상호작용을 위한 인터페이스이다. 4. 컴퓨터 하드웨어와 구조폰 노이만 구조CPU와 메모리를 두고 그 사이를 *버스로 연결한 구조임.버스 : 데이터를 전달하는 통로프로그램 내장 방식을 사용함.프로그램 내장 방식폰 노이만 구조의 핵심 개념으로, 프로그램 명령어와 데이터를 메모리에 함께 저장하는 방식임.CPU(Central Processing Unit) 구성장치(1) 산술논리 연산장치 : CPU에서 실제로 데이터 연산 담당(2) 제어장치 : 모든 장치들의 동작을 지시하고 제어(3) 레지스터 : CPU내에서 계산을 위해 임시로 값을 보관하는 장치 → 변수와 같은 기능메모리 종류RAM (Random Access Memory)랜덤으로 데이터를 읽어도 데이터 저장 위치와 상관없이 읽는 속도가 같다.전력이 끊기면 데이터 휘발됨메인 메모리로 사용됨ROM (Read Only Memory)전력이 끊겨도 데이터를 보관할 수 있으나 데이터를 한번 쓰면 수정이 불가능 함.컴퓨터의 부팅과 관련된 바이오스를 저장하는데 주로 사용됨 5. 컴퓨터의 부팅과정컴퓨터의 전원을 누른 경우 ROM에 저장된 바이오스가 실행됨(1) 바이오스가 주요 하드웨어에 이상이 없는지 확인a. 이상이 있는 경우 오류음을 내며 부팅이 이루어 지지 않음b. 이상이 없는 경우 마스터 부트 레코드에 저장된 부트로더를 메모리로 가져와서 실행함(2) 부트로더 실행a. 운영체제가 여러개인 경우 실행할 운영체제 선택b. a.에서 운영체제를 선택했거나 운영체제가 하나인 경우 운영체제를 메모리로 불러옴(3) 운영체제 실행운영체제 실행 이후 실행되는 모든 응용 프로그램은 메모리에 올라와서 실행되며 운영체제가 관리함 6. 인터럽트폴링방식CPU가 입출력 관리자에게 입출력 명령을 내린 후 입출력 명령 완료 여부를 주기적으로 확인하는 방식주기적으로 CPU가 확인해줘야 하니 CPU 성능이 좋지 않음인터럽트폴링방식의 문제점 해결CPU가 입출력 관리자에게 입출력 명령을 내린 후 다른 작업을 진행한다. 입출력 관리자는 입출력이 완료되면 CPU에게 신호를 주고 CPU는 그 신호를 받아 *인터럽트 서비스 루틴(ISR)을 실행시켜 작업을 완료한다.*인터럽트 서비스 루틴(ISR) : 특정 인터럽트가 들어오면 그 인터럽트를 처리하는 함수비동기적으로 동작하기 때문에 성능에 이점이 있다.인터럽트 방식하드웨어 인터럽트 소프트웨어 인터럽트[ Section 2. 프로세스와 쓰레드 ]1. 프로그램과 프로세스프로그램(Program)이란?저장장치에 저장된 명령문의 집합체, 애플리케이션, 앱이라고도 불림.컴퓨터 관점에서 저장장치만 사용하는 수동적 존재프로세스(Process)란?저장장치에 저장된 프로그램이 메모리에 올라갔을 때 프로그램이 실행되며, 프로세스라고 불림.메모리/CPU 사용, 입/출력 작업을 진행므로 컴퓨터 관점에서 능동적인 존재프로세스의 구조1) Code 영역, 2) Data 영역, 3) Stack 영역, 4) Heap 영역 2. 멀티프로그래밍과 멀티프로세싱유니 프로그래밍(Uniprogramming)하나의 프로그램만 메모리에 적재하여 실행하는 방식한 번에 하나의 프로세스만 실행되는 가장 기본적인 운영 체제 방식멀티 프로그래밍(Multiprogramming)여러 프로그램을 메모리에 동시에 적재하여 실행하는 방식이며, 단일 CPU에서 여러 프로세스를 번갈아가며 실행한다.CPU가 한 프로세스의 작업을 처리하는 동안 다른 프로세스의 작업을 기다리는 형태로 작업을 스위칭하고, 이를 반복하여 여러 프로세스를 병렬적으로 실행하는 방식멀티 프로그래밍은 CPU의 활용도를 높이기 위해 여러 프로세스를 메모리에 적재하고, CPU가 유휴 상태에 있지 않도록 대기 상태에 있는 프로세스를 실행한다.멀티 프로세싱(Multiprocessing)멀티 프로세싱은 물리적으로 여러 개의 CPU를 사용하여 동시에 여러 프로세스를 실행하는 방식여러 개의 CPU가 병렬적으로 동작하여 프로세스를 동시에 처리할 수 있다.프로세스 간의 작업 분담: 각 CPU는 특정 프로세스를 처리하여 작업을 나누어 수행한다.프로세스 간 통신: 프로세스 간의 데이터 공유 및 통신을 통해 협력하여 작업을 수행한다.멀티 프로세싱 방식을 통해 단일 CPU 처리에 비해 더 높은 성능과 처리량을 기대할 수 있다.시분할 처리멀티프로그래밍의 한 형태로, 하나의 CPU가 여러 프로세스를 번갈아가며 실행하는 것 3. PCB (Process Control Block)PCB프로세스 생성시 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB를 만들고 저장함.PCB들은 연결리스트라는 자료구조로 저장되며, 프로세스 종료시 운영체제는 연결리스트에서 해당 프로세스의 PCB를 제거함. 이때 연결리스트 구조는 유지PCB의 구조포인터, 프로세스 상태, 프로세스 ID, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보, CPU 스케줄링 정보 4. 프로세스 상태프로세스는 시분할 시스템을 처리하기 위한 다섯가지 상태를 가지고 있다.1) 생성 (New)PCB를 생성하고 메모리에 프로그램 적재를 요청해둔 상태2) 준비 (Ready)프로세스가 메모리에 적재되었고, CPU 할당을 기다리는 상태준비상태의 프로세스는 CPU 스케줄러에 의해 CPU가 할당된다.대부분의 프로세스는 준비상태이다.3) 실행 (Running)준비상태의 프로세스가 CPU스케줄러에 의해 CPU를 할당받아 실행되는 상태실행상태에 있는 프로세스의 수는 CPU의 개수만큼이다. (CPU가 1개이면 실행상태의 프로세스는 최대 1개)CPU스케줄러는 부여된 시간을 초과하면 할당된 CPU를 강제로 빼앗고 프로세스는 준비상태로 되돌아간다.4) 대기 (Waiting)입출력 작업에서 입출력이 완료될 때 까지 기다리는 상태프로세스 실행상태에서 입출력 작업이 필요한 경우 프로세스를 대기상태로 전환하고 다른 프로세스에게 CPU를 할당한다. 이후 입출력 작업이 완료되면 대기상태인 프로세스에게 CPU 할당 기회를 준다.5) 완료 (Terminated)프로세스가 종료된 상태프로세스가 사용했던 데이터를 메모리에서 제거하고 생성된 PCB도 제거한다. 5. 컨텍스트 스위칭컨텍스트 스위칭 (Context Switching)프로세스 실행 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 새 프로세스의 상태로 전환하는 작업컨텍스트 스위칭 과정에서 PCB에 각 프로세스의 상태가 기록되며, CPU는 해당 정보로 다시 설정됨컨텍스트 스위칭 발생 이유CPU 점유시간 초과시I/O 요청이 있는 경우다른종류의 인터럽트 발생시 6. 프로세스 생성과 종료프로세스 생성 과정.exe 파일 실행시운영체제가 코드영역과 데이터 영역을 메모리에 로드 + 빈 스택과 빈 힙을 만들어 공간 확보프로세스 관리를 위한 PCB를 만들어서 값을 초기화 해준다. 1 ~ 3의 과정은 운영체제가 부팅되고 0번 프로세스 생성시 최초 1번 실행된다.이후 생성되는 프로세스는 0번 프로세스를 복사하여 사용한다. → 새로 생성하는것보다 복사가 빠름fork() 함수 사용하여 프로세스를 복사하고 exce() 함수를 실행하여 복사한 부모 프로세스의 코드 영역과 데이터 영역을 자식 프로세스가 원하는 값으로 덮어씀프로세스 종료자식 프로세스는 exit() 함수를 사용하여 부모 프로세스에게 정상 종료를 알림부모 프로세스는 자식 프로세스의 Exit Status를 읽고 자식 프로세스를 정리한다. (Exit Status=0인 경우 정상종료)좀비 프로세스자식 프로세스 보다 부모 프로세스가 먼저 종료되거나 자식 프로세스가 비정상적으로 종료되어 메모리에 계속 살아있는 상태컴퓨터를 재부팅하면 메모리가 초기화 되어 좀비 프로세스가 사라짐 7. 쓰레드 (Thread)프로세스의 문제점운영체제는 프로세스 단위로 작업을 처리하며, 각 프로세스는 독립됩 메모리 공간(코드, 데이터, 힙, 스택)을 사용한다.하지만 여러 프로세스가 실행될수록 다음과 같은 단점들이 발생한다.컨텍스트 스위칭 오버헤드 : 프로세스 간 전환 시 많은 시간이 소요메모리 공간 분리 : 프로세스 간 메모리를 공유하지 않기 때문에, 데이터를 주고받으려면 복잡한 통신 방식(IPC, Inter-Process Communication)필요, 통신의 비용이 상대적으로 많이 들며 성능 저하 발생.자원의 비효율적 사용 : 동일한 프로그램을 여러 프로세스로 실행 시, 각 프로세스가 중복된 자원을 사용하여 메모리 낭비발생.쓰레드 (Thread)프로세스의 단점을 보완하기 위해 등장하나의 프로세스 내에서 실행되는 단위이며, 1개 이상의 쓰레드가 존재할 수 있음메모리 공유쓰레드는 코드, 데이터, 힙 영역을 공유하며, 스택은 각 쓰레드마다 별도로 가진다.작업 효율프로세스 단위가 아닌 쓰레드 단위로 작업이 이루어지며, 컨텍스트 스위칭 비용이 줄어들고, 쓰레드 간 통신이 빠르고 간단하다.관리 구조쓰레드마다 ID가 부여되고, 쓰레드를 관리하기 위한 TCB(Thread Control Block)가 존재한다.프로세스와 쓰레드의 장단점쓰레드는 효율적인 자원 사용과 빠른 통신을 가능하게 하지만, 안정성 면에서는 프로세스 방식이 더 유리하다.안정성프로세스는 서로 독립적, 하나의 프로세스에 문제가 생겨도 다른 프로세스에는 영향을 주지 않음쓰레드는 하나의 프로세스 내에서 동작, 프로세스에 문제가 생기면 모든 쓰레드에 영향을 미침.성능프로세스는 메모리를 독립적으로 사용, IPC 통신으로 인해 오버헤드가 크고 속도가 느림.쓰레드는 메모리를 공유하고, 스택을 제외한 자원을 함께 사용하므로 오버헤드가 작고 빠름. 그러나 공유된 자원에서 경쟁 상태나 충돌 문제가 발생할 수 있음.[ Section 3. CPU스케줄링 ]1. CPU 스케줄링 개요CPU 스케줄링운영체제가 모든 프로세스에게 CPU를 할당/해제 하는 것CPU Burst 와 I/O BurstCPU Burst (연산)컴퓨터가 연산하는 시간I/O Burst (입출력 작업)컴퓨터가 입출력을 기다리거나 처리하는 시간 2. 다중큐프로세스 상태에서 준비(Ready)상태와 대기(Waiting)상태의 프로세스는 큐(Queue)라는 자료구조로 관리된다.큐(Queue) 자료구조선입선출(FIFO) 방식으로 작동하며, 작업이 들어온 순서대로 처리되는 자료구조먼저 들어온 작업이 먼저 처리되고 나중에 들어온 작업은 나중에 처리됨 3. 스케줄링 목표1) 리소스 사용률2) 오버헤드 최소화3) 공평성4) 처리량5) 대기시간6) 응답시간 4. FIFO (First In First Out) 알고리즘FIFO (First In First Out)먼저 들어온 작업이 먼저 처리됨.CPU 스케줄링의 입장에서 스케줄링 큐에 들어온 순서대로 CPU를 할당받아 처리하는 방식임.FIFO 알고리즘의 단점먼저 들어온 프로세스가 끝나야만 다음 프로세스가 실행될 수 있다.실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 한다.I/O 작업이 있는 경우 I/O 작업이 끝날때 까지 CPU 가 쉬게 되므로 CPU 사용률이 떨어짐.평균 대기 시간프로세스 여러개가 실행될 때, 이 프로세스들 모두가 실행되기까지 대기시간의 평균을 말함.스케줄링의 성능은 평균 대기 시간으로 평가함FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나기 때문에 현대 운영체제에서 잘 쓰이지 않고 일괄처리 시스템에 쓰임.

알고리즘 · 자료구조･인프런워밍업클럽･운영체제･CS

1

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

운영체제폴링방식 성능향상1초마다 플레이어가 스킬을 사용했는지 체크하는 코드, 1초마다 체크하기 때문에 성능에 좋지않다. 이를 해결하기 위한 방식으로 어떤걸 이용해야 하는지?while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 } 해당 코드는 주기적으로 cpu를 동작시키는 폴링 방식으로, 비동기적으로 작동하는 인터럽트 방식을 통해 플레이어가 스킬을 사용했을때 cpu에게 신호를 주는 인터럽트 서비스 루틴(ISR)을 실행시켜 작업을 완료해야 한다.프로그램과 프로세스가 어떻게 다른가요?프로그램은 컴퓨터의 관점에서 저장장치만 사용하는 수동적인 존재이고, 프로세스는 메모리도 사용하고 운영체제의 CPU 스케쥴링 알고리즘에 따라서 CPU도 사용하고, 필요에 따라 입출력도 하기때문에 능동적인 존재이다.멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?둘 다 여러개를 처리하는것은 동일하나, 멀티프로그래밍은 메모리의 관점에서 메모리에 여러개의 프로세스가 올라온 것이고, 멀티프로세싱은 CPU의 관점에서 여러개의 프로세서를 처리하는 것을 말한다.운영체제는 프로세스를 관리하기 위해서 어떤것을 사용하나요?운영체제는 CPU를 통해 프로세스를 관리하기 위해 프로세스마다 PCB(Process Control Block) 에 여러 정보를 저장해 관리한다. PCB는 연결리스트로 구성되어 있으며, 운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거한다.컨텍스트 스위칭이란 뭔가요?운영체제에서 CPU를 통해 프로세스(A)를 실행하는 중에, 다른 프로세스(B)를 실행하기 위해 실행중인 프로세스(A)의 상태를 저장하고 다른프로세스(B)의 상태값(PCB)으로 교체하는 작업을 말한다. 자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤걸 선택하실 건가요? 이유를 함께 적어주세요. 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램은 덱(deque)의 자료구조를 선택한다. 학생은 전학, 전입, 자퇴 등의 이유와 1년이 지나면 교실에 새로운 학생들이 오기 때문에 덱을 이용해 수정이 편리한 프로그램으로 작성한다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.순서대로 주문을 처리하는 프로그램에는 큐(queue)의 자료구조를 선택한다. 큐는 FIFO의 규칙을 가진 자료구조로, 순서대로 처리하기 위해 tail을 추가하고 양방향 연결리스트로 구현하면 된다.

백엔드･CS스터디-미션

1

[인프런 워밍업 클럽 스터디 2기] 백엔드 클린 코드, 테스트 코드 1주차 발자국

해당 글은 박우빈님의 강의를 수강하며 작성한 글입니다. 강의 수강1. 추상과 구체추상과 구체, 이 두 단어는 항상 같이 다니는 한 쌍이다.추상이란?구체적인 정보에서 어떤 이미지를 뽑아내는 것.중요한 정보는 가려내어 남기고 덜 중요한 정보는 생략하여 버린다.추상은 항상 구체적인 실재에서 시작해야 한다.위 내용을 통해 구체적인 내용에서 추상의 단계로 가는 방법이 있고, 그 반대의 방법도 존재한다.우리는 강의를 통해서 구체적인 지뢰찾기 코드를 추상화해가며 객체지향의 개념을 적용해보는 시간을 가졌다. 2. 논리, 사고의 흐름뇌 메모리 적게 쓰기최소한의 인지적 노력으로 최대의 정보를 제공해야 한다.뇌는 범주화라는 작업을 통해 무언가를 떠올린다.이 말은 즉, 누군가 작성한 코드(조상)가 남(후손)이 보아도 쉽게 읽고 이해할 수 있다면, 그것은 뇌 메모리를 적게 쓸 수 있게 한 효과적인 코드가 아닐까 싶다.Early returnEarly return 사용을 통해 else의 사용을 지양하자사고의 depth 줄이기공백 라인공백 라인도 의미를 가진다.읽는 사람으로 하여금 의미를 분절시켜 추가적인 정보전달이 가능하다.부정어 사용부정어구를 쓰지 않아도 되는 상황인지 체크부정의 의미를 담은 다른 단어가 존재하는지 고민하거나 부정어구 메서드 사용해피 케이스와 예외 처리 3. 객체 지향 패러다임객체 설계하기 : 미션으로 대체SOLIDSRP: Single Responsibility PrincipleOCP: Open-Closed PrincipleLSP: Liskov Substitution PrincipleISP: Interface Segregation PrincipleDIP: Dependency Inversion Principle 4. 객체 지향 적용하기상속과 조합상속보단 조합을 이용하자.조합과 인터페이스를 활용하는 것이 유연한 구조다.Value Object훌륭한 추상화 기법 중 하나기본 타입을 객체로 감싸서 의미 부여 및 추상화를 하는 것.동등성 vs 동일성일급 컬렉션Enum의 특성과 활용상수집합변경이 잦은 개념은 Enum보다 DB로 관리하자.다형성 활용하기숨겨져 있는 도메인 개념 도출하기도메인 지식은 만드는 것이 아니라 발견하는 것이다.미션Day 2추상과 구체의 예시 제시추상"노래를 듣는다" 라는 추상적인 문장을 구체화 해보았다구체이어폰에서 발생한 음파가 공기를 통해 외이로 도달한다.외이도를 통해 전달된 음파는 고막에 도달하고, 고막은 음파에 의해 진동한다.고막의 진동은 중이의 세 개의 작은 뼈로 전달된다.세 개의 뼈는 음파의 진동을 증폭시켜 내이의 달팽이관으로 전달한다.달팽이관에 있는 액체가 움직이면서 유모 세포를 흔들고, 이 과정에서 전기 신호로 생성한다.전기 신호가 청각 신경을 통해 뇌로 전달된다.뇌의 청각 피질이 신호를 분석하고 해석하여 소리를 인식한다.Day 41. 코드 리팩토링2. SOLID에 대한 자기만의 언어로 정리깃허브 링크 대체노션 링크 대체회고클린코드란 무엇인가 에 대해 다시 한번 고민하게 되는 주간이었다. 사이드 프로젝트를 진행하면서 주로 나의 코드를 내가 자주 보고 고치기 때문에 남이 어떻게 이해할지에 대해서 깊게 고민해보지 못했던 것 같다. 이번 기회를 통해 프로젝트 코드에서 고칠 부분이 상당히 많이 떠올랐고, 스터디 중간 중간 적용해보려고 노력하려 한다. 빡빡한 스케줄을 회사와 병행하다보니 강의 수강과 미션 수행을 모두 처리하는 것이 상당히 쉽지 않았다. 다행히 이번 주간에는 쉬는 날이 많아서 겨우 맞춰나간 것 같다. 많은 스터디원 분들이 성실히 수행하는 것을 보며 동기부여가 되고 있다.남은 3주도 잘 마무리하여 완주러너가 되고 싶다.

BE･클린코드･워밍업클럽

1

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

운영체제 1. while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 } 위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요? 폴링 방식의 성능 문제를 해결하기 위해서는 인터럽트를 사용할 수 있습니다. 인터럽트란, CPU가 주기적으로 실행이 완료되었는지 상태를 체크하는 대신, 그 시간에 다른 작업을 수행할 수 있도록 하는 메커니즘입니다. 즉, CPU가 계속해서 상태를 확인하지 않아도 특정 조건이 충족되면 원래의 작업을 즉시 처리할 수 있게 하는 알림 같은 개념이다.코드 수정해보기스킬 사용 여부를 계속 체크하는 대신, 다른 작업을 수행하면서도 플레이어가 스킬을 사용했을 때를 감지해서 특정한 반응이 일어날 수 있도록 코드를 수정했습니다.void onSkillActivated() { // 스킬이 활성화 되면 실행되는 코드 activateSkill(); } int main() { // 스킬 사용 이벤트에 인터럽트 핸들러 등록 registerInterruptHandler("SkillActivated", onSkillActivated); while (true) { // 기타 게임 로직 처리 } return 0; } 2. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 코드, 즉 명령어의 집합으로 .exe와 같은 파일 형태로 존재합니다. 실행되지 않으면 CPU, 메모리 등의 시스템 자원을 사용할 수 없습니다. 이제 이러한 프로그램을 더블 클릭 등으로 실행을 시키면 메모리에 적재되어 CPU에서 실제로 실행되고, 바로 그것을 프로세스라고 부릅니다. 프로세스는 실행 중일 때 시스템 자원을 사용합니다. 또한 준비 상태, 실행 상태, 대기 상태 등 다양한 상태를 가집니다.한 마디로 프로그램은 실행 중이 아닌 상태의 코드이고, 프로세스는 실행 중인 상태의 프로그램입니다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 메모리 상에 여러 프로세스가 존재하고, CPU가 이 프로세스들을 번갈아 가며 실행하는 방식입니다. 멀티프로세싱은 CPU가 여러개의 프로세스를 처리하는 방식입니다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요? 운영체제는 PCB(Process Control Block)를 사용하여 프로세스를 관리합니다. PCB에는 각 프로세스에 대한 정보가 저장되어 있습니다. 포인터, 프로세스 상태, 프로세스 ID, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보, CPU 스케줄링 정보 등 프로세스에 효율적으로 접근하고, CPU가 뺏겼다가 프로세스가 다시 실행될 때와 같은 상황에 필요한 정보들이 PCB에 담겨있습니다. 컨텍스트 스위칭이란 뭔가요?운영체제가 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스의 상태를 PCB에 저장하고, 다른 프로세스의 상태값으로 CPU의 세팅을 변경하는 작업을 말합니다. CPU의 점유 시간이 다 된 경우, I/O 요청이 있는 경우, 다른 종류의 인터럽트가 있는 경우에 컨텍스트 스위칭이 발생합니다. 예를 들어 프로세스 A의 CPU 점유 시간이 다 된 경우, 현재 CPU 레지스터 값을 PCB A에 저장하고, 다음에 실행될 프로세스의 PCB를 참조해서 해당 프로세스의 마지막 상태로 CPU의 레지스터 값을 세팅합니다. 자료구조와 알고리즘 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. 학생 정보를 저장하기 위해 해시 테이블을 사용하면 좋을 것 같습니다. 일반적으로 학생들은 고유한 학번(학생 id)을 갖고 있기 때문에 이러한 학번을 key로 사용하면, 특정 학생의 id만 알고있으면 학생의 정보에 빠르게(O(1)) 접근할 수 있어 유용할 것이라고 생각합니다. 또한 한 교실의 학생 인원에 변동(전학 등)이 생길 경우 해시 테이블을 사용한다면 학생 데이터의 삽입, 삭제도 빠르게 할 수 있습니다. 다만, 해시함수에서 충돌이 발생할 수 있기 때문에 이 점에 유의해서 프로그램을 작성해야할 것입니다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.주어진 조건에 가장 적합한 자료구조는 큐라고 생각합니다.큐는 FIFO(First In First Out), 가장 먼저 들어온 것이 가장 먼저 나가는 방식으로 동작합니다. 따라서 큐를 사용하면 주문이 들어온 순서대로 처리할 수 있습니다. 또한 새로운 주문을 큐의 끝에 추가하는 삽입 연산, 가장 먼저 들어온 주문을 큐의 맨 앞에서 제거하는 삭제 연산 등의 간단한 연산만으로 주문 프로그램을 구현할수 있습니다.

워밍업클럽･CS･미션

1

[워밍업 클럽 스터디 2기 - BE 클린코드&테스트] 1주차 발자국

1주차 학습내용보기 좋은 코드 작성법예외가 발생할 가능성 낮추기어떤 값의 검증이 필요한 부분은 주로 외부 세계와의 접점e.g) 사용자 입력, 외부 사용자 요청의도한 예외와 예상하지 못한 예외를 구분하기Null을 대하는 자세항상 NPE를 방지하는 방향으로 경각심을 가지기메서드 설계 시 return null을 자제하기Optional은 꼭 필요한 상황에서 반환 타입에 사용반환받았다면 최대한 빠르게 해소하기 1주차 미션 회고Keep평소에 내가 코드를 작성하며 클린코드를 목표하며 고민했던 부분과 강의내용과 거의 대부분 일치해서 좋은 방향으로 가고 있구나라는 생각이 들었다. 스터디 발자국도 제출기한에 맞춰 늦지않게 제출하였다. Problem아무래도 자격증 시험과 같이 있다보니 강의의 내용을 빠른 배속으로 들을 때가 종종 있는 것 같다. Try시간에 급박해서 들으려고 하지말고, 출퇴근 시간을 활용하며 이 스터디에 임해야겠다.

1

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

학습 내용 이번 주차에는 아래의 내용을 학습했다.운영체제프로세스CPU알고리즘과 자료구조 (Stack, Queue, Hash Table, Linked List 등)회고전공수업을 들으면서 한번씩은 정리하고 시험까지 봤던 내용들이지만 다시 정리가 필요하다고 느꼈고, 워밍업 클럽 스터디를 시작하게 되었다. 이번엔 현업이 바빠 미션과 발자국을 다소 급하게 마무리지었던 것 같은데, 다음부터는 조금 더 자세하고 깊게 정리하고 싶다.

1

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

수강 방식전체적으로 강의 내용을 노션에 정리하며 수강(비공개 처리)강의 화면을 캡쳐하여 정리하고 코드를 따라치지만 단순 클론 코딩이 아닌 이해될 때 까지 넘어가지 않음) 운영체제 비전공자 출신에게 도움이 되는 내용들이었습니다. 프로세스, 쓰레드나 메모리, cpu등등 말로 듣고 글로 된 설명을 읽었을 때는 제대로 이해되지 않았던 부분들이 그림과 함께 학습하니 이해가 빠르게 되었습니다.외에도 프로그램이 어떤 흐름을 통해 실행되는지, 인터넷 창에서 생각없이 눌렀던 탭 추가 기능은 스레드를 추가함으로써 과도한 메모리 할당을 막는다는지 등등이 있었습니다.아직까지는 많은 내용을 보지 못했지만 남아있는 강의들을 수강한다면 실무에 도움이 크게 될거라 생각하여 열심히 수강해야 겠다는 생각을 가졌습니다. 자료구조와 알고리즘 C로 배우고 C#으로 개발하고 있는 나에게 자바스크립트는 익숙하면서도 낯선 언어였습니다. 다만 다뤄보았던 자료구조는 같았기에 이해가 어렵진 않았습니다.다만 연결리스트의 개념 이해와 구현은 조금 어려웠습니다.처음에는 head와 next가 뭔지 이해가 되지 않았으나 그림을 보고 코드를 따라치다보니 조금씩 이해가 되었던 것 같습니다.연결 리스트를 통해 큐, 스택, 덱 등등 자료구조들을 직접 구현해보는 점이 좋았고 현실에서 자료구조와 비슷한 경험을 빗대어 말씀해주시는게 좋았습니다.특히나 자료구조는 실무 개발에서도 적용할 수 있기 때문에 지금까지 배운 자료구조와 앞으로 배울 자료구조 및 알고리즘을 수강하면서 하나씩 적용해보고자 합니다.

발자국

1

첫번째 미션

운영체제 C while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다.이 방식은 폴링방식입니다.1초마다 체크하기 때문에 성능에 좋지 않습니다.이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?매 순간 체크 해야하는 폴링 방식이 아니라 인터럽트 방식을 적용한다.코드로 구현하자면 콜백 방식을 적용한다는 것이 조금 더 올바른 표현 방식으로 생각됩니다.게임 루프 (물리 => 사용자 입력 => 게임 로직 => 렌더링)사용자 입력 부분에서 스킬 사용이 되었다면 해당 순간에 콜백함수를 호출하여 게임로직에 적용되면매 순간 체크하는 것이 아닌 해당 사용자 입력 순간에만 적용하기에 오버헤드가 감소할 것 입니다. 2. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 저장장치에 코드, 데이터영역이 저장되는 것을 의미하며,프로세스는 해당 프로그램이 메모리에 올라가 코드, 데이터, 힙, 스택영역과 PCB를 할당받아 CPU를 통해 실행되는 것을 의미합니다. 3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 메모리내에 여러 프로그램을 올리는 것이고,멀티프로세싱은 운영체제의 시분할을 이용하여 여러 프로세스를 빠르게 전환하여 사용자 입장에서 동시에 처리되는 것처럼 느껴지는 작업을 의미한다. 4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB를 통해 프로세스의 정보를 갱신하고, CPU 스케줄링을 통해 프로세스들의 CPU 점유를 결정한다. 5. 컨텍스트 스위칭이란 뭔가요?프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 현재 실행중인 PCB상태를 수정하고 다른 프로세스의 PCB정보를 가져와서 CPU를 다시 세팅하는 과정을 의미한다.자료구조와 알고리즘1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요?이유를 함께 적어주세요.강의에는 없지만, 동적배열과 해시 테이블을 같이 사용할 것 같습니다.키 값으로 학년, 반을 구분하고 벨류 값에는 동적배열을 넣어 학생의 출석번호를 인덱스로 삼아 참조하는 방식을 사용할 것 같습니다.해시 테이블을 사용한 이유는 학년, 반을 통해 학생이 소속되어 있는 교실을 찾을 수 있으며,교실의 학생 수는 반 마다 다를 수 있기에, 확장성과 참조속도를 고려하여 동적배열이 어울려 보입니다. 2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.기본적으로는 큐를 사용하지만, 큐를 응용하여 다중 큐를 구현할 것 같습니다.고객의 메뉴 선택에 따라 오래 걸리는 음식이 있고, 메뉴가 다양할 수도 있습니다.이러한 조건으로 여러 개의 다중 큐를 만들어 손님들의 평균 대기 시간을 줄이려는 시스템을 구축할 것 같습니다.걸리는 시간에 의한 조건만 추가하면 안되고, 후순위 메뉴가 주문이 들어온 지 얼마나 경과했냐 또한 고려해야 합니다.

1

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

자료구조와 알고리즘시간복잡도: 알고리즘의 실행 시간을 입력 크기의 함수로 표현한 것자바스크립트 실행 환경 구축: Node.js나 브라우저를 사용해 JS 코드를 실행할 수 있는 환경 설정배열: 연속된 메모리 공간에 동일한 타입의 데이터를 저장하는 자료구조연결리스트 개념: 노드들이 데이터와 다음 노드의 참조를 가지고 연결된 선형 자료구조연결리스트 구현: 노드 클래스와 리스트 클래스를 정의하여 삽입, 삭제, 탐색 기능 구현스택 개념: LIFO(Last In First Out) 원칙을 따르는 선형 자료구조스택 구현: 배열이나 연결리스트를 사용해 push, pop 등의 연산 구현큐 개념: FIFO(First In First Out) 원칙을 따르는 선형 자료구조큐 구현: 배열이나 연결리스트를 사용해 enqueue, dequeue 등의 연산 구현덱 개념과 구현: 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, 배열이나 이중 연결리스트로 구현해시테이블 개념: 키를 값에 매핑하는 자료구조로, 빠른 검색을 위해 해시 함수 사용셋 개념과 구현: 중복을 허용하지 않는 컬렉션으로, 해시테이블을 기반으로 구현 가능운영체제운영체제 개요: 하드웨어와 사용자 간의 중개자 역할을 하는 시스템 소프트웨어운영체제의 역사: 일괄 처리 시스템부터 현대의 다중 사용자 시스템까지의 발전 과정운영체제의 구조: 커널, 시스템 콜, 사용자 인터페이스 등으로 구성된 계층적 구조컴퓨터 하드웨어와 구조: CPU, 메모리, 저장장치, 입출력 장치 등의 기본 구성요소컴퓨터의 부팅 과정: BIOS/UEFI 실행부터 운영체제 로딩까지의 단계적 과정인터럽트: 외부 이벤트나 예외 상황을 CPU에 알리는 메커니즘프로그램과 프로세스: 프로그램은 정적인 코드, 프로세스는 실행 중인 프로그램의 인스턴스멀티프로그래밍과 멀티프로세싱: 여러 프로그램의 동시 실행과 여러 프로세서를 사용한 병렬 처리PCB: 프로세스의 상태 정보를 저장하는 데이터 구조프로세스 상태: 생성, 준비, 실행, 대기, 종료 등의 프로세스 생명주기컨텍스트 스위칭: 실행 중인 프로세스를 전환하는 과정프로세스 생성과 종료: fork(), exec() 등의 시스템 콜을 통한 프로세스 관리쓰레드: 프로세스 내에서 실행되는 더 작은 실행 단위CPU 스케줄링 개요: 프로세스들 간에 CPU 시간을 할당하는 방법다중큐: 우선순위나 특성에 따라 프로세스를 여러 큐로 관리하는 스케줄링 기법스케줄링 목표: CPU 사용률 최대화, 처리량 증가, 대기 시간 최소화 등FIFO: 가장 단순한 스케줄링 알고리즘으로, 먼저 도착한 프로세스를 먼저 실행1주차 후기국비지원 교육을 듣고 취업을 하면서 CS 공부를 해 본 적이 없다보니 이름만 들어보고 개념을 모르는 내용들이 많아 학습에 대한 필요성을 느꼈는데, 때마침 인프런에서 워밍업 클럽으로 CS 코스가 열려서 신청하게 되었다.쉽게 풀어서 설명해주시는 감자 코치님의 강의 영상 따라 가다보니 기본적인 내용을 이해하는 데 큰 어려움은 없었던 것 같다.코치님 왈, 잘 모르겠으면 그림을 그려가면서 이해하라고 했는데 앞으로는 그림 그려가면서 이해해보는 것도 좋을 것 같다.미션은 강의에서 들은 내용과 추가적으로 궁금해서 찾아보았던 내용을 토대로 해결할 수 있었다.이번주는 좀 바쁘게 몰아서 들은 감이 있는데, 다음주는 차근차근 추가적인 내용도 찾아가며 강의를 듣고 싶다.

알고리즘 · 자료구조･인프런･인프런워밍업클럽･CS･운영체제･자료구조･알고리즘･감자･1주차

1

CS_전공지식_첫번째미션

운영체제 while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다.이 방식은 폴링방식입니다.1초마다 체크하기 때문에 성능에 좋지 않습니다.이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?폴링 방식의 단점을 보완한 인터럽트 방식을 사용할 수 있습니다. 인터럽트는 다음과 같은 과정으로 진행됩니다. cpu가 입출력 관리자에게 입출력 명령을 내리고 다른 작업을 합니다. 입출력 관리자가 입출력이 완료됐을 때 cpu에게 신호를 주고 cpu는 그 신호를 받아서 인터럽트 서비스 루틴을 실행시켜 작업을 완료합니다. 2. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 하드디스크 등과 같은 저장장치에 저장된 명령문의 집합체입니다. 프로세스는 간단하게 실행 중인 프로그램이라고 할 수 있습니다. 하드디스크에 저장된 프로그램이 메모리에 올라갔을 때 실행 중인 프로그램을 프로세스라고 부릅니다. 3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티 프로그래밍은 메모리에 여러 개의 프로세스가 올라온 것이고, 멀티프로세싱은 cpu가 여러 개의 프로세스를 처리하는 것입니다. 4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?운영체제는 여러 개의 프로세스를 전부 관리하고 공평하게 실행시켜야 합니다. 프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고 pcb라는 것을 만들고 저장합니다. pcb들은 연결리스트라는 자료 구조로 저장됩니다. 운영체제는 프로세스가 종료되면 연결리스트에서 해당 pcb를 제거합니다. 이러한 과정으로 운영체제는 프로세스를 관리하기 위해서 pcb를 사용합니다. 5. 컨텍스트 스위칭이란 뭔가요?컨텍스트 스위칭은 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 기존에 실행중이던 프로세스를 저장하고 실행할 프로세스의 상태값으로 교체하는 것입니다. 자료구조와 알고리즘 1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요?이유를 함께 적어주세요.덱을 선택할 것입니다. 교실의 학생은 보통 가나다 순으로 번호를 부여받습니다. 새로 들어오는 학생이 들어와 있는 학생 보다 뒷 번호를 받을 수도 있고 앞 번호를 받을 수도 있기 때문에 양쪽에서 데이터를 삽입할 수 있는 덱이 가장 적절할 것 같습니다. 2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐를 선택할 것입니다. 큐는 먼저 들어온 데이터를 먼저 처리합니다. 이는 먼저 들어온 주문이 가장 먼저 나가야 하는 주문을 받는 프로그램과 동일한 처리 과정이라 생각하기 때문입니다.

컴퓨터 구조

1

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

수강한 강의https://www.inflearn.com/course/비전공자-운영체제https://www.inflearn.com/course/자료구조-알고리즘-기본학습한 내용운영체제프로그램과 프로세스의 차이멀티프로그래밍과 멀티프로세싱PCB프로세스 상태와 생성~종료 과정쓰레드자료구조시간복잡도 표현여러가지 자료구조와 장, 단점배열, 연결리스트스택, 큐, 덱해시테이블, 셋회고일부 알고 있다고 생각했던 내용이었음에도 쉽게 설명하는 게 어렵게 느껴졌다. 익숙해지고 바로 설명할 수 있을 정도로 기초에 탄탄해지고 싶다.이번주에 강의를 다소 몰아듣게 되었는데 차주에는 최대한 일정에 맞춰서 들어보자!그래도 1주차 목표치와 과제를 모두 끝낸 점은 칭찬해~

알고리즘 · 자료구조

1