All

16장 힙으로 우선순위 유지하기

이진 탐색 트리 외의 다른 트리 종류가 많다. 그 중 하나가 힙이라는 트리이다. 힙은 데이터 세트에서 가장 큰 또는 가장 작은 데이터 원소를 계속 알아내야 할 때 특히 유용하다. 16.1 우선순위 큐 앞서 배웠던 큐는 First In, First Out 방식으로 큐 끝에서만 데이터를 삽입하고 큐 앞에서만 접근과 삭제를 수행한다. 즉, 큐의 데이터에 접근하려면 데이터가 삽입했던 순서에 우선권이 있다. 우선순위 큐는 삭제와 접근에 있어 전형적인 큐와 흡사하나, 삽입에 있어 정렬된 배열과 비슷한 리스트다. 즉, 우선순위 큐 앞에서만 데이터에 접근하고 삭제하되 데이터를 삽입할 때는 데이터를 늘 특정 순서대로 정렬시킨다. 병원 응급실의 중증도 분류체계 관리 애플리케이션을 예로 들어보자. 응급실에서는 도착한 순서대..

15장 이진 탐색 트리로 속도 향상

정렬 알고리즘은 아무리 빨라도 O(NlogN)시간이 걸린다. 따라서 데이터를 자주 정렬해야 하면 다시 정렬하는 일이 없게 애초에 데이터를 항상 정렬된 순서로 유지하는 편이 합리적이다. 정렬된 배열은 순서대로 데이터를 유지하는 간단하면서도 효과적인 도구다. 또한 특정 연산에 매우 빨라서 읽기에는 O(1), 이진 검색을 사용할 때는 O(logN)이 걸린다. 하지만 삽입과 삭제가 상대적으로 느리다. 최악의 시나리오일 경우 N단계가 걸리고, 평균적으로 N / 2 단계가 걸린다. 즉 O(N)이므로 단순한 삽입이나 삭제치고는 느리다. 전반벅으로 빠른 속도를 내는 자료 구조를 원한다면 해시 테이블이 좋은 선택지다. 해시 테이블은 검색, 삽입, 삭제가 O(1)이다. 연산이 빠르지만 순서를 유지하지 못하므로 알파벳순으로..

Next.js를 사용하는 이유

Framework vs Library React는 라이브러리이고, Next는 React의 프레임워크이다. 이 둘의 궁극적인 차이점은 “응용 프로그램의 흐름 주도권을 누가 가지고 있느냐" 이다. 여기서 프레임워크란? 원하는 기능 구현에 집중하여 개발할 수 있도록 일정한 형태와 필요한 기능을 갖추고 있는 골격 즉, 뼈대를 의미한다. 사용자는 코드를 작성하여 애플리케이션을 개발한다. 여기서 앱/서버 등의 구동, 메모리 관리, 이벤트 루프 등의 공통된 부분을 프레임워크가 관리한다. 라이브러리란? 컴퓨터 프로그램이 사용하는 비휘발성 자원의 모임. 즉, 특정 기능을 모아둔 코드 혹은 함수들의 집합이며 코드 작성 시 활용 가능한 도구들을 의미한다. Next.js SSR을 쉽게 구현하도록 도와주는 프레임워크 Next...

14장 노드 기반 자료 구조

다양한 자료 구조는 모두 노드라는 개념에 기반해 만들어졌다. 노드란 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각이다. 노드 기반 자료 구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하는데 성능상 큰 이점이 많다. 14장에서는 가장 간단한 노드 기반 자료 구조이자 이후 배울 내용의 기반인 연결 리스트 살펴본다. 14.1 연결 리스트 연결 리스트 (Linked List)는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 배열과 연결 리스트는 외견상 상당히 비슷한 모습으로 동작하지만 내부적으로는 크게 다르다. 앞서 배웠듯이 코드에서 배열을 생성하면 메모리 내에 연속된 빈 셀 그룹을 찾아 사용자 애플리케이션이 데이터를 저장할 수 있도록 할당한다. 컴퓨터는 어떤 메모리 주소든 한 번에 접근할 수 ..

13장 속도를 높이는 재귀 알고리즘

지금까지 버블 정렬과 선택 정렬, 삽입 정렬 같은 많은 정렬 알고리즘을 살펴봤다. 하지만 실제로 배열을 정렬할 때는 이러한 방법을 쓰지 않는다. 컴퓨터 언어에는 대부분 내장 정렬 함수가 있어 사용자가 스스로 구현하는 데 드는 시간과 노력을 아껴준다. 컴퓨터 언어 중 대다수가 내부적으로 채택한 정렬 알고리즘이 바로 퀵 정렬이다. 퀵 정렬은 매우 빠른 정렬 알고리즘이다. 특히 평균 시나리오에서 효율적이다. 최악의 시나리오 즉, 역순으로 정렬된 배열에서는 삽입 정렬이나 선택 정렬과 성능이 유사하지만 대부분의 경우 일어나는 평균 시나리오에서는 훨씬 빠르다. 퀵 정렬의 동작 방식을 공부하면 재귀를 사용해 어떻게 알고리즘의 속도를 크게 향상시키는지 배울 수 있다. 13.1 분할 배열을 분할한다는 것은, 배열로부터 ..

