📗 self-study/📗 inflearn

[자료 구조와 알고리즘] 정렬 - 병합 정렬

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 정렬 - 병합 정렬 📍 병합 정렬(Merge Sort) 👉🏻 다른 정렬보다는 조금 복잡함 👉🏻 분할 정복(divide and conquer)을 이용할 것 [3, 5, 2, 4, 1, 7, 8, 6] // 한 번에 8개의 원소를 정렬하기 어려우니까 반으로 쪼개서 먼저 생각함! [3, 5, 2, 4] [1, 7, 8, 6] // 또 반으로 쪼개면 더 편하지 않을까? [3, 5] [2, 4] [1, 7] [8, 6] // 또 쪼개면? [3] [5] [2] [4] [1] [7] [8] [6] // 정렬이 필요 없을 정도로 단순해짐! // 이제 순서대로 병합! [3, 5] [2, 4] [1, 7] [6, 8] // 각 배열의 두 개의 원소는 모두 정렬됨! [2, 3,..

[자료 구조와 알고리즘] 정렬 - 삽입 정렬

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 정렬 - 삽입 정렬 📍 삽입 정렬(Insertion Sort) 👉🏻 배열을 두 영역으로 나누어 진행(정렬된/되지 않은 영역) [4, 1, 5, 3, 6, 2] // 정렬되지 않은 영역에서 데이터를 꺼내 정렬된 영역 사이에 삽입 [4, 1, 5, 3, 6, 2] // 첫 번째 숫자인 4만 정렬되어 있다고 가정 _ _ [4, 1, 5, 3, 6, 2] // 정렬되지 않은 영역 데이터 1을 정렬된 데이터 4와 비교한 뒤, 4보다 작으므로 삽입 [1, 4, 5, 3, 6, 2] [1, 4, 5, 3, 6, 2] // 정렬되지 않은 영역 데이터 5를 정렬된 데이터의 가장 오른쪽부터 비교 [1, 4, 5, 3, 6, 2] [1, 4, 5, 3, 6, 2] // 정렬되지..

[자료 구조와 알고리즘] 정렬 - 선택 정렬

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 정렬 - 선택 정렬 📍 선택 정렬(Selection Sort) 👉🏻 배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가지고 옴 [6, 3, 4, 1, 2, 5] // 정렬되지 않은 영역(전체)를 순회 후 가장 작은 값 찾음: 1 _ _ [1, 3, 4, 6, 2, 5] // 가장 작은 값을 첫 번째 원소로 가지고 옴 // 1은 정렬 완료 [1, 3, 4, 6, 2, 5] // 순회 후 가장 작은 값 찾음: 2 _ _ [1, 2, 4, 6, 3, 5] // 가장 작은 값을 첫 번째 원소로 가지고 옴 // 2까지 정렬 완료 [1, 2, 4, 6, 3, 5] // 순회 후 가장 작은 값 찾음: 3 _ ..

[자료 구조와 알고리즘] 정렬 - 버블 정렬

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 정렬 - 버블 정렬 📍 버블 정렬(Bubble Sort) 👉🏻 가장 쉽게 생각할 수 있는 정렬 중 하나로 구현이 쉬우나 성능이 좋지는 않음 [4, 2, 3, 1] // 앞에 있는 숫자와 그 뒤의 숫자를 비교해서 조건에 따라 자리를 바꿈 _ _ [2, 4, 3, 1] _ _ [2, 3, 4, 1] _ _ [2, 3, 1, 4] // 4(마지막 원소) 자리가 고정되었음(정렬 완료) _ _ [2, 3, 1] // 배열 유지 _ _ [2, 1, 3] // 3(마지막 원소) 자리가 고정되었음 _ _ [1, 2] // 남은 원소는 1 하나이므로 정렬 끝 📍 버블 정렬의 구현 [ bubble_sort.mjs ] function BubbleSort(arr) { // 배열이..

[자료 구조와 알고리즘] 재귀 - 하노이 탑

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 재귀 - 하노이 탑 📍 하노이 탑 👉🏻 세 개의 기둥과 서로 다른 크기의 원반들이 있음 👉🏻 가장 큰 원반이 아래 있고, 위로 갈수록 작은 원반으로 이루어짐 👉🏻 다른 기둥으로 원반을 옮겨야 하는데 규칙 1) 한 번에 하나의 원반만 움직일 수 있음규칙 2) 가장 위에 있는 원반만 움직일 수 있음규칙 3) 아래에 작은 원반이 올 수 없음 👉🏻 즉, 기둥 B는 기둥 A의 원반을 기둥 C로 옮기기 위해 임시로 거쳐가는 곳 📍 하노이 탑을 하향식 재귀 방식으로 생각하면? 👉🏻 가장 큰 크기의 원반 3을 가장 아래에 옮겨야 하기 때문에 첫 번째 목표는 원반 3을 기둥 C로 이동시켜야 함 👉🏻 즉 원반 1, 2를 기둥 B로 옮기는 것을 하위 문제로 생각함 👉🏻 👉🏻 원..

