'🗒️ 책 & 강의 정리' 카테고리의 글 목록 (2 Page)

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

2022.12.26

데이터를 정렬하고 싶을 수 있다. 퀵 정렬 같은 정렬 알고리즘으로 데이터를 정리할 수 있지만 O(NlogN)이라는 시간이 필요하다. 따라서 데이터를 자주 정렬해야 한다면 애초에 데이터를 항상 정렬된 순서로 유지하는 편이 합리적이다. 정렬된 배열은 읽기 O(1), 검색 O(logN), 삽입 O(N), 삭제 O(N)이다. 순서를 유지하면서도 빠른 검색과 삽입, 삭제가 가능한 자료 구조가 필요하면 어떻게 해야 할까? 정렬된 배열도 해시 테이블도 완벽하지 않다. 이진 탐색 트리를 보자. 1. 트리 트리(tree)는 노드 기반 자료 구조이며, 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다. 가장 상위에 위치한 노드를 루트라고 부른다. 루트는 트리의 꼭대기다. 노드는 부모와 자식 노드가 있을 수 있다. 패..

🗒️ 책 & 강의 정리/🏗️ 누구나 자료구조와 알고리즘

14장 노드 기반 자료구조

2022.12.09

노드Node: 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각 노드 기반 자료구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하는데 성능상 큰 이점이 많다. 14장에서는 가장 간단한 노드 기반 자료구조인 연결 리스트를 살펴본다. 1. 연결 리스트 연결 리스트Linked List는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 컴퓨터에 들어 있는 메모리는 데이터조각을 저장하는 셀들의 거대한 집합으로 나타낼 수 있다. 코드에서 배열을 생성하면 메모리 내에 연속된 빈 셀 그룹을 찾아 데이터를 저장할 수 있도록 할당한다. 컴퓨터는 어떤 메모리 주소든 한 번에 접근할 수 있으므로 배열 내 어떤 인덱스든 바로 갈 수 있다. 그러나 연결 리스트 내 데이터는 연속된 메모리 블록이 아니라 컴퓨터 메모리 전체..

🗒️ 책 & 강의 정리/🏗️ 누구나 자료구조와 알고리즘

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

2022.12.08

컴퓨터 언어에는 대부분 내장 정렬 함수가 있어 사용자가 스스로 구현하는 데 드는 시간과 노력을 아껴준다. 컴퓨터 언어 중 대다수가 내부적으로 채택한 정렬 알고리즘은 퀵 정렬(quick sort)이다. 퀵 정렬은 재귀를 사용한 알고리즘으로, 그 동작 방식을 알아보며 재귀를 사용해 어떻게 알고리즘의 속도를 향상시키는지 배울 수 있다. 퀵 정렬은 매우 빠른 정렬 알고리즘으로 특히 평균 시나리오에서 매우 효율적이다. 최악의 시나리오(역순 정렬된 배열)에서는 삽입 정렬이나 선택 정렬과 성능이 유사하나 대부분의 경우에서는 훨씬 빠르다. 퀵 정렬은 분할(partitioning)이라는 개념에 기반한다. 1. 분할 배열을 분할한다는 것은 배열로부터 임의의 수, 즉 피벗을 가져와 피벗보다 작은 수는 피벗의 왼쪽에, 큰 수..

🗒️ 책 & 강의 정리/🏗️ 누구나 자료구조와 알고리즘

12장 동적 프로그래밍

2022.12.08

11장에서는 재귀적으로 작성하는 법과 재귀로 보다 복잡한 문제를 해결하는 법을 배웠다. 그러나 재귀로 어떤 문제를 해결할 수는 있어도 제대로 사용하지 않으면 또 다른 문제가 발생하기도 한다. 재귀를 잘못 사용할 경우 알고리즘의 시간 복잡도가 O(2^N)과 같은 가장 느린 빅 오 카테고리에 속하게 될 수 있다. 12장에서는 재귀의 속도를 느리게 만드는 가장 흔한 걸림돌을 찾고 그러한 알고리즘을 빅 오 관점에서 어떻게 나타내는지, 어떻게 개선하는지를 배운다. 1. 불필요한 재귀 호출 동일한 하위 문제의 계산 결과를 여러 번 호출하는데, 동일한 인자를 넣었을 때 항상 동일한 결과가 나올 때 2. 빅 오를 위한 작은 개선 이러한 추가적인 재귀 호출을 전부 없앨 수 있는 방법이 있다. 코드에서 결과를 변수에 저장..

🗒️ 책 & 강의 정리/🏗️ 누구나 자료구조와 알고리즘

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

2022.12.07

이 챕터에서는 “재귀적으로 작성하는” 법을 쉽게 익힐 수 있는 몇 가지 비법을 배우게 된다. 11장에서는 재귀의 효율성은 논하지 않는다. 사실 재귀는 알고리즘의 시간 복잡도에 몹시 부정적인 영향을 미친다. 1. 재귀 카테고리: 반복 실행 가장 쉬운 카테고리로, 반복적으로 한 작업을 실행하는 알고리즘이다. 10장에서 잠깐 훑어본 디렉토리 출력 알고리즘 역시 반복 실행 카테고리의 한 예다. 1.1 재귀 트릭: 추가 인자 넘기기 숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 수행하려고 한다. 단 새 배열을 만드는 것이 아니라 배열 자체에서 수정하겠다. 제자리(in-place) 수정 데이터를 조작(변경)하는 기본적인 방식은 일반적으로 두 가지다. 첫 번째 방법은 원래 배열은 그대로 두고 “두 ..

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

14장 노드 기반 자료구조

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

12장 동적 프로그래밍

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

티스토리툴바