몽땅뚝딱 개발자

15장, 16장 다시 읽어보기 .. 🥺 트리(Tree) 순서를 유지하면서도 빠른 검색과 삽입, 삭제가 가능한 자료 구조가 필요한 경우에 사용한다. 트리도 노드 기반 자료 구조이지만 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다. 트리의 각 노드에는 다른 두 노드로 이어지는 링크가 있다. 1.1. 개념 루트(root): 가장 상위 노드로 꼭대기에 있다. 부모(parent), 자손(descendant), 조상(ancestor) 레벨(level): 각 줄을 의미한다. 프로퍼티(property): 균형 잡힌 정도이다. 모든 노드에서 하위 트리의 노드 개수가 같으면 그 트리는 균형(balanced) 트리다. 1.2 이진 탐색 트리 이진과 탐색이라는 수식어가 붙는데 이진 트리는 각 노드에 자식이 0개나 1..

연결 리스트(linked list) 1.1. 연결 리스트가 유용한 순간 연결 리스트는 배열과 상당히 유사하지만 자료 구조의 성능에 큰 차이가 있다. 가령 세 번째 node에 있는 값을 읽거나 검색하기 위해서는 첫 번째부터 접근하여 순차적으로 진행해야 하므로 O(N)이다. 따라서 읽기와 검색에서는 유의미한 차이가 없지만 연결 리스트는 삽입에서 빛을 발휘한다. 배열에서 최악의 시나리오는 인덱스 0에 데이터를 삽입하거나 삭제할 때이다. 나머지 데이터를 한 셀씩 오른쪽으로 옮겨야 하기 때문에 효율성은 O(N)이 된다. 반면 연결 리스트는 딱 한 단계인 O(1)만 걸린다. 삽입하는 경우 배열처럼 한 셀씩 옮기는 것이 아니라 기존 리스트 앞에 새 노드를 생성하고 노드가 이전의 첫 번째 노드를 가리키도록 만들면 된다..

퀵 정렬(Quicksort) 버블 정렬, 선택 정렬, 삽입 정렬같은 알고리즘이 있지만 대부분의 언어에서는 퀵 정렬(Quicksort)를 선택한다. 퀵 정렬은 매우 빠른 정렬 알고리즘으로 평균 시나리오에서 효율적이다. 최악의 시나리오에서는 삽입 정렬, 선택 정렬과 성능이 유사하지만 대부분의 경우의 평균 시나리오에서는 훨씬 빠르다. 1.1. 퀵 정렬의 분할 퀵 정렬은 분할이라는 개념에 기반한다. 배열을 분할 한다는 것은 배열로부터 임의의 수인 피벗(pivot)을 가져와 피벗보다 작은 모든 수는 피벗의 왼쪽에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 둔다. 1. 여기서 3을 피벗으로 지정하고 두 개의 포인터를 사용한다. 0 pointer1 5 2 1 6 pointer2 3 pivot 2. 왼쪽 포인터를 한 셀..

재귀 함수 올바르게만 사용하면 재귀는 강력한 도구가 될 수 있다. 사용 예시 1. 카운트다운 함수를 for문으로 작성할 수도 있겠지만 재귀를 사용할 수도 있다. // for문으로 작성 function countdown(number) { for (let i=number i>=0; i--) { console.log(i); } } // 재귀로 작성 function countdown(number) { console.log(i); if (number === 0) { return; } else { countdown(number - 1); } } 사용 예시 2. 모든 하위 디렉토리까지 반환하는 함수의 경우 하위 디렉토리의 단계를 알 수 없다. 이 때 재귀를 사용하여 원하는 만큼 아래로 가 하위 디렉토리를 알 수 있다..

스택(stack) 1.1. 정의 스택이 데이터를 저장하는 방법은 배열과 같으며 단순히 원소들의 리스트이다. 스택 연산을 묘사하는 데 쓰이는 유용한 두문자어가 LIFO(Last In, First Out)이다. 스택은 다음과 같은 세 가지 제약이 있다. 데이터는 스택의 끝에만 삽입할 수 있다. 데이터는 스택의 끝에서만 삭제할 수 있다. 스택의 마지막 원소만 읽을 수 있다. 접시 더미나 수직으로 놓인 배열로 묘사하여 생각해보자. 1.2. 용어 푸시(push): 스택에 값을 추가하는 것 팝(pop): 스택의 위에서 원소를 제거하는 것 예를 들어, 대괄호와 중괄호가 잘 닫혔는지 확인하는 linter를 구현한다고 쳐보자. "var a = { y: [1, 2, 3] }"라는 문장을 처리할 때 각 여는 괄호를 만날 때..