[자료 구조와 알고리즘] 재귀적으로 생각하기

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 재귀적으로 생각하기 📍 재귀 함수를 만들 때는 해당 함수가 이미 구현되었다고 생각하면 좋음! ex) 5! = 5 * factorial(4); 1~5까지 배열의 합 = 5 + 1~4까지의 배열 합 📍 패턴 1: 단순 반복 실행 👉🏻 반복문으로 구현했을 때보다 큰 이점이 되는 부분이 없음 👉🏻 오히려 콜 스택 공간을 많이 차지해 성능이 for문보다 좋지 않음 📍 패턴 2: 하위 문제의 결과를 기반으로 현재 문제 계산 👉🏻 ex: facorial //상위 문제 // 하위 문제 return number * factorial(number - 1); 👉🏻 for문을 이용해 계산하는 방식을 상향식 계산, 재귀를 이용하여 하위 문제 기반으로 현재 문제 계산하는 방식을 하향..

[자료 구조와 알고리즘] 재귀(recursion)

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 재귀(recursion) 📍 재귀(recursion) 👉🏻 어떠한 것을 정의할 때 자기 자신을 참조하는 것 👉🏻 주로 함수를 정의할 때 사용하며, 재귀적으로 정의된 함수를 "재귀 함수"라고 함 [ recursion.mjs ] //function myFunction(number) { // console.log(number); // myFunction(number + 1); // } // myFunction(1); // 기저 조건(탈출 조건)이 없으므로 프로그램 자동 종료 = 언제 끝날지 예측 안 됨 // 숫자가 1~11111까지 출력됨(컴퓨터마다 메모리 공간이 달라 다르게 출력될 수 있음) // 메모리 공간이 가득 차면 콜스택으로 자동 중단됨 function ..

[자료 구조와 알고리즘] 셋(Set)

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 셋(Set) 📍 셋(Set) 👉🏻 데이터의 중복을 허용하지 않는 자료 구조 👉🏻 해시 테이블을 이용한 자료 구조로 해시 셋이라고도 불림 👉🏻 Value를 사용하지 않고 Key만 사용하여 구현 📍 셋(Set)의 추상 자료형 [ HashSet.mjs ] ximport { HashTable } from './HashTable.mjs'; class HashSet { constructor() { this.hashTable = new HashTable(); } add(data) { if(this.hashTable.get(data) == null) { this.hashTable.set(data, -1); // 아무 값이나 넣어도 상관은 없으나 예시로 -1 넣음 } } i..

[자료 구조와 알고리즘] 해시테이블(HashTable)

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 해시테이블(HashTable) 📍 해시테이블(HashTable) 👉🏻 해시, 맵,해시맵, 딕셔너리라고도 불림 👉🏻 해시 + 테이블 합쳐진 자료 구조 📍 해시테이블(HashTable) 예시 👉🏻 야구 선수의 등 번호 👉🏻 기존 테이블은 메모리 낭비하는 경우가 있어(ex: 야구 선수 등번호의 경우 빈 숫자가 있음) 특정한 계산(해시 함수, ex: 10으로 나눠서 넣음)을 거쳐 메모리 절약을 하고자 함 👉🏻 키(Key)를 알고 있을 경우 조회/삽입/삭제를 O(1)의 성능으로 접근할 수 있게 됨 👉🏻 단, 이때 등 번호가 11번, 21번이 있다면 해시 함수를 거친 값은 모두 1이 됨 👉🏻 중복된 값이 있다면 같은 인덱스에 연결 리스트로 연결함 👉🏻 21번을 찾고자 ..

[자료 구조와 알고리즘] 덱(Deque)

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 덱(Deque) 📍 덱(Deque) 👉🏻 데이터의 삽입과 제거를 head, tail에서 자유롭게 할 수 있음 👉🏻 덱을 이용하여 스택, 큐를 모두 구현할 수도 있음 📍 덱의 추상 자료형 [ Deque.mjs ] import { DoublyLinkedList } from './DoublyLinkedList.mjs'; class Deque { constructor() { this.list = new DoublyLinkedList(); } printAll() { this.list.printAll(); } // O(1)의 성능 addFirst(data) { this.list.insertAt(0, data); } // O(1)의 성능 removeFirst() { re..