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

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

tenenger 1개월 전

자료 구조 및 알고리즘

 

배열

다른 프로그래밍 언어 vs 자바스크립트 특징

다른 프로그래밍 언어의 경우는 배열의 크기를 정하고 연속적인 공간을 차지한다. 반면 자바스크립트 언어의 경우에는 배열의 크기를 정하지 않고 비연속적인 공간을 차지한다.

다른 프로그래밍 언어의 배열은 배열의 크기를 늘릴경우 연속적인 공간을 새로 찾아서 기존의 내용을 복사붙여넣기 하기 때문에 성능이 좋지 않다. 반면 자바스크립트 언어의 경우에는 배열의 크기를 정하지 않기 때문에 비연속적인 공간에 값을 넣어 성능이 상대적으로 좋다.

다른 프로그래밍 언어의 배열은 배열의 크기를 할당해야하기 때문에 불필요한 공간을 차지할 수 있다. 반면 자바스크립트 언어의 배열은 배열의 크기를 정하지 않고 동적으로 크기가 정해지기 때문에 불필요한 공간을 줄일 수 있다.

 

공통 특징

배열의 시작주소 + 인덱스를 이용하여 참조를 하고, 참조의 경우 O(1) 의 성능을 보여준다.

 

🏷 자바스크립트 언어의 경우 비연속적인 공간을 차지하는데, 연결리스트로 노드가 연결되어 있어 인덱스로 접근할 수 있어 다른 프로그래밍언어에서 사용되는 배열과 유사하게 연속적인 공간을 차지하는 것 처럼 보여진다.

 

단방향 연결리스트

특징

연결리스트는 다른 노드를 가르키는 포인터가 있고, 하나의 노드가 다른 하나의 노드를 가르키며 서로 연결되어 있지 않아 단방향 연결리스트라고 불린다.

 

데이터 추가시, 인덱스의 위치에 따라 성능이 달라지는데 맨 앞에 데이터 추가시 O(1)의 성능을 가지는 반면, 맨 뒤에 데이터를 추가시 마지막 노드를 확인하고 추가해야하므로 O(n)의 성능을 가진다.

데이터 삭제와 조회도 마찬가지이다.

 

연관된 자료구조

스택

 

스택(Stack)

특징

First In Last Out (FILO) 방식이며, 가장 첫번째로 들어간 노드가 가장 마지막으로 나오는 순서를 따른다. 예시로 설거지를 한 접시를 탑을 쌓는다면 가장 위의 접시부터 빼는 것을 생각하면 이해가 쉽다.

 

구현

단방향 연결리스트를 이용하여 위에서 부터 값을 넣는 push, 가장 위에서 제거하는 pop, 가장 위에 위치한 값을 확인하는 peek, 스택이 비어있는지 확인하는 isEmpty 메서드를 구현했다.

 

양방향 연결리스트

특징

양방향 연결리스트의 경우 하나의 노드가 다른 하나의 노드를 가리키고 있는데, 서로간에 참고하는 경우를 양방향에서 알 수 있다고 해서 양방향 연결리스트라고 한다.

 

연관된 자료구조

큐, 덱, 셋

 

큐(Queue)

특징

First In First Out (FIFO) 방식이며, 가장 첫번째로 들어간 노드가 가장 첫번째로 나오는 순서를 따른다. 예시로 마트 계산대에서 가장 먼저 줄을 선 사람부터 계산을 진행하는 것을 생각하면 이해가 쉽다.

 

구현

양방향 연결리스트를 이용하여 값을 넣는 enqueue, 값을 제거하는 dequeue, 가장 첫번째로 위치한 값을 확인하는 front, 큐가 비어있는지 확인하는 isEmpty 메서드를 구현했다.

 

데크(Deque)

특징

스택과 큐를 특징이 혼합된 자료구조로, 데이터를 첫번째와 마지막에 데이터를 추가, 삭제, 조회를 할 수 있다.

 

구현

양방향 연결리스트를 이용하여 맨 앞의 값을 넣는 addFirst, 맨 앞의 값을 제거하는 removeFirst, 맨 뒤의 값을 넣는 addLast, 맨 뒤의 값을 제거하는 removeLast, 데크가 비어있는지 확인하는 isEmpty 메서드를 구현했다.

 

해시테이블

특징

해시 함수 + 테이블을 합친 개념으로 프로그래밍 언어마다 용어의 차이가 있다. 자바스크립트의 경우 해시 테이블이라고 한다.

