데이터를 정렬하고 싶을 수 있다. 퀵 정렬 같은 정렬 알고리즘으로 데이터를 정리할 수 있지만 O(NlogN)이라는 시간이 필요하다. 따라서 데이터를 자주 정렬해야 한다면 애초에 데이터를 항상 정렬된 순서로 유지하는 편이 합리적이다. 정렬된 배열은 읽기 O(1), 검색 O(logN), 삽입 O(N), 삭제 O(N)이다. 순서를 유지하면서도 빠른 검색과 삽입, 삭제가 가능한 자료 구조가 필요하면 어떻게 해야 할까? 정렬된 배열도 해시 테이블도 완벽하지 않다. 이진 탐색 트리를 보자. 1. 트리 트리(tree)는 노드 기반 자료 구조이며, 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다. 가장 상위에 위치한 노드를 루트라고 부른다. 루트는 트리의 꼭대기다. 노드는 부모와 자식 노드가 있을 수 있다. 패..
이 챕터에서는 “재귀적으로 작성하는” 법을 쉽게 익힐 수 있는 몇 가지 비법을 배우게 된다. 11장에서는 재귀의 효율성은 논하지 않는다. 사실 재귀는 알고리즘의 시간 복잡도에 몹시 부정적인 영향을 미친다. 1. 재귀 카테고리: 반복 실행 가장 쉬운 카테고리로, 반복적으로 한 작업을 실행하는 알고리즘이다. 10장에서 잠깐 훑어본 디렉토리 출력 알고리즘 역시 반복 실행 카테고리의 한 예다. 1.1 재귀 트릭: 추가 인자 넘기기 숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 수행하려고 한다. 단 새 배열을 만드는 것이 아니라 배열 자체에서 수정하겠다. 제자리(in-place) 수정 데이터를 조작(변경)하는 기본적인 방식은 일반적으로 두 가지다. 첫 번째 방법은 원래 배열은 그대로 두고 “두 ..
재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어다. 1. 루프 대신 재귀 루프를 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다. 재귀를 쓸 수 있다고 해서 무조건 재귀를 써야 한다는 것은 아니다. 재귀는 명쾌한 코드를 작성할 수 있는 하나의 도구다. 2. 기저 조건 기저 조건(base case): 함수가 반복되지 않는 경우 모든 재귀 함수에는 함수가 무한대로 호출되지 않게 하는 기저 조건이 적어도 하나 있어야 한다. 3. 재귀 코드 읽기 재귀 코드를 읽는 방법 기저 조건을 찾는다. 기저 조건에서 함수가 어떻게 동작하는지 살펴본다. “끝에서 두 번째” 조건을 찾는다. 곧 보이겠지만 이는 기저 조건 바로 전 조건이다. “끝에서 두 번째” 조건에서 함수가 어떻게 동작하는지 살펴본다. 방금 분석한..
9장에서는 스택과 큐를 알아본다. 스택과 큐는 임시 데이터를 처리할 수 있는 간결한 도구다. 운영 체제 아키텍처부터 출력, 데이터 순회에 이르기까지 스택과 큐를 임시 컨테이너로 활용하여 뛰어난 알고리즘을 만들 수 있다. 1. 스택 스택이 데이터를 저장하는 방법은 배열과 같다. 즉, 원소들의 리스트다. 스택에는 다음과 같은 제약이 있다. 데이터는 스택의 끝에만 삽입할 수 있다. 데이터는 스택의 끝에서만 삭제할 수 있다. 스택의 마지막 원소만 읽을 수 있다. 접시 더미를 쌓아올린 것처럼 생각해도 좋다. 스택의 끝(삽입, 삭제, 읽기 가능)을 top, 밑을 bottom이라고 한다. 스택에 새 값을 삽입하는 것을 스택에 푸시한다고도 말한다. 스택의 끝에서 원소를 제거하는 것을 pop이라고 한다. LIFO - L..
✍🏻 누자알 앞부분은 기본 내용이고, 다시 공부할 필요가 없다고 생각했다. 그래서 정리에 조금 소홀함이 있었다. 그러나 최근 쳤던 코딩 테스트에서 CS 지식 중 선택 정렬과 버블 정렬에 대해 물어보는 문제가 나왔다. 와! 마침 누자알 4장과 5장이 버블 정렬과 선택 정렬에 대해 자세하게 설명하고 있어서 해당 문제를 맞출 수 있었다. 역시 공부는 기본이 중요하다는 것을 다시 깨달았다. 기록하지 않으면 까먹을 것 같아서 느슨해지지 말자는 다짐으로 여기 기록한다. 배열이 정렬되어 있지 않다면 컴퓨터는 선형 검색을 해야 하므로 특정 값이 배열 내에 존재하는지 검색하기 위해 O(N)의 수행 단계가 필요하다. 정렬된 배열이라면 컴퓨터가 이진 검색을 수행할 수 있으므로 O(log N)의 수행 단계가 필요하다. 그러나..
