[인프런 워밍업 클럽 3기 - CS] - 1주차 발자국 (자료구조와 알고리즘) - 2
💻 개요📌 배열선언배열의 크기와 함께 변수로 선언하면 연속된 메모리 공간을 찾아 할당한다. 해당 메모리에 배열 요소들을 할당하고 남은 메모리 공간은 쓰레기 값으로 할당해둔다. 이후, 남은 배열 공간에 값을 할당하면 쓰레기 값이 차지하던 주소에 데이터를 덮어씌운다.- 운영체제는 배열의 시작 주소만을 기억한다.- 배열의 인덱스 값을 통해 조회시, 운영체제는 배열의 시작 주소에 인덱스를 더해 데이터를 반환한다. (효율적인 참조 성능)- 하지만 데이터 삽입, 삭제 성능은 비효율적이다. // 6 ~ 10 은 쓰레기 값 할당 int arr[10] = {1, 2, 3, 4, 5}; // 배열의 남은 공간에 데이터를 삽입하면 쓰레기 값 -> 데이터로 덮어씌움 arr[5] = 6; arr[6] = 7; // ✅ 만약 배열의 크기를 넘어서 할당하려면? // 뒤 메모리 공간에 중요한 정보가 있을 수도 있으니 기존 메모리 공간을 확장할 수는 없다. // 새로운 연속된 메모리 공간을 찾아서 배열을 복사하여 할당. // 데이터 삽입, 삭제 성능은 비효율적- Javascript의 경우, 배열은 객체이다.- 대부분 불연속적인 메모리 공간을 할당하여 배열을 생성한다. 📌 연결리스트✅ 개념- 배열의 단점을 해소하기 위해 등장- 메모리 공간에 분산하여 데이터를 저장하고, 해당 데이터들을 연결시켜준다.- 각 데이터를 노드라고 칭하며, 노드는 data와 다음 노드의 주소를 담는 next를 저장한다.- 첫 노드의 주소만 알고 있다면, 그 이후의 노드 또한 접근할 수 있다.⭕ 데이터 삽입 및 삭제- 배열에서 중간에 데이터를 삽입하기 위해서 이후 데이터를 모두 한 칸 씩 뒤로 미뤄서 저장시켜줘야 했음- 연결리스트는 삽입하려는 데이터의 노드를 생성하고 삽입 위치의 앞, 뒤 노드의 연결만 수정해주면 쉽게 삽입이 가능- 삭제도 마찬가지.❌ 데이터 참조- 배열은 연속된 메모리 공간이 할당되어, 접근의 시간 복잡도는 O(1)- 연결리스트는 데이터가 분산되어 있기 때문에, 첫 번째 노드부터 순서대로 노드를 참조해가며 데이터에 접근 - 시간 복잡도 O(n)- 참조가 많이 이루어지는 상황: 배열- 삽입, 삭제가 많이 이루어지는 상황: 연결리스트 ✅ 구현추상자료형 : 데이터와 해당 데이터를 다루는 연산을 함께 묶어 추상적으로 정의연결리스트의 추상자료형1. printAll(): 모든 데이터 출력2. clear(): 모든 데이터 제거3. insertAt(index, data): 인덱스 데이터 삽입4. insertLast(data): 마지막 데이터 삽입5. deleteAt(index): 인덱스 데이터 삭제6. deleteLast(): 마지막 데이터 제거7. getNodeAt(index): 인덱스 데이터 조회 📌 스택(Stack)✅ 개념FILO(First In Last Out) 규칙을 갖고 있는 리스트먼저 들어온 노드가 가장 나중에 나간다.1. 엘리베이터에 줄을 서있는 상태 - 엘리베이터에서 내릴 때는 늦게 탄 사람이 먼저 내린다.2. 설거지 - 씻어야 할 접시가 쌓이고 마지막에 쌓인 접시 먼저 설거지를 한다.3. 되돌리기 작업 - 실행된 작업이 쌓이고 마지막 작업으로 되돌린다.4. 문법 검사기 - 열린 괄호를 먼저 넣고 닫는 괄호가 올바르게 들어오는 지 확인 ✅ 구현스택의 추상자료형1. push: 데이터 삽입2. pop: 데이터 제거3. peek: 데이터 참조4. isEmpty: 비었는지 체크 📌 큐(Queue)✅ 개념FIFO(First In First Out) 규칙을 갖고 있는 리스트먼저 들어간 노드가 먼저 나온다.1. 마트에서 줄 설 떄 - 먼저 줄 선 사람이 계산을 먼저 한다.2. 운영체제 프로세스 - 운영체제가 프로세스 순서대로 CPU 연산을 처리1. tail의 등장- head만 있다면 처음 들어온 데이터를 제거하기 위해서 head부터 해당 노드까지 이동해야 함 - O(n)- tail을 저장하여 마지막 노드(처음 들어온 데이터)의 위치를 저장 - O(1)2. 단방향 연결리스트 보완- tail 노드를 삭제해도 이전 노드를 참조할 수 없음(단방향으로 head부터 저장되기에) - O(n)- 이중 연결리스트를 통해 각 노드는 이전 노드와 다음 노드의 위치를 저장한다 - O(1) ✅ 구현큐의 추상자료형1. enqueue: 데이터 삽입2. dequeue: 데이터 제거3. front: 데이터 참조4. isEmpty: 비었는지 체크 📌 덱(Deque)✅ 개념데이터의 삽입과 제거를 head와 tail에서 자유롭게 가능하다. ✅ 구현덱의 추상자료형1. printAll: 모든 데이터 출력2. addFirst: head에 데이터 삽입3. removeFirst: head에서 데이터 제거4. addLast: tail에 데이터 삽입5. removeLast: tail에 데이터 제거6. isEmpty: 리스트 비었는지 체크 📌 해시테이블✅ 개념- 해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)라고도 불린다.- 해시와 테이블이 합쳐진 자료구조 해시함수입력값(`key`)를 고유한 값(`index`)로 변환하는 함수.- 데이터의 균등한 분포가 중요해시 함수를 통해 반환된 index값과 value를 테이블에 저장하고 동일한 index를 반환한 다른 value는 연결 리스트를 통해 저장이 가능하다. 장점1. 빠른 데이터 탐색, 삽입, 삭제가 가능 (`O(1)`)- 만약 동일한 인덱스의 연결 리스트로 조회 시, O(n)단점1. 해시 함수에 따라 메모리 공간 낭비가 발생할 수 있음2. 좋은 해시 함수의 구현은 필수적이다. ✅ 구현해시 테이블의 추상자료형1. set: 데이터 삽입2. get: 해당 key의 value 조회3. remove: 해당 key의 value 제거 📌 셋✅ 개념- 셋(Set) : 데이터 중복을 허용하지 않는 자료구조 ✅ 구현셋의 추상자료형1. add(data): 데이터 삽입2. isContain(data): 데이터 체크3. remove(data): 데이터 제거4. clear(): 셋 비우기5. isEmpty(): 셋 비었는지 체크6. printAll(): 모든 데이터 출력 📌 더 찾아본 점❓ 자바스크립트에서의 배열1. 동적 크기 조정 가능- 자바스크립트 배열은 동적으로 크기가 조정된다.- 새로운 요소를 추가하거나 제거하면 그에 맞춰 배열의 크기가 변경된다.2. 다양한 데이터 타입 저장 가능- number, string, boolean, object 등 다양한 타입의 데이터가 배열에 저장될 수 있다.- 자바스크립트의 배열을 객체이기 때문에, 객체의 프로퍼티로 모든 데이터 타입이 저장 가능하다.3. 타입은 객체(`object`) 이지만 배열 메서드를 제공한다.- push(), pop(), map() 등 배열에서 사용가능한 메서드를 제공한다. ❓ typeof([])는 왜 object로 결과가 나올까?✅ typeof 연산자는 매개변수의 자료형이 원시 값인지, 참조 값인지를 구분해준다. 자바스크립트 배열의 prototype을 보면 Array.prototype을 갖고 그 상위 프로토타입은 Object.prototype을 갖는다. 그렇기에 결국 배열은 객체의 프로토타입을 상속받고 있기에 참조값이며 object가 반환된다. ❓ 원시 값, 참조 값이 뭐야?✅ 원시 값(Primitive Value)은 값이 변경될 수 없고(immutable), 직접 값이 저장되는 데이터 형태를 의미한다. 새로운 값을 변수에 저장하면 메모리 주소에 해당 값이 그대로 저장되며 변수에 값을 변경시키면 새로운 메모리에 값을 할당시킨다. 즉, 기존 메모리 주소에 저장된 값을 변경시킬 수 없다.- undefined, boolean, number, string ,,참조 값(Reference Value)는 값이 변경 가능(mutable)하고 참조형 데이터를 의미한다. 변수가 직접 값을 저장하는 것이 아닌 해당 값이 위치한 메모리 주소를 참조한다. 객체의 프로퍼티 값을 변경하게 되면 해당 메모리를 참조하는 모든 변수들이 영향을 받는다.- Object, Array, Function ❓ typeof([])는 그럼 왜 배열 메서드를 사용할 수 있는가?✅ arr → Array.prototype → Object.prototype → null 이런 프로토타입 체인을 갖고 있기 때문에, 결국 배열은 Array.prototype에서 제공하는 메서드를 상속받아서 사용할 수 있다. ❓ 해시 충돌에 대한 극복 방법✅ 해시 충돌(Hash Collision)을 극복하기 위해 다양한 방법들이 존재.1. 분리 연결법(Separate Chaining): 해시 함수를 통해 동일한 버킷에 할당된 데이터들을 연결시켜 관리한다.- 간단한 구현으로 해시 테이블의 크기를 확장할 필요가 없다- 데이터의 양이 많아질 수록, 동일 버킷에 체이닝된 데이터가 많아진다. (쏠림 현상)2. 개방 주소법(Open Addressing): 버킷에 하나의 데이터만 저장하고, 충돌 시에 비어있는 버킷에 할당- 동일한 규칙을 통해 비어있는 버킷을 찾아야 한다.1. 선형 탐색(Linear Probing): index로부터 n만큼 이동하여 빈 버킷 검색2. 제곱 탐색(Quadratic Probing): index로부터 제곱수만큼 이동하여 빈 버킷 검색(+1, +4, +9,,)3. 이중 해시(Doouble Hashing): 다른 해시함수를 한 번 더 적용- 선형 탐색으로 구현해본 해시 테이블 📔 회고CS 로드맵에 참여하면서 목적없이 강의를 듣고 공부하기 보다는이 로드맵을 통해 어떤 것을 얻고 싶고 클럽이 진행하는 동안 어떤 것을 꾸준히 지켜나갈 것인지 정하여 공부하는 것이 나의 성장을 더 효율적으로 끌어올려 줄 것 같아, 미리 선정하고 수업에 임하였다.🚀 최종 목표 : 로드맵을 마무리하고 알고리즘 문제들을 제대로 이해할 수 있을 정도의 수준이 되기.🚀 매주 규칙:각 섹션마다 하나의 .md 파일을 생성하고, 섹션 내 각 유닛은 헤더로 구분강의를 듣고 최대한 이쁘게 (?) 정리해놓기매 강의를 듣고 궁금하거나 이해가 안가는 부분은 추가적으로 더 찾아서 정리해두기기존의 계획은 강의를 수강하면서 어느 정도의 지식을 갖춘 상태에서 알고리즘 문제에 도전하려 하였다.하지만 완벽한 준비는 없을 것 같기도 하고, 쉬운 문제부터 차근차근 풀어보면 목적의식을 가져가며 강의도 수강할 수 있을 것 같고, 더 빠르게 습관화시킬 수 있을 것 같아, 2주차부터는 강의를 듣고 관련된 알고리즘 문제를 한 문제씩 풀어보려고 한다. 강의에 관련된 알고리즘 최소 1문제씩 풀어 습관화