테이블을 배열로 만드는 방식의 경우 테이블의 키(숫자)를 인덱스로 하여 값을 저장했다. 이 방법은 사용되지 않는 인덱스의 경우 낭비되는 공간이기 때문에 메모리 낭비를 초래한다. 그래서 해시 함수를 사용하여 낭비되는 공간을 줄이는 방식이 해시 테이블이라고 한다.

해시테이블의 경우 해시 함수에 따라 성능이 좋고 나쁨이 결정되기 때문에 좋은 해시 함수를 만드는 것이 가장 중요하다.

 

구현

배열을 만들고, 양방향 연결리스트를 배열의 원소로 넣어 하나의 배열에 여러개의 양방향 연결리스트를 가진다.

 

연관된 자료구조

셋

 

셋(Set)

특징

중복된 자료를 허용하지 않는다.

 

구현

해시테이블을 이용하여 값을 넣는 add, 값을 제거하는 remove, 맨 뒤의 값을 넣는 addLast, 값을 초기화하는 clear, 저장된 값들을 출력하는 printAll, 셋이 비어있는지 확인하는 isEmpty 메서드를 구현했다.

 

미션1

  1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.

  • 배열 또는 해시테이블을 선택할 거 같습니다.

  • 만약 학생을 나누는 키 값이 연속적인 경우 배열을 선택해도 메모리 낭비 공간이 없겠지만, 만약 키값이 불연속적인 경우 배열로 저장할 경우 낭비되는 공간이 생길 수 있으므로, 해시 함수를 이용하여 낭비되는 메모리 공간을 줄이는 해시테이블을 사용합니다.

 

  1. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.

  • 큐 자료구조를 선택할 거 같습니다.

  • 큐 자료구조의 특징이 첫번째 들어온 데이터가 가장 첫번째로 나가는 FiFO 방식이기 대문에 들어온 순서대로 처리하기에 적합한 자료구조입니다.

 


자료 구조 및 알고리즘

 

인터럽트

입출력 장치의 데이터를 읽거나 쓰려고 할 때 기존의 폴링 방식의 단점을 해결하려고 나온 방식이다.

기존의 폴링방식은 입출력 장치의 데이터를 지속적으로 확인해야하기 때문에 성능이 좋지 않았고, 인터럽트를 통해 입출력 장치가 CPU에게 신호를 주면 CPU는 그때 처리하는 방식이어서 성능상에 이점이 있다.

 

인터럽트

입출력 장치의 데이터를 읽거나 쓰려고 할 때 기존의 폴링 방식의 단점을 해결하려고 나온 방식이다.

기존의 폴링방식은 입출력 장치의 데이터를 지속적으로 확인해야하기 때문에 성능이 좋지 않았고, 인터럽트를 통해 입출력 장치가 CPU에게 신호를 주면 CPU는 그때 처리하는 방식이어서 성능상에 이점이 있다.

 

프로그램과 프로세스

프로그램은 저장장치에 저장된 명령문의 집합체이다. 프로세스는 프로그램이 메모리에 적재되어 실행중인 상태, 즉 실행중인 프로그램을 뜻한다.

 

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

유니프로그래밍은 메모리에 하나의 프로그램이 올라갔으며, 즉 하나의 프로세스가 있다.

멀티프로그래밍은 메모리에 여러개의 프로그램이 올라갔으며, 즉 여러개의 프로세스가 있다.

멀티프로세싱은 CPU가 여러개의 프로세스를 처리하는 것이다.

 

PCB

운영체제가 CPU가 프로세스를 효과적으로 관리하기 위해 PCB를 사용한다.

PCB에는 프로세스에 대한 정보가 있어 시분할 시스템에서 CPU를 이용하여 여러개의 프로세스를 관리할 때 사용한다.

 

프로세스 상태

시분할 시스템으로 여러 프로세스를 돌아가며 실행하여, 동시에 실행되는 것 처럼 보인다.

  • 생성 : PCB생성 후 메모리에 프로그램 적재 요청

  • 준비 : CPU에 의해 사용을 기다리고 있음, CPU 스케줄러에 의해 할당

  • 실행 : 준비 상태에 있는 프로세스가 CPU를 할당받아 실행되는 상태

  • 대기 : 프로세스가 입출력 요청을 하면 입출력이 완료까지 대기

  • 완료 : 프로세스 종료 및 PCB제거

컨텍스트 스위칭