대부분의 프로그래밍 언어는 해시 테이블이라는 자료 구조를 포함하는데 빠른 읽기라는 엄청난 능력이 있다. 해시 테이블은 쌍으로 이뤄진 값들의 리스트로 키를 사용하여 값을 찾는다. 해시 테이블은 프로그래밍 언어에서 서로 다른 이름으로 불린다. 해시, 맵, 해시 맵, 딕셔너리, 연관 배열 등이다. 딱 한 단계만 걸리므로 평균적으로 효율성이 O(1)이다. 룩업 시 단방향(one-directional)이다. 해시 함수를 만드는 대표적인 방법으로는 나누기, 곱하기가 있다. 1.1. 곱하기 시의 문제 곱하기 시 만약 키 값이 동일할 경우 문제가 생긴다. 알파벳 순서대로 숫자로 변환하여 해싱하고(A는 1, B는 2..) 문자열을 특정 숫자로 변환한다고 쳤을 때, BAD는 2 x 1 x 4로 8이라는 키 값을 가진다. ..

지금까지는 최악의 시나리오만 생각하여 빅오를 추론했다. 하지마 최악의 시나리오 외에 고려할 사항들이 있다. 정렬의 종류에는 버블 정렬, 삽입 정렬, 선택 정렬이 있는데 최악의 시나리오만을 고려했을 때 선택 정렬이 가장 나은 방법이라고 생각할 수 있다. 하지만 평균 시나리오도 중요하게 고려해야 한다. 삽입 정렬 선택 정렬 정의 임의로 첫번째 인덱스의 값을 삭제한 뒤 임시 변수에 담아놓고 왼쪽에 있는 값을 비교하여 임시 변수에 있는 값보다 크면 값을 오른쪽으로 시프트하고 공백에 임시 변수에 있는 값을 담는다. 최소값을 찾은 뒤 다음 인덱스와 교환한다. 최악의 시나리오 N²단계 N² / 2단계 평균 시나리오 N² / 2단계 N² / 2단계 최선의 시나리오 약 N단계 N² / 2단계 거의 정렬된 데이터를 다룰거..

빅 오는 알고리즘을 서로 비교하고 주어진 상황에 알맞은 알고리즘을 결정하게 해주는 도구이지만 유일한 도구는 아니다. 빅 오 표기법에서는 한 알고리즘이 다른 알고리즘보다 훨씬 빠른 경우에도 두 경쟁 알고리즘을 똑같은 방식으로 표기하기도 한다. 선택 정렬(selection sort) 1.1. 선택 정렬(selection sort)이란? 1단계. 값을 왼쪽 → 오른쪽으로 확인하며 어떤 값이 최솟값인지 결정한다. 2단계. 최솟값이 정해졌다면 가장 패스스루를 처음 시작했을 때의 값과 교환한다. 두번째 패스스루는 인덱스 1부터 시작하게 된다. 매 패스스루는 1, 2단계를 반복하며 배열 끝에서 시작하는 패스스루에 도달할 때 까지 반복한다. 1.2. 선택 정렬의 효율성 export const selectionSort ..

버블 정렬(Bubble sort) 1.1. 버블 정렬 알고리즘 이런 배열이 주어졌을 때 버블 정렬 알고리즘이 어떻게 동작하는지 보자. [2, 1, 3, 5] 1. 배열내에서 연속된 두 항목을 가리킨다. 처음에는 배열의 첫 원소부터 시작한다. [2, 1, 3, 5] 2. 두 항목의 순서가 바뀌어있으면 두 항목을 교환하며, 순서가 올바르다면 아무것도 하지 않는다. [1, 2, 3, 5] 3. 포인터를 오른쪽으로 한 셀씩 옮긴다. [1, 2, 3, 5] 4. 배열의 끝까지 이 단계를 반복한다. 이를 패스스루(pass-through)라 한다. 끝나면 다시 처음 두 값으로 옮겨서 1~3단계를 다시 실행함으로써 새로운 패스스루를 실행한다. 교환이 일어나지 않는 패스스루가 생길 때 까지 패스스루를 반복한다. 1.2...

어떤 알고리즘을 "22단계의 알고리즘", "400단계의 알고리즘"이라고 표시할 수는 없다. 선형 검색의 효율성을 정량화하는 보다 효과적인 방법은 배열에 N개의 원소가 있을 때 선형 검색에 N단계가 필요하다고 표현하는 것이다. 그래서 수학적 개념을 차용하여 이러한 개념을 형식화한 표현을 빅 오 표기법이라 부른다. 이 표기법을 사용하여 주어진 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다. 선형 검색에는 배열의 원소 수만큼의 단계가 필요하다. O(N) "빅 오 N"이라고 발음하며 "차수 N"이라고도 부른다. "알고리즘에 N단계가 필요하다"라는 뜻이다. 이 O(N)인 알고리즘을 선형 시간을 갖는 알고리즘이라고도 부른다. N이 얼마든 항상 상수 단계만 필요하기떄문에 상수 시간(constant time)을..