Books/누구나 자료구조와 알고리즘

20장 코드 최적화 기법

마지막 장에서는 코드 최적화 기법 몇 가지를 소개한다. 다음의 사고 전력 (mental strategy)은 지난 몇 년간 코드를 더 효율적으로 바꾸는 데 큰 역활을 했다. 20.1 전제 조건: 현재 빅 오 파악하기 최적화 기법으로 들어가기 전에 알고리즘 최적화에 앞서 반드시 해야 할 일은 현재 코드의 효율성을 파악하는 것이다. 즉, 현재 얼마나 빠른지 알아야 알고리즘을 더 빠르게 만들 수 있기 때문이다. 20.2 시작점: 상상할 수 있는 최상의 빅 오 “상상할 수 있는 최상의 빅 오”(가능한 최상의 실행 시간)를 생각하는 것은 모든 알고리즘에 유용하며, 반드시 최적화 프로세스의 첫 단계여야 한다. 배열의 각 항목을 출력하는 함수라면 항목 N개를 각각 처리해야 하므로 최상의 빅 오는 O(N)이다. 알고리즘..

19장 공간 제약 다루기

알고리즘의 효율성 척도에는 알고리즘이 얼마나 빠른지 시간 복잡도만 있는게 아니라 공간 복잡도 또한 존재한다. 즉, 알고리즘이 얼마나 많은 메모리를 소모하는가가 유용할 수 있다. 메모리 제한이 있다면 공간 복잡도가 중요한 요인이다. 대량의 데이터를 다루거나 메모리가 제한된 작은 장치를 프로그래밍할 때는 정말 중요하다. 19.1 공간 복잡도의 빅 오 시간 복잡도를 표현할 때와 마찬가지로 빅 오 표기법을 사용해 공간 복잡도를 표현한다. 공간 복잡도, 메모리 소모 관점에서 핵심 질문은 **“데이터 원소가 N개일 때 알고리즘은 메모리 단위를 얼마나 소모할까?”**이다 function makeUpperCase(array) { let newArray = []; for(let i = 0; i < array.length..

18장 그래프로 뭐든지 연결하기

페이스북 혹은 인스타 같은 소셜 네트워크에서 친구 관계는 상호적이다. 이를 구현하기 위해 2차원 배열을 사용한다면 특정 유저의 친구를 찾기 위해 목록 내 관계를 일일히 확인해야 하고, 이는 O(N)이 걸리는 매우 느린 방법이다. 이때 그래프라는 자료 구조를 사용하면 O(1) 시간 만에 찾을 수 있다. 18.1 그래프 그래프는 관계에 특화된 자료 구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다. 소셜 네트워크의 예시에선 한 사람은 한 노드로, 사람 간 친구 관계는 선으로 표현한다. 18.1.1 그래프 대 트리 트리도 그래프의 한 종류다. 두 자료 구조 모두 서로 연결되는 노드로 구성된다. 모든 트리는 그래프지만, 그래프가 모든 트리는 아니다. 트리로 규정되는 그래프는 사이클이 있을 수 없으며,..

17장 트라이(trie)해 보는 것도 나쁘지 않다

스마트폰의 자동 완성 기능이 어떻게 동작하는가? 단어들 모두를 배열에 저장했다면 O(N)으로 느릴 것이고, 해시 테이블은 단어를 통째로 해싱해서 키로 삼아야 하므로 사용할 수 없다. 정렬된 배열을 사용한다면 O(logN)로 빨라질 것이다. 하지만 특수한 트리 기반 자료 구조를 사용하면 O(1)의 속도로 원하는 단어에 접근할 수 있다. 트라이는 자동 완성이나 자동 수정 같은 중요한 기능을 지원한다. 17.1 트라이 트리의 한 종류인 트라이는 자동 완성 같은 텍스트 기반 기능에 이상적이다. 트라이는 추출을 뜻하는 retrieval에서 왔으니 트리로 발음해야 옳지만, 트리라는 발음이 모든 트리 기반 자료 구조에 보편적으로 쓰이므로 혼동을 막고자 트라이라고 발음한다. 17.1.1 트라이 노드 대부분의 트리처럼 ..

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

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

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

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

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 재귀 트릭: 추가 인자 넘기기 숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 작성하려고 한다...