전체 글

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..