인프런 워밍업 클럽 스터디 3기 - 1주차 발자국
모든 내용은 감자님의 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 강좌를 정리한 내용입니다.자료구조와 알고리즘 1일차1⃣ 자료구조자료구조는 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냅니다.대표적인 예 1) → 변수숫자나 문자열 저장하기 위해 변수 사용let a = 87; 예2) 배열숫자나 문자열 등을 연속적으로 저장접근 → 인덱스let arr = [87, 70, 100]; arr[1] ✅ 일반 변수와 배열의 처리방법의 차이? 🤔let a = 87; let b = 70; let c = 100; let average = (a + b + c) / 3; let arr = [87, 70, 100]; // 평균 변수 초기화 let average = 0; for(let i = 0; i < arr.length; i++) { average += arr[i]; } average /= arr.length; 4개의 숫자의 평균을 구한다고 가정하고 각자의 방법으로 처리하면// 변수를 추가하고 평균 구한 코드도 수정해야함 let a = 87; let b = 70; let c = 100; // 변수 추가 let d = 55; // 평균 구하는 코드 수정 let average = (a + b + c + d) / 4; // 배열에 데이터만 입력하면 평균이 구해진다. let arr = [87, 70, 100, 55]; // 평균 변수 초기화 let average = 0; for(let i = 0; i < arr.length; i++) { average += arr[i]; } average /= arr.length; ✔ 배열의 처리 방법이 유지/보수가 변수의 처리 방법보다 편리하다.2⃣ 알고리즘어떤 문제를 해결하기 위한 확실한 방법배열의 모든 숫자를 더하고 원소의 개수만큼 나눠라데이터가 어떤 자료구조를 하고 있는지에 따라 평균을 구하는 방식이 달라졌다.즉, 자료구조에 따라서 알고리즘이 달라진다.앞서 배열 자료구조의 평균을 구하는 방법에서 여러가지의 알고리즘이 있을 수 있다.✔” 배열의 모든 숫자를 더하고 원소의 개수만큼 나눠라 “✔” 배열의 첫 번째 원소와 두 번째 원소, 세 번째 원소를 더하고 3을 나눠라 “즉, 같은 자료구조에 대해서도 알고리즘은 여러가지가 있을 수 있다.시간복잡도1⃣ 더 좋은 알고리즘의 기준문제를 해결할 때 더 좋은 알고리즘을 사용하는 것이 당연하다.사용자의 요구에 따라 다르지만, 일반적으로 알고리즘의 속도가 성능의 척도가 된다. 이를 시간 복잡도라 부른다.✔ 시간 복잡도란?특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간컴퓨터에 성능에 따라 알고리즘을 처리하는데 걸리는 시간이 다르므로, 알고리즘을 평가할 때는 시간을 측정하는 것이 아닌 코드에 성능에 많은 영향을 주는 부분을 평가한다.이는 반복문이다.반복문이 많으면 느려지기 때문이다.예제)// 주어진 배열에서 5를 찾으시오 let arr = [1, 3, 5, 7]; // 최선의 경우 한 번에 찾음 -> Big-오메가 // 최악의 경우 배열의 길이만큼 걸림 -> Big-O // 평균의 경우 배열 길이의 중간만큼 걸림 -> Big-세터 빅오표기법최악의 경우 찾는 데이터가 배열의 끝에 있을 때배열의 길이가 n이라면 최악의 경우 n번 만에 찾을 수 있다. 이를 O(n), 선형시간 알고리즘이다.✔ 입력이 늘어날 때 계산량이 늘어나는 척도를 나타내기 위한 것운영체제가 하는 일1⃣ 프로세스 관리브라우저를 켜 놓고 노래도 들으며 게임을 해도 전부 동시에 실행이 된다.운영체제가 프로세스를 관리하지 않는다면 이 중 한 가지만 실행될 것입니다.2⃣ 메모리 관리3⃣ 하드웨어 관리운영체제는 사용자의 하드웨어에 대한 직접적인 접근을 막는다.특정 영역에 다른 중요한 데이터가 있을 수도 있고 공격을 막기 위해서이다.4⃣ 파일 시스템 관리운영체제의 역사1⃣ 1940년대애니악세계에서 가장 큰 스케일의 전자디지털 계산기입출력 속도가 느리고 입출력 도중에는 계산을 할 수 없음.인력으로 cpu를 대체2⃣ 1950년도 초반직접 회로(IC) 개발CPU, 메모리는 존재했지만 키보드와 모니터는 없었다. 대신 펀치카드를 이용하여 구멍을 뚫어 컴퓨터가 계산을 하게 하고 이를 라인프린터로 출력하는 방식을 사용3⃣ 중후반컴퓨터의 처리속도보다 오퍼레이터가 카드를 넣고 전달하는 과정이 느리게 느껴짐.오퍼레이터의 오버헤드가 큼이를 해결하기 위해 싱글스트림 배치시스템을 도입함.프로그래머가 펀치 카드를 여러 개를 가지고 오면 이를 한 번에 컴퓨터에 전달해주고 컴퓨터는 여러 개의 프로그램을 순서대로 실행해서 결과를 한 번에 확인할 수 있게 하는 시스템이다.1960년대시분할 시스템(시간 분할 시스템)유닉스 운영체제를 개발했는데 이는 멀티 프로그래밍과 다중 사용자와 파일시스템을 개발한 운영체제이다.✔ 문제점메모리 침범 문제70년대개인 컴퓨터 시대애플의 매킨토시 마이크로소프트의 MS-DOS 사용운영체제의 구조✅ 커널프로세스와 메모리, 저장장치를 관리하는 기능 담당사용자는 인터페이스를 통해서만 커널에 접근 가능✔ GUI(Graphic User Interface)그래픽으로 커널과 상호작용(마우스를 이용)✔ CLI(Command-Line Interface)텍스트를 이용해 커널과 상호작용(직접 텍스트 입력)사용자와 어플리케이션은 커널과의 인터페이스로 시스템 콜을 사용, 하드웨어와 커널의 인터페이스로는 드라이버 사용컴퓨터 하드웨어와 구조1⃣ 폰 노이만 구조프로그램 내장 방식애니악과 같이 하드웨어로 프로그램을 만들었기 때문에 프로그램이 달라질 때마다 매번 스위치와 배선을 다시 조정을 해야했다.이를 해결하기 위해 CPU와 메모리(RAM) 사이에 버스(데이터를 전달하는 통로)를 둔다.프로그램은 메모리에 올려서 실행시키는데 프로그램을 메모리에 내장했다고 해서 프로그램 내장방식이라고 한다.2⃣ 컴퓨터 하드웨어메인보드다른 하드웨어를 연결하는 장치3⃣ CPU 구조CPU(Central Processing Unit)는 중앙처리장치라고 부른다.이를 구성하는 장치는 세 가지로 나뉜다.산술논리 연산장치(Arithmetic and Logic Unit, ALU)제어장치 (Control Unit) - 모든 장치들의 동작을 지시하고 제어하는 장치레지스터(변수)4⃣ 메모리 종류메모리는 크게 RAM과 ROM으로 구별할 수 있다.RAM(Random Access Memory)은 랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 읽는 속도가 같습니다. 전력이 끊기면 데이터도 같이 끊긴다.ROM(Read Only Memory)전력이 끊겨도 데이터를 계속 보관할 수 있지만 데이터를 한 번 쓰면 수정이 불가능주로 부팅과 관련된 바이오스를 저장하는 데 주로 쓰임.3⃣ 중후반컴퓨터의 처리속도보다 오퍼레이터가 카드를 넣고 전달하는 과정이 느리게 느껴짐.오퍼레이터의 오버헤드가 큼이를 해결하기 위해 싱글스트림 배치시스템을 도입함.프로그래머가 펀치 카드를 여러 개를 가지고 오면 이를 한 번에 컴퓨터에 전달해주고 컴퓨터는 여러 개의 프로그램을 순서대로 실행해서 결과를 한 번에 확인할 수 있게 하는 시스템이다.1960년대시분할 시스템(시간 분할 시스템)유닉스 운영체제를 개발했는데 이는 멀티 프로그래밍과 다중 사용자와 파일시스템을 개발한 운영체제이다.✔ 문제점메모리 침범 문제70년대개인 컴퓨터 시대애플의 매킨토시 마이크로소프트의 MS-DOS 사용컴퓨터 부팅과정✅ ROM에 저장된 바이오스 실행주요 하드웨어에 이상이 없는지 체크이상이 있으면 부팅이 되지 않고, 이상이 없다면 하드디스크에 있는 마스터 부트 레코드에 저장된 부트로더를 메모리로 가져와서 실행한다.윈도우나 리눅스 둘 중 하나의 운영체제를 선택하면 부팅이 완료됨.인터럽트1⃣ 폴링(Polling)CPU가 입출력 장치에 데이터를 읽거나 쓰려고 하는 상황을 생각해보면CPU가 입출력 장치에 명령을 내리고CPU관점에서 입출력 명령이 언제 완료될 지 알 수 없기 때문에 주기적으로 학인해줘야한다.이를 폴링방식이라고 한다.이는 성능이 좋지 않다는 단점을 가지고 있다.2⃣ 인터럽트폴링 방식의 단점을 해결한 방식입출력 관리자는 입출력이 완료됐을 때 CPU에게 신호를 주고 CPU는 그 신호를 받아 인터럽트 서비스 루틴(ISR)을 실행시켜 작업을 완료한다.하드웨어 인터럽트입출력 등과 같은 인터럽트가 있다.소프트웨어 인터럽트2⃣ 컴퓨터 하드웨어메인보드다른 하드웨어를 연결하는 장치3⃣ CPU 구조CPU(Central Processing Unit)는 중앙처리장치라고 부른다.이를 구성하는 장치는 세 가지로 나뉜다.산술논리 연산장치(Arithmetic and Logic Unit, ALU)제어장치 (Control Unit) - 모든 장치들의 동작을 지시하고 제어하는 장치레지스터(변수)4⃣ 메모리 종류메모리는 크게 RAM과 ROM으로 구별할 수 있다.RAM(Random Access Memory)은 랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 읽는 속도가 같습니다. 전력이 끊기면 데이터도 같이 끊긴다.ROM(Read Only Memory)전력이 끊겨도 데이터를 계속 보관할 수 있지만 데이터를 한 번 쓰면 수정이 불가능주로 부팅과 관련된 바이오스를 저장하는 데 주로 쓰임.3⃣ 중후반컴퓨터의 처리속도보다 오퍼레이터가 카드를 넣고 전달하는 과정이 느리게 느껴짐.오퍼레이터의 오버헤드가 큼이를 해결하기 위해 싱글스트림 배치시스템을 도입함.프로그래머가 펀치 카드를 여러 개를 가지고 오면 이를 한 번에 컴퓨터에 전달해주고 컴퓨터는 여러 개의 프로그램을 순서대로 실행해서 결과를 한 번에 확인할 수 있게 하는 시스템이다.1960년대시분할 시스템(시간 분할 시스템)유닉스 운영체제를 개발했는데 이는 멀티 프로그래밍과 다중 사용자와 파일시스템을 개발한 운영체제이다.✔ 문제점메모리 침범 문제70년대개인 컴퓨터 시대애플의 매킨토시 마이크로소프트의 MS-DOS 사용자료구조와 알고리즘 2일차 1⃣ 배열메모리의 특정 크기의 연속된 공간을 미리 할당받는 자료구조JavaScript의 배열은 C언어에서의 배열과는 달리 객체를 가지는 형태이다.2⃣연결리스트불연속적인 메모리 위치에 저장하며, 노드를 생성하여 이 안에 데이터와 다음 노드를 가리키는 포인터를 저장하여 연결하는 자료구조이다. class Node { constructor(data, next = null) { // this.변수 -> 프로퍼티 this.data = data; this.next = next; } } class LinkedList { constructor() { this.head = null; this.count = 0; } printAll() { let currentNode = this.head; let text = "["; while (currentNode != null) { text += currentNode.data; currentNode = currentNode.next; if (currentNode != null) { text += ", "; } } text += "]"; console.log(text); } // 리스트의 모든 원소를 제거하는 함수 clear() { this.head = null; this.count = 0; } insertAt(index, data) { if (index < 0 || index > this.count) { throw new Error("범위를 벗어났습니다."); } let newNode = new Node(data); if (index == 0) { newNode.next = this.head; this.head = newNode; } else { let currentNode = this.head; for (let i = 0; i < index - 1; i++) { currentNode = currentNode.next; } newNode.next = currentNode.next; currentNode.next = newNode; } this.count++; } // 마지막 데이터 뒤에 삽입하는 기능 insertLast(data) { this.insertAt(this.count, data); } deleteAt(index) { if (index < 0 || index > this.count) { throw new Error("범위를 벗어났습니다."); } let currentNode = this.head; if (index == 0) { let deleteNode = this.head; this.head = this.head.next; this.count--; return deleteNode; } else { for (let i = 0; i < index - 1; i++) { currentNode = currentNode.next; } } let deleteNode = currentNode.next; currentNode.next = currentNode.next.next; this.count--; return deleteNode; } } // 다른 자바스크립트 파일에서 Node 클래스를 참조할 수 있도록 export export { Node, LinkedList }; 3⃣Operating System프로그램은 수동적(코드가 실행되기를 기다림), 프로세스는 능동적(메모리, CPU등 사용)이다.프로세스는 Code, Data, Heap, Stack 영역으로 이루어져있다.생성된 프로세스를 연결리스트 형태인 PCB로 저장한다.자료구조와 알고리즘 3일차1⃣스택FIFO의 특징을 가지는 자료구조이다.2⃣큐FIFO의 특징을 가지는 자료구조로 작업 스케쥴링 등에 활용된다. 3⃣ 해시 테이블 (Hash Table) Key-Value 형태로 데이터를 저장하는 자료구조빠른 검색(O(1))이 가능하지만, 해시 충돌이 발생할 수 있다. 4⃣트리 (Tree) 계층 구조를 이루는 자료구조. 이진 탐색 트리 (BST): O(log n)의 탐색 속도를 가진다.힙 (Heap): 우선순위 큐 구현에 사용된다.트라이 (Trie): 문자열 검색 최적화.5⃣ 그래프 (Graph) 정점(Vertex)과 간선(Edge)으로 구성된 자료구조.최단 경로 탐색 (Dijkstra), 최적 경로 찾기 (A*) 등에 활용된다.\ 자료구조 FCFS 먼저 도착한 순서대로 실행 (대기 시간 증가 가능) SJF 실행 시간이 가장 짧은 프로세스부터 실행 SRTF 남은 실행 시간이 가장 짧은 프로세스부터 실행 RR 일정 시간(Time Quantum)마다 프로세스를 교체 Priority Scheduling 혼합 우선순위가 높은 프로세스부터 실행
