Grit

Chapter 1. Preliminaries: Statistical and Causal Models하단의 목차를 클릭하여 이동할 수 있습니다 :)1. Simson's Paradox        1-1. 인과추론2. Probability and Statistics        2-1. Variables        2-2. Events        2-3. Conditional Probability        2-4. Independence        2-5. Probability Distributions1. Simson's ParadoxSimson's Paradox란 전체 집단(entire population)이 갖는 통계적 관계가 하위 집단(subpopulation)에서 역전되는 데이터를 의미한다...

Chapter 20. 코드 최적화 기법하단의 목차를 클릭하여 이동할 수 있습니다 :)1. 전제 조건: 현재 빅 오 파악하기2. 시작점: 상상할 수 있는 최상의 빅 오3. 룩업 마법        3-1. 저자와 도서 찾기        3-2. 두 수의 합(two-sum) 문제4. 패턴 인식        4-1. 동전 게임        4-2. 합 교환(sum swap) 문제5. 탐욕 알고리즘        5-1. 배열 최댓값        5-2. 최대 부분합        5-3. 탐욕스러운 주가 예측6. 자료 구조 변경        6-1. 애너그램 생성기        6-2. 그룹 정렬7. 연습 문제 정리1. 전제 조건: 현재 빅 오 파악하기최적화의 전제 조건(prerequisite)은 현재 코드의 효율..

Chapter 19. 공간 제약 다루기하단의 목차를 클릭하여 이동할 수 있습니다 :)1. 공간 복잡도의 빅 오2. 시간과 공간 트레이드오프3. 재귀에 숨겨진 비용4. 연습 문제 정리공간 복잡도(space complexity)란 알고리즘이 얼마나 많은 메모리를 소모하는지를 의미한다.1. 공간 복잡도의 빅 오공간 복잡도 또한 빅 오로 표기한다.공간 복잡도의 핵심 질문은 "데이터 원소가 N개일 때 알고리즘은 메모리 단위를 얼마나 소모할까?" 이다.공간 복잡도는 추가로 소모되는 메모리만을 고려한다.추가로 소모되는 공간은 보조 공간(auxiliary space)이라 한다.다른 책에서는 원래 입력까지 포함하는 경우도 있다.2. 시간과 공간 트레이드오프공간 복잡도와 시간 복잡도 중 어느 것을 우선시할 것인지는 주어진..

Chapter 18. 그래프로 뭐든지 연결하기하단의 목차를 클릭하여 이동할 수 있습니다 :)1. 그래프        1-1. 그래프 대 트리        1-2. 그래프 용어        1-3. 기초 그래프 구현        1-4. 방향 그래프 (Directed graph)        1-5. 객체 지향 그래프 구현2. 그래프 탐색        2-1. 깊이 우선 탐색 (Depth-First Search, DFS)        2-2. 너비 우선 탐색 (Breadth-First Search, BFS)        2-3. 깊이 우선 탐색 vs 너비 우선 탐색3. 가중 그래프4. 최단 경로 문제        4-1. 데이크스트라의 알고리즘 (p442)5. 연습 문제 정리그래프(graph)는 관계에 특..

Chapter 17. 트라이(trie)해 보는 것도 나쁘지 않다하단의 목차를 클릭하여 이동할 수 있습니다 :)1. 트라이 노드2. 단어 저장3. 트라이 검색       3-1. 트라이 검색의 효율성4. 트라이 삽입5. 자동 완성 개발       5-1. 단어 수집       5-2. 자동 완성 마무리6. 연습 문제 정리트라이(tire)는 자동 완성과 자동 수정 등의 기능을 구현할 때 사용하기 좋다.트라이의 어원은 retrieval 이다. 따라서 '트리'라고 발음하는 것이 맞다. 그러나 기존의 트리 자료 구조와 차이를 두기 위해 트라이라 칭한다.트라이는 교재마다 설명이 조금씩 상이할 수 있다. 그러나 기본적인 개념은 동일하다.1. 트라이 노드트라이 또한 노드를 기반으로한 자료 구조 이다.트라이는 자식 노드..

