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

강의 요약자료구조어떤 알고리즘의 성능의 지표로 빅오표기법($O(n)$)을 사용한다.배열(array)동일한 자료형 요소들의 모임메모리의 연속된 공간에 위치한다데이터의 참조의 시간복잡도 $O(1)$데이터 추가 및 삭제 시간복잡도 $O(n)$연결리스트(linked list)데이터와 다음 노드의 주소를 저장하는 포인터를 가진 노드들이 일자로 연결된 자료구조 각 노드들이 랜덤한 공간에 위치해도 된다.데이터의 참조의 시간복잡도 $O(n)$데이터 추가 및 삭제 시간복잡도 $O(1)$스택(stack)후입선출(LIFO, Last In First Out)큐(queue)선입선출(FIFO, First In First Out)덱(deque)양방향으로 데이터의 접근 및 처리가 가능한 자료구조해시테이블(hashtable)키(key)와 값(value)을 매핑시켜 저장하는 자료구조키를 해시함수를 통해서 변환하여, 변환된 값으로 값을 참조한다.해싱(hashing) : 임의의 크기의 값을 해시 함수를 통해 고정된 크기의 값으로 변환하는 작업해시 충돌(collision) : 다른 키로부터 동일한 해시 함수의 결과값이 나오는 경우chaining 기법 : 해시테이블의 공간을 연결리스트 자료구조를 사용하여 존재하는 데이터 뒤에 연결시킨다.open addressing : 해시 함수의 반환값의 위치에 이미 데이터가 있는 경우 다른 해시 코드를 사용하는 것데이터의 CRUD 작업에 대해 $O(1)$의 시간복잡도를 갖는다. (해시충돌이 없는 경우)메모리를 많이 차지하고, 해시 충돌 시 다른 자료구조를 사용하거나 좋은 해시함수를 구현해야 함셋(set)데이터의 중복을 허용하지 않는 자료구조순서도 고려되지 않는다.학습 내용 정리[배열, linked list](https://github.com/yeeuniii/TIL/blob/main/DataStructure/%EB%B0%B0%EC%97%B4%EA%B3%BC-%EB%A7%81%ED%81%AC%EB%93%9C%EB%A6%AC%EC%8A%A4%ED%8A%B8.md)[stack, queue, deque](https://github.com/yeeuniii/TIL/blob/main/DataStructure/%EC%8A%A4%ED%83%9D-%ED%81%90-%EB%8D%B1.md)[hash table](https://github.com/yeeuniii/TIL/blob/main/DataStructure/%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94.md)[set](https://github.com/yeeuniii/TIL/blob/main/DataStructure/Set.md) 운영체제프로세스와 스레드프로세스는 메모리에 프로그램이 적재되어 운영체제의 관리하에서 실행되는 프로그램이다.프로세스가 생성되면 PCB가 생성되고, 준비 상태(Ready)가 되어 운영체제로부터 CPU를 할당받기를 기다린다.CPU를 할당받으면 실행 상태(Running)가 된다.이때 CPU 점유 시간을 초과하면 운영체제로부터 CPU 제어권을 빼앗고 다시 대기 상태(Ready)가 되고,입출력 작업이 요청되면 대기 상태(Waiting)가 되어 CPU 스케줄링의 대상에서 제외된다.입출력 작업 완료 시, 다시 대기 상태(Ready)가 된다.모든 작업이 완료되면 프로세스의 자원(PCB, 메모리 등)이 회수된다. 프로세스는 고유한 메모리와 PCB를 갖기 때문에 프로세스의 수에 비례하게 메모리도 증가한다.따라서 프로세스 내에서 스택을 제외한 메모리와 PCB를 공유하는 스레드를 사용하여 멀티태스킹을 구현한다.스레드는 가볍지만, 메모리를 공유하기 때문에 동기화 문제가 발생할 수 있다. CPU 스케줄링운영체제가 여러 프로세스에 합리적으로 CPU를 할당 / 해제하는 행위CPU 스케줄링의 성능은 평균 대기 시간에 따라 결정된다.FIFO들어온 순서대로 작업을 처리한다.하나의 프로세스의 작업이 완료되어야 다음 프로세스를 실행할 수 있다.SJF프로세스의 작업 시간을 정확히 예측할 수 없다.Burst Time이 큰 프로세스는 무한 대기가 발생할 수 있다.RR(Round Robin)time slice를 기반으로 모든 프로세스에 공평하게 CPU를 할당한다.time slice가 너무 작을 경우 잦은 컨텍스트 스위칭에 의한 오버헤드가 발생할 수 있다.MLFQ(Multi Level Feedback Queue)프로세스의 우선순위를 줘서(프로세스마다 time slice를 다르게 줌) CPU 처리율과 I/O 처리율의 균형을 제공한다. [1주차 학습 내용 정리](https://github.com/yeeuniii/TIL/blob/main/OS/%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%89%BD%EA%B2%8C-%EB%B0%B0%EC%9A%B0%EB%8A%94-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C.md) 회고강의에서 이해가 되지 않거나 부족한 부분들을 더 찾아보고 채워나가면서 생각보다 학습 시간이 오래 걸렸다. 이렇게 학습함으로써 확실히 이해하고 머릿속에 남는 것 같아 후회되지는 않지만, 그럼으로써 매일매일 계획된 스케줄대로 학습하기가 어려워진 것 같다.자료구조의 경우, 이전 알고리즘 스터디에서 학습했던 것과 비슷한 부분이 많아 리마인드하는 느낌으로 반복 학습해줬다. 그래도 이전과 다르게 연결리스트로 자료구조를 구현하면서 또 다른 방식을 알아갈 수 있어 좋았던 것 같다.운영체제는 진짜 42서울에서 배웠던 것은 헛이었다... 운영체제의 역사, 컴퓨터 구조와 같은 완전 기본부터 학습을 시작하니 다음께 다다 이해되는 느낌.. 이때까지 OS는 주먹식 암기로 학습했었는데 이해를 기반으로 학습되니 운영체제의 기반이 잡힌 기분이다! 그러면서 이때까지 조금씩 주워듣고 겉핥기로만 알고 있던 부분을 플러스알파로 학습하면서 지식을 탄탄히 채워나갈 수 있었다!! 스터디 고민했었는데 운영체제의 개념을 정리할 수 있는 시간이 되었다는 점에서 스터디 신청이 하나도 후회되지 않는다!다만 이번주는 CS 학습에 좀 끌려다니듯이 살았는데, 다음주부터는 일정 학습시간을 정해두고 그날 학습할 것은 그날 끝내도록하자! 미션과 발자국을 이렇게 시간 임박해서 작성하는 불상사를 만들지 않도록... 다음주도 화이팅!

[인프런 워밍업 클럽 CS 3기] 1주차 자료구조 미션

Q1) 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.학생 정보의 조회와 데이터 수정은 빈번히 발생할 수 있다.학생의 전학이 빈번하지 않다면, 데이터의 삽입 및 추가가 자주 발생하지 않을 것이다.교실 내의 학생 수가 고정된다는 가정하에 데이터의 조회와 수정의 성능이 좋은 배열을 사용하는 것이 좋을 것 같다.단, 전학이 빈번하게 발생한다면 배열이 아닌 연결리스트를 사용하는 것이 좋다.또한 학생의 출석번호를 key로 하는 해시테이블 사용을 고려해봐도 괜찮을 것 같다. Q2) 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.들어온 순서대로 작업이 처리되는 구조를 가진 Queue를 선택할 것이다. Q3) 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.import sys import os sys.path.append(os.path.abspath(os.path.join(os.path.dirname(__file__), "..", "linkedlist"))) from linked_list import LinkedList class Stack: def __init__(self): self.stack = LinkedList() def push(self, data): self.stack.insert_last(data) def pop(self): try: return self.stack.delete_last() except AttributeError: return None def peek(self): return self.stack.get_node_at(last) def is_empty(self): return self.stack.count == 0 Q4) 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력 ⁉ charCodeAt() 메서드란?String 값의 charCodeAt() 메서드는 주어진 인덱스의 UTF-16 코드 단위를 표현하는 0과 65535 사이의 정수를 반환합니다.https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt즉, 매개변수 인덱스(default=0)의 문자를 아스키코드로 변환하여 반환하는 메서드이다.console.log("a".charCodeAt()); // 97 console.log("A".charCodeAt()); // 65 console.log("박예은".charCodeAt(0)); // 48149 console.log("박예은".charCodeAt(1)); // 50696 console.log("박예은".charCodeAt(2)); // 51008 charCodeAt 메서드를 사용하여 hash 함수를 구현하면 아래와 같다.function hashFunction(name, size) { let hashValue = 0; for (let index = 0; index 해시 충돌을 줄이기 위해서 곱셈이나 시프트 연산을 추가하는 방식도 고려할 수 있다. python에서는 ord() 함수를 통해 문자를 아스키코드로 변환할 수 있다. def hash(self, name): hash_value = 0 for char in name: hash_value += ord(char) return hash_value % len(self.array) 이전의 main문의 key - value를 바꿔서 확인해보았다.from hash_table import HashTable if __name__ == "__main__": map = HashTable() map.set("정현우", 13); map.set("푸이그", 66); map.set("카디네스", 4); map.set("이주형", 2); map.set("송성문", 24); map.set("최주환", 53); map.set("김동엽", 38); map.set("전태현", 97); map.set("김건희", 12); map.set("김태진", 1); print("250308 키움 히어로즈 선발선수 해시테이블") for index in range(10): values = map.array[index] node = values.head print(index, end=" : ") while node: print(str(node.data.key) + "의 등번호 : " + str(node.data.value), end=" ➡ ") node = node.next print("None") print() print("이주형 등번호: ", map.get("이주형")) print("김혜성 등번호: ", map.get("김혜성")) print("정현우 등번호: ", map.get("정현우")) print() print("선발투수(정현우) 제거") map.remove("정현우") print("정현우 등번호: ", map.get("정현우")) 250308 키움 히어로즈 선발선수 해시테이블 0 : 전태현의 등번호 : 97 ➡ None 1 : None 2 : None 3 : 정현우의 등번호 : 13 ➡ None 4 : 김건희의 등번호 : 12 ➡ 김동엽의 등번호 : 38 ➡ 송성문의 등번호 : 24 ➡ 카디네스의 등번호 : 4 ➡ None 5 : None 6 : 최주환의 등번호 : 53 ➡ None 7 : 이주형의 등번호 : 2 ➡ None 8 : 김태진의 등번호 : 1 ➡ 푸이그의 등번호 : 66 ➡ None 9 : None 이주형 등번호: 2 김혜성 등번호: None 정현우 등번호: 13 선발투수(정현우) 제거 정현우 등번호: None

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