프로세서를 실행 중에 다른 프로세스를 실행하기 위해 현재 프로세서의 상태 값을 저장하고, 다른 프로세스의 상태 값으로 교체하는 것을 뜻합니다.

PCB의 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경된다.

프로세스 생성과 종료

초기 컴퓨터 부팅 후 부모 프로세스가 생성된다.

이후 모든 다른 프로세스는 부모 프로세스를 복사하여 생성되며, 이는 프로세스를 새로 생성하는 것보다 성능에 이점이 있다.

내부의 코드는 자식 프로세스가 exec() 함수가 실행되면 덮어쓰게된다.

 

쓰레드

하나의 프로세스에 하나 이상의 쓰레드가 존재한다.

프로세스가 많아질 수록 PCB, 코드, 데이터, 스택, 힙 영역을 만들어 줘야하기 때문에 메모리를 많이 차지하는 이슈가 있었다. 그리고 브라우저의 탭들은 프로세스마다 통신을 하기 위해 IPC를 이용해야하는데 IPC의 비용이 많은 이슈가 있었다.

쓰레드는 이러한 문제를 해소하기 위해 Code, data, heap을 공유하며, stack은 쓰레드마다 하나씩 가지고, IPC 비용을 줄일 수 있었다.

쓰레드를 이용하면 IPC 비용을 줄일 수 있고 메모리 공간을 절약할 수 있다. 그러나 하나의 프로세스에 문제가 생기면 프로세스에 있는 쓰레드가 모두 문제가 생기는 단점이 있다.

 

CPU 스케줄링

프로세스를 실행하기 위해 CPU 스케줄링은 고려해야할 사항이 2가지 있다.

  1. 어떤 프로세스에게 CPU를 할당할 것인가.

  2. 어떤 프로세스에게 얼만큼의 CPU 할당 시간을 줄것인가.

 

다중큐

준비 상태에 있는 프로세스는 실행 상태로 변환된다.

준비 상태에 있는 프로세스의 PCB는 준비 상태의 다중 큐에 존재하며 CPU 스케줄러에 의해 실행이 결정된다.

대기 상태에 있는 I/O 작업의 프로세스의 PCB가 대기 상태의 다중큐에 존재하며, CPU스케줄러에 의해 실행이 결정된다.

스케줄링 목표

  • 리소스 사용률

  • 오버헤드 최소화

  • 공평성

  • 처리량

  • 대기시간

  • 응답시간

FIFO

스케줄링 큐에 들어온 순서대로 할당하며, 먼저 들어온 프로세스가 종료되어야 다음 프로세스가 실행된다.

만약 Burst Time이 오래 걸리는 프로세스의 위치에 따라 평균 대기시간이 크게 차이가 난다.

현대에서는 사용되지 않으나, 일괄처리시스템에서 주로 사용된다.

 

미션2

  1.  

while(true){
      wait(1); // 1초 멈춤
      bool isActivated = checkSkillActivated(); // 체크
    }

위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?

  • 인터럽트

 

  1. 프로그램과 프로세스가 어떻게 다른가요?

     

    • 프로그램은 저장장치에 저장된 명령문의 집합체입니다.

    • 프로세스는 메모리 상에 적재되어 실행중인 프로그램입니다.

     

  2. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?

     

    • 멀티프로그래밍은 메모리 관점에서 메모리에 여러개의 프로세스가 존재하는 것을 뜻합니다.

    • 멀티프로세싱은 CPU 관점에서 여러개의 프로세스를 처리하는 것을 뜻합니다.

     

  3. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?

  • 운영체제는 PCB를 사용하여 프로세서를 관리합니다.

  • 예를 들어 시분할 시스템으로 여러개의 프로세스를 번갈아가며 프로세스를 실행해야할 때, CPU에서 특정 프로세스 실행 후 레지스터를 해당 프로세서의 PCB에 저장하고 다른 프로세스의 PCB의 레지스터 정보를 불러와서 실행하는 것을 반복하여 마치 여러개의 프로세스가 동시에 실행되는 것처럼 관리할 수 있습니다.

 

  1. 컨텍스트 스위칭이란 뭔가요?

  • 프로세서를 실행 중에 다른 프로세스를 실행하기 위해 현재 프로세서의 상태 값을 저장하고, 다른 프로세스의 상태 값으로 교체하는 것을 뜻합니다. PCB의 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경됩니다.

 

댓글을 작성해보세요.

채널톡 아이콘