Chapter 16. 힙으로 우선순위 유지하기하단의 목차를 클릭하여 이동할 수 있습니다 :)1. 우선순위 큐2. 힙3. 힙 속성 (최대 힙)        3-1. 삽입        3-2. 삭제        3-3. 힙 vs 정렬된 배열4. 마지막 노드 문제        4-1. 배열 기반 힙 순회        4-2. 힙 삽입 코드        4-3. 힙 삭제 코드5. 우선순위 큐로 쓰이는 힙6. 연습 문제 정리        6-1. 3 번 (힙 정렬)힙은 데이터 세트에서 가장 큰 또는 가장 작은 데이터 원소를 계속 알아내야 할 때 특히 유용하다.1. 우선순위 큐우선순위 큐(priority queue)의 삭제와 접근은 전형적인 큐와 유사하다. 그러나 삽입은 정렬된 배열과 유사한 리스트이다.삭제 & 접..

Chapter 15. 이진 탐색 트리로 속도 향상하단의 목차를 클릭하여 이동할 수 있습니다 :)1. 트리2. 이진 탬색 트리        2-1. 검색        2-2. 삽입        2-3. 삭제3. 이진 탐색 트리 다뤄보기4. 이진 탐색 트리 순회이진 탐색 트리는 순서를 유지하면서도 빠른 검색, 삽입, 그리고 삭제가 가능한 자료 구조이다.1. 트리트리(tree)는 노드를 기반으로한 자료 구조이다.단, 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다는 차이가 있다.트리 용어 정리루트(root) : 트리의 최상위 노드부모(parent) : 노드의 바로 상위 노드. (노드가 속한 노드).자식 : 노드의 바로 하위 노드.자손(descendant) : 노드에 속하는 모든 하위 노드. (자식 노드..

Chapter 14. 노드 기반 자료 구조하단의 목차를 클릭하여 이동할 수 있습니다 :)1. 연결 리스트2. 연결 리스트 구현 (python)        2-1. 읽기        2-2. 검색        2-3. 삽입        2-4. 삭제        2-5. 연결 리스트의 연산의 효율성3. 이중 연결 리스트4. 이중 연결 리스트 기반 큐5. 연습 문제 정리6. 이쯤에서 전체 복습노드란 자료 구조의 일종으로 컴퓨터 메모리 곳곳에 흩어져 있는 자료 구조를 의미한다.1. 연결 리스트연결 리스트(linked list)란 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조이다.연결 리스트는 컴퓨터 메모리 전체에 걸쳐 데이터가 분산 저장되어 있다. 즉, 배열처럼 연속된 메모리 블록에 데이터가 저장되지..

Chapter 13. 속도를 높이는 재귀 알고리즘하단의 목차를 클릭하여 이동할 수 있습니다 :)1. 분할2. 퀵 정렬3. 퀵 정렬의 효율성4. 퀵 셀렉트5. 다른 알고리즘의 핵심 역할을 하는 정렬6. 연습 문제 정리대부분의 컴퓨터 언어는 퀵 정렬(Quicksort)을 내장 정렬 함수로 사용한다. 버블 정렬, 선택 정렬, 삽입 정렬 등 많은 알고리즘을 배웠으나 실질적으로 배열 정렬에는 사용하지 않는다.퀵 정렬이 내장 정렬 함수로 사용되는 이유는 퀵 정렬의 평균 빅 오가 가장 효율적인 시간 복잡도이기 때문이다.최악의 경우에 해당하는 빅 오는 삽입 정렬, 그리고 선택 정렬과 유사하다.퀵 정렬은 분할(partitioning)이라는 개념에 기반한다.1. 분할분할은 일종의 정렬방식이다.분할은 첫 번째로 배열 내에서..

Chapter 12. 동적 프로그래밍하단의 목차를 클릭하여 이동할 수 있습니다 :)1. 재귀 요약2. 하위 문제 중첩3. 동적 프로그래밍의 두 가지 방식        3-1. 메모이제이션 (memoization)        3-2. 상향식4. 요약 정리5. 연습 문제 정리재귀는 효율적이지만 느린 빅 오 카테고리이다.재귀의 느리다는 문제는 동적 프로그래밍으로 완화할 수 있다.1. 재귀 요약함수 내에서 두 번 함수를 호출하는 재귀는 매우 느린 알고리즘이다. 따라서 가능한 경우 불필요한 함수의 호출을 제거해야 한다.간단하게 불필요한 호출을 제거한느 방법 중 하나는 호출의 결과를 변수에 저장한 뒤, 다음 호출에 해당 변수의 값을 사용하는 방법이 있다.2. 하위 문제 중첩변수에 호출 값을 저장하는 방법은 변수에..