인프런 워밍업 클럽 스터디 3기 - CS 전공지식 <셋째 주 발자국>
[Day 11~13]
Algorithm
정렬 알고리즘(Sorting Algorithm)
개요
대표적인 정렬 알고리즘
버블 정렬(Bubble Sort) (Day 09 참고)
선택 정렬(Selection Sort) (Day 09 참고)
삽입 정렬(Insertion Sort)
개요 및 특징
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해, 자신의 위치를 찾아 삽입하는 알고리즘(참고).
구현이 쉬운 편에 속하나 성능은
O(n^2)로 매우 낮음.
구현하기
첫 번째 구현: 강의 보며 구현 (Done)
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 (Done)
세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 (Done)
네 번째 구현: 아무것도 안 보고 구현 (Done)
마지막 구현: 익숙한 파이썬으로 구현(+리팩토링(비파괴적 연산, 예외처리)) (Done)
병합 정렬(Merge Sort)
개요 및 특징
Array를 정렬의 최소 단위(=1개)로 쪼개 정렬한 결과를 병합하여 정렬하는 알고리즘.
Devide and Conquer 기법과 재귀 함수를 이용해 정렬함(참고).
참고: 여기서 설명하는 건
mergeSort()가 아니라merge()다. 저걸 누가 헷갈리냐고? NADA재귀적으로 구현해야 하므로 이해와 구현이 어려우나, 성능(
O(nlogn))이 매우 높음.
구현하기
첫 번째 구현: 강의 보며 구현 (Done)
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 (Done)
세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현
네 번째 구현: 아무것도 안 보고 구현
마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링)
퀵 정렬(Quick Sort)
개요 및 특징
피벗(Pivot)을 기준으로 작은 값과 큰 값을 분할하며 정렬하는 알고리즘.
Devide and Conquer 기법과 재귀 함수를 이용해 정렬함(참고).
pivot에 따라
Θ(nlogn),O(n^2)로, 안정적으로O(nlogn)의 성능을 뽑아내는 병합 정렬이 더 좋음.
구현하기
첫 번째 구현: 강의 보며 구현 (Done)
두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현
세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현
네 번째 구현: 아무것도 안 보고 구현
마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링)
Operating System
가상 메모리(Virtual Memory)
개요
실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술(혼공컴운 402p.)
가상 메모리 시스템에서 MMU는 동적 주소 변환(Dynamic Address Translation; DAT)을 통해 RAM의 물리 주소와 스왑 영역을 하나의 가상 주소로 보고 관리함(참고).
OS가 실행할 프로세스 외 프로세스를 스와핑(Swapping)하는 방식으로 구현되어 있음.
주소 공간 분할 방식
세그멘테이션(Segmentation)
개요 및 특징
프로세스를 세그멘트(Segment)로 잘라서 메모리에 배치하는 방법.
MMU는 Segment Table을 통해 DAT하여 각 프로세스의 논리 주소를 물리 주소로 변환함(참고: 1, 2
).
Segmentation Table이 아님!
메모리의 가변적 분할+프로세스 내 각 영역의 메모리 접근 보호 용이성 vs. 외부 단편화
DAT 과정 (참고: 1, 2, 3)
프로세스가 코드를 실행해 필요한 명령어와 데이터의 가상 주소를 CPU에 전달함.
CPU가 MMU에게 특정 논리 주소의 물리 주소 정보를 요청함.
MMU가 Segment Table의 Base Address와 Bound Address를 통해 해당 가상 주소와 연결된 물리 주소를 찾음.
MMU가 가진 STBR을 통해 S.T.의 물리 메모리상 시작 위치를 찾음.
S.T.상 해당 프로세스의 가상 주소가 몇 번째 세그먼트에 위치해 있는지 찾음.
세그먼트 테이블의 해당 인덱스로부터 찾은 Base Address와 Bound Address 값을 참고해 진행.
가상 주소 값 < Bound Address 값이라면Base Address 값+가상 주소 값으로 물리 주소 값을 알아냄.가상 주소 값 > Bound Address 값이라면 프로세스를 종료시킴.
페이징(Paging) (참고: 1, 2, 3, 4)
개요 및 특징
프로세스의 논리 주소 공간을 페이지(Page) 단위로, 물리 주소 공간을 프레임(Frame)으로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법(혼공컴운 403p.)
페이지 테이블의 크기가 너무 커져서 메모리를 낭비하지 않도록 주의하는 것이 관건.
메모리의 효율적 관리 vs. 내부 단편화
DAT 과정 (참고: 1, 2, 3)
프로세스 코드 실행 ... CPU의 특정 논리 주소의 물리 주소 정보 요청까지는 동일함.
MMU가 Page Table을 통해 해당 가상 주소와 연결된 물리 주소를 찾음.
해당 가상 주소의 Page Number 및 Offset을 통해 고유 Page Table에 접근함.
Page Number = 가상 주소 / 페이지 크기,Offset = 가상 주소 % 페이지 크기
PTBR을 통해 P.T.의 물리 메모리상 시작 위치를 찾음.
S.T.상 페이지 번호로 프레임 번호를 찾고, 해당 프레임의 시작 주소에 Offset을 더해 변환함.
페이지드 세그멘테이션(Paged Segmentation)
개요 및 특징
DAT 과정 (참고: 1, 2, 3)
프로세스 코드 실행 ... CPU의 특정 논리 주소의 물리 주소 정보 요청까지는 동일함.
S.T.상 해당 프로세스의 가상 주소가 몇 번째 세그먼트에 위치해 있는지 찾음.
영상에서 "0x12300 번지이니 1번 세그먼트구만!"이라는 설명은 예시일 뿐, 번지 수와 세그먼트 번호 간의 관계는 없음(참고).
해당 세그먼트의 접근 권한 위반 여부 확인
위반이라면 해당 요청을 한 프로세스를 Shutdown시킴.
페이지 넘버를 통해 프레임 넘버를 가져 온 후, 해당 프레임으로 접근함.
Invalid라면 Swap 영역에서 가져옴.
해당 프레임의 시작 주소로부터 offset을 더해 원하는 데이터에 접근함(참고: 1, 2).
[Day 14]
Algorithm
메모이제이션(Memoization) (참고: 1, 2, 3)
정의 및 특징
함수 호출의 결과를 캐싱하고 동일한 입력이 다시 발생할 때 캐싱된 결과를 반환하는 하향식 접근(참고).
공간 복잡도-시간 효율성 간 Trade-off 관계에 있음.
계산 결과를 저장하기 위한 추가 메모리가 필요하지만, 일반적으로 중복 계산 제거로 얻는 시간 효율성(Time Effeciency)이 훨씬 높으므로 자주 활용됨.
메모이제이션 예제: 피보나치 수열(참고).
메모이제이션 없이 구현
메모이제이션 활용해 구현
Operating System
입출력 장치(I/O Device)
개요
새로운 데이터를 받아들여서 중앙 처리기로 보내고 다시 처리 결과를 받아 알아볼 수 있는 형태로 바꾸어 주는 장치(참고).
CPU와 메모리 버스에 직접 연결되지 않고, 간접적으로 연결되면 전부 I/O Device!(참고)
유저가 시스템과 소통할 수 있게 하는 장치로, 다른 장치에 비해 처리 속도(=전송률)가 매우 느림.
각 장치는 각자의 Device Controller를 통해 데이터를 보내고, I/O Bus를 통해 CPU를 거쳐 RAM에 도달함.
DMA(Direct Memory Access)를 추가해 CPU 없이 I/O Controller가 Event 등 데이터를 RAM에 직접 전달하는 입출력 방식, 즉 Memory Mapped I/O로 확장됨(참고).
각 Device의 공통 내부 구조 (※ I/O Device는 종류별, 브랜드별, 제품별로 내부 구조가 천차만별임)
Buffer
입출력 장치와 응용 프로그램 사이의 데이터를 임시로 저장하는 메모리 공간.
일반적으로 이중 버퍼링, 즉 입력 버퍼와 출력 버퍼를 사용하는 방식이 일반적임.
Registers
CPU가 장치 상태를 확인하거나 명령을 보낼 때 사용하는 메모리 공간.
데이터 레지스터, 상태 레지스터, 제어 레지스터로 이루어져 있음(참고).
데이터 전송 단위에 따른 분류 (※ 한 장치에서도 기능별로 달리 작동하는 기기도 있음) (참고: 1, 2, 3)
캐릭터 디바이스(Character Device)
정의 및 특징
Fixed Size Block로 정보를 기록하는 장치로, Event의 순서가 상관없는 장치에 사용함.
B.D.에 비해 데이터 전송 단위가 작음
종류
마우스(Mouse)
정의 및 특징
2차원 평면에서의 움직임을 컴퓨터에 전송하는 포인팅 디바이스의 일종.
일반적으로 2차원 평면상에서 위치 정보(x, y)와 버튼 클릭 정보, 스크롤 동작 등을 전달함.
현대 GUI 기반 OS에서 가장 대중적인 입력장치로 쓰이고 있음.
Event 처리 및 전달 과정 (※ 커서 이동 기준)
Ball Mouse
사용자로부터 Event 발생
Optical Mouse
키보드(Keyboard)
블록 디바이스(Block Device)
개요 및 특징
C.D.에 비해 데이터 전송 단위가 큼
종류
HDD(Hard Disk Drive)
정의 및 특징
비휘발성, 순차접근이 가능한 컴퓨터의 보조 기억 장치(참고).
여러 개의 플래터(Platter)가 회전하며 데이터를 저장하고 읽는 자기식 저장장치임.
Flash Memory
CPU와 I/O Device 간 통신 과정
MMID (※ 강의에 소개된 방식)
PMID
[Day 15]
Algorithm
타뷸레이션(Tabulation) (참고: 1, 2, 3)
정의 및 특징
문제를 하위문제로 나눠 계산한 결과를 테이블에 저장한 후, 해당 테이블을 연산에 활용하는 상향식 접근(참고).
메모이제이션은 계산 및 저장, 호출을 그때그때 하고, 타뷸레이션은 계산 및 저장을 먼저 해두고 나중에 한꺼번에 호출한다는 게 가장 큰 차이!
재귀 호출을 하지 않으므로 공간 복잡도도 낮고, Call Stack 생성/제거 Overhead가 없어 T.E도 높음.
반복문의 Overhead는 Loop Unrolling 등의 추가 최적화 여지가 있어 시간 효율성 측면에서는 반복문이 효율적임!
단, 일부 상황(예: TSP)에서는 메모이제이션의 시간 효율성이 더 높을 수 있음.
재귀적 풀이 과정이 더 가독성이 좋을 때, 계산 가능한 경우의 수에 비해 실제 연산에 쓰이는 연산값은 매우 적을 때 등
구현하기
타뷸레이션 예제: 피보나치 수열
Operating System
File System
개요 및 특징
컴퓨터에서 파일이나 자료를 쉽게 발견 및 접근할 수 있도록 보관 또는 조직하는 체제(참고).
파일 관리자가 Block 단위로 저장된 Block Device에 Byte 단위로 접근할 수 있도록 변환함.
파일 시스템의 기능
파일 및 폴더 생성, 수정, 삭제
파일 권한 관리
무결성 보장
백업 및 복구
암호화(Encryption)
File Descriptor
개요 및 특징
Process가 특정 파일에 접근할 때 사용하는 추상적인 값(참고).
[Week Review]
일주일 동안 공부하면서 배우고 느낀 점
독학으로 CS 공부를 하는 나름의 습관에 감이 잡힌 것 같다.
마지막 주 시작을 지난주에 미처 다 이해하지 못한 메모리 분할 방식에 대해 공부하면서 시작했다. 처음엔 정말 이해가 가지 않았지만, 강의를 계속 반복 학습하고, 관련 자료를 찾아보고, 이해가 안 되면 ChatGPT와 충분한 질답을 주고받으면서 공부했다.
위 일련의 과정에서 파편화된 지식을 계층적으로 재구성해 정리하는 방법, Hallucination이라는 태생적 한계를 지닌 LLM을 공부에 활용할 때 어느 정도로 참고해야 하는지, 신용할 만한 정보는 어디에 많이 있는지 등에 관한 감이 잡혔다.
어려웠던 점
강약 조절이 너무 어렵다...
감자님 강의를 보면 해당 주제에 대한 감은 오지만 지식이 체계적으로 쌓이는 느낌은 들지 않는다. 이건 감자님 강의가 입문자들을 위한 쉬운 설명에 주안점을 두고 있어서 그런 거지 단점이 아니다. 오히려 나 같은 비전공자들로 하여금 '뭘 공부해야 하지?'에 대한 가이드를 준다는 점에서 최고다.
근데 내 성격과 몸이 문제다. 지식을 대충 말고 제대로 정리하다 보니 끝이 없다. 이러다간 이번 주는 발자국을 제때 완성 못하고 스터디도 준비 못할 것 같다.
어찌저찌 마무리했다... 휴... 원래 내 방식은 노트 정리를 탑다운으로 틀만 잡고 그 후부터는 바텀업으로 디테일을 계속 파고드는 스타일이었는데, 탑다운으로 강의 내용을 어느 정도(한 60% 정도?) 머릿속에 집어넣기 전까진 정리라는 행위를 하지 않기로 했다. 그 후에 머릿속에 있는 내용을 최대한 있는 대로 정리한 후에 바텀업으로 디테일을 파고들었다. 시간상 정리하지 못한 부분도 있긴 하나 머릿속엔 있기 때문에 반쯤 성공이라고 자축해 본다.
향후 목표
나만의 CS 완전 정복 로드맵 마스터하기
이번 워밍업 클럽은 내 첫 CS 공부였다. 이전까지는 주먹구구식으로 그때그때 필요한 정보만 공부하다 보니 지식이 계속 휘발되는 느낌이었다. 그런데 이번 CS 공부를 하면서 오직 CS 하나만을 집중적으로 공부했다 보니 왜 CS 공부를 해야 하는지 그 이유가 분명해졌다.
나는 언젠가 창업을 하고자 한다. 창업해서 서비스를 운영하려면 모르긴 몰라도 아득히 높은 수준의 갖은 능력이 필요하리라 여겨진다. 그러나 요즘은 K-MOOC나 KOCW, edX 등을 통해 전공 강의조차도 무료로 들을 수 있는 시대이니 느리더라도 꾸준히 멈추지 않고 나아간다면 분명 승산이 있다고 생각한다.
워밍업 클럽 마무리 관련 소감
워밍업 클럽 전반 관련
네트워킹이 제대로 이뤄지지 못하고 각자도생하는 느낌이어서 아쉬웠다. 워밍업 클럽이 '특정 목표를 가진 사람들을 모아놓자' 딱 거기에 의의가 있는 프로그램이라면 할 말 없지만, 운영 쪽에서 개별 스터디를 장려하는 유인(스터디 과정 제출 시 가산점, 놀러 와서 커피 쿠폰 뿌리고 가기 등)이 있었다면 훨씬 좋았을 것 같다.
감자님 강의 관련 (※ 대문자 T 주의해 주세요 감자님 ㅠㅠㅠ 나쁜 마음은 없습니다ㅠㅠㅠㅠㅠㅠㅠ)
자료구조 및 알고리즘 강의는 만점을 줘도 아깝지 않은 강의였다고 생각한다. 자료구조이나 알고리즘 모두 시각화가 정말 중요하다고 생각하는데, 단순히 달달 외우는 게 아니라 생각할 수 있는 힘을 기르게 해주신 훌륭한 강의였던 것 같다.
운영체제 강의는 아쉬움이 남는다. (내게 이런 평가를 내릴 만큼의 지식이 있기는커녕 그 1%도 안 되지만) 내용상 잘못 설명하신 부분이나 실제로는 다르지만 같다고 퉁치고 넘어가는 내용들이 가끔 있었다. 나만 해도 지난 3주 동안 강의의 큰 오류를 2개나 찾았다. 강의 수강 대상자가 입문자라면 쉬운 설명만큼이나 내용의 정확성도 중요하다고 생각한다. 초보들은 처음 배운 지식을 수정하기가 매우 어렵기 때문이다.
스터디 관련
1주차부터 2주차, 그리고 오늘까지 CS 스터디를 모집해 운영해 왔다. 매주 일요일 2시에, 워밍업 클럽 일정대로 공부한 내용을 공유하는 스터디였는데 이탈률도 높고 남은 사람들의 참여율도 저조했다. 더 이상 말은 안 하겠지만... 많이 실망스러웠다.
그래도 공유해야 할 내용이 있는 만큼 내가 이해한 내용을 하나라도 더 매끄럽게 설명할 수 있게 노력한다든지, 정확한 내용이 맞는지 더블, 트리플, 쿼드러플 체크를 반복했던 점은 좋았다. 혼자 공부할 때도 늘 그렇게 하고 있었다는 게 문제지만.
나 자신 관련
우선 나 자신에게 고생했다고 말하고 싶다. 어찌 됐건 수료를 했으니까. 얻은 것들도 무수히 많고. 무엇보다 막연하기만 했던 'CS란 뭘까?'에 대한 해답과 '비전공자인 내가 CS를 감히 도전해도 될까?'에 대한 해답을 얻은 게 긍정적이다.
하지만, 개인적으로 내가 나에게 느꼈으면 하는 감정은 답답함과 공포였다. 근데 둘 모두 전혀 없다. '비전공자여도 전공자들을 찍어누를 만큼의 지식과 경험, 능력을 갖고 싶다'는 다소 허황된 꿈이 여기서 현실로 다가왔어야 했는데... 아쉽다.
답변 0