12장 동적 프로그래밍

지금까지 재귀적으로 작성하는 법과 재귀로 보다 복잡한 문제를 해결하는 법을 배웠지만 재귀로 확실히 어떤 문제는 해결할 수 있어도 제대로 사용하지 않으면 또 다른 문제가 발생한다. 재귀는 종종 O(2ⁿ)같은 가장 느린 빅 오 카테고리의 주된 요인이 된다. 12.1 불필요한 재귀 호출 다음의 재귀 함수는 배열의 최대값을 찾는다. function max(array) { if (array.length === 1) return array[0]; if (array[0] > max(array.slice(1))) { return array[0]; } else { return max(array.slice(1)); } } 만약 배열의 요소가 하나면 그 값이 최대값이 된다. 각 재귀 호출의 핵심은 하나의 수 (array[0..

11장 재귀적으로 작성하는 법

재귀적으로 작성하는 법을 보다 쉽게 익힐 수 있는 기법을 소개한다. 11.1 재귀 카테고리: 반복 실행 반복적으로 한 작업을 실행하는 알고리즘에 재귀 함수를 적용할 수 있다. 이전에 다뤘던 카운트 다운 함수를 예시로 들어보자. function countdown(number) { console.log(number); if (number === 0) { return; } else { countdown(number - 1); } } 반복 실행 카테고리에 속하는 문제들은 함수의 마지막 줄에서 단순히 그 함수를 다시 한 번 호출한다. 위의 예제에선 coundown(number - 1)이다. 11.1.1 재귀 트릭: 추가 인자 넘기기 숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 작성하려고 한다...

10장 재귀를 사용한 재귀적 반복

재귀는 이후 나올 보다 고급 알고리즘을 이해하기 위한 컴퓨터 과학의 핵심 개념이다. 재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어. 10.1 루프 대신 재귀 카운트 다운 함수를 구현하다고 하자 function countdown(number) { for (let i = number; i >= 0; i--) { console.log(i); } } 반복문을 이용해 함수를 구현할 수 있지만, 재귀로 카운트 다운 함수를 구현할 수도 있다. function countdown(number) { console.log(number); countdown(number - 1); } countdown(10)을 호출한다고 가정하면,10을 출력하고, countdown(10) 함수가 끝나기 전에 countdown(9) 함수를..

9장 스택과 큐로 간결한 코드 생성

지금까지 자료 구조를 논할 때는 주로 자료 구조에 따라 다양한 연산의 성능이 어떻게 달라지는가에 초점을 맞췄다. 하지만 프로그래밍 지식 창고에 다양한 자료 구조를 쌓아 두면 보다 간단하고 읽기 쉬운 코드를 생성하는 데 도움이 된다. 스택과 큐는 제약을 갖는 배열이다. 이러한 제약 덕분에 두 자료 구조가 매우 간결해진다. 스택과 큐는 임시 데이터를 처리할 수 있는 간결한 도구다. 다양한 분야에서 사용해 뛰어난 알고리즘을 만들 수 있다. 9.1 스택 스택이 데이터를 저장하는 방법은 배열과 같다. 단순히 원소들의 리스트지만 세 가지 제약이 있다. 데이터는 스택의 끝에만 삽입할 수 있다 데이터는 스택의 끝에서만 삭제할 수 있다 스택의 마지막 원소만 읽을 수 있다 스택의 끝을 위(top), 스택의 시작을 밑(bo..

8장 해시 테이블로 매우 빠른 룩업

8장이 끝날 때까지 데이터를 O(1) 만에 룩업할 수 있는 해시 테이블이라는 특수한 자료 구조의 사용법을 배울 것이다. 8.1 해시 테이블 대부분의 프로그래밍 언어는 해시 테이블이라는 자료 구조를 포함하며, 해시 테이블에는 빠른 읽기라는 놀랍고 엄청난 능력이 있다. 해시, 맵, 해시맵, 딕셔너리, 연관 배열 등의 이름을 갖는다. let menu = new Map([["french fries", 0.75], ["hamburger", 2.5], ["hot dog", 1.5], ["soda", 0.6]]); 해시 테이블은 쌍으로 이뤄진 값들의 리스트다. 첫 번째 항목을 키(key)라 부르고, 두 번째 항목을 값(value)이라 부른다. 자바스크립트에서는 다음과 같은 문법으로 키의 값을 룩업할 수 있다. men..