Q1) 아래 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }플레이어가 스킬을 사용한 경우에 이벤트를 발생시키거나 콜백 함수가 실행되도록 구현하여 무한 반복문을 돌면서 불필요한 자원 낭비를 막을 수 있다. Java Script의 경우 eventListener를 사용하여 이벤트를 다룰 수 있고, C언어는 select나 kqueue와 같이 멀티플렉싱을 지원하는 시스템 콜 함수를 사용하여 작업이 완료된 경우 후속 작업을 처리하도록 구현할 수 있다. 폴링 방식(Polling)I/O 작업이 완료되었는지 CPU가 주기적으로 확인하는 것→ CPU의 낭비가 심하다.⇒ 인터럽트 방식을 사용인터럽트(Interrupt)I/O 관리자에게 I/O 작업을 맡기고, CPU는 다른 작업을 처리.I/O 작업 완료 시, 인터럽트 발생 → CPU가 완료된 I/O 작업을 이어서 처리⇒ CPU의 낭비 없이 CPU의 처리량을 높일 수 있다. Q2) 프로그램과 프로세스가 어떻게 다른가요?프로그램저장장치에 저장된 코드의 집합으로, 정적인 상태이다.수동적프로세스실행 중인 프로그램으로, 프로그램이 메모리에 적재되어 운영체제의 관리하에 실행되는 동적 개체이다.능동적 Q3) 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍하나의 메모리에 여러 개의 프로세스를 적재하여 실행시키는 것이다.시분할(time-sharing) 시스템을 통해 여러 개의 프로세스가 동시에 실행되는 것처럼 보이게 할 수 있다. 실제로는 한 번에 하나의 프로세스만 실행된다.멀티프로세싱여러 개의 프로세서(CPU)가 여러 개의 프로세스를 실행시키는 것이다.실제로 여러 개의 프로세스가 동시에 실행될 수 있다. (병렬처리)동시에 작업되는 프로세스의 최대 수 = CPU 개수 Q4) 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요? 프로세스가 생성될 때 운영체제는 PCB(Process Control Block)를 생성한다. PCB에는 Process ID, 프로세스 상태, 포인터, PC(Process Counter), 레지스터 정보 등이 포함되어 있다. 이 정보를 통해(특히 PC, 레지스터 정보) 시분할 시스템에서 CPU 할당 시 이전 작업 상태를 이어받아 실행할 수 있다. Q5) 컨텍스트 스위칭이란 뭔가요?한 프로세스가 I/O 작업 요청이나 CPU 점유시간 초과 등으로 인해 CPU를 반납해야 할 경우, 인터럽트가 발생하여 운영체제가 해당 프로세스로부터 CPU 제어권을 회수한다.이때, 현재 실행 중인 프로세스의 레지스터 값 등을 PCB에 저장한다.이후, 다음에 실행할 프로세스의 PCB에 저장된 레지스터 값을 CPU에 로드하고,PC에 저장된 다음으로 실행할 명령어의 주소를 보고 프로세스의 작업을 이어서 진행한다.