전체 글

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)이다. 연산이 빠르지만 순서를 유지하지 못하므로 알파벳순으로..

Next.js를 사용하는 이유

Framework vs Library React는 라이브러리이고, Next는 React의 프레임워크이다. 이 둘의 궁극적인 차이점은 “응용 프로그램의 흐름 주도권을 누가 가지고 있느냐" 이다. 여기서 프레임워크란? 원하는 기능 구현에 집중하여 개발할 수 있도록 일정한 형태와 필요한 기능을 갖추고 있는 골격 즉, 뼈대를 의미한다. 사용자는 코드를 작성하여 애플리케이션을 개발한다. 여기서 앱/서버 등의 구동, 메모리 관리, 이벤트 루프 등의 공통된 부분을 프레임워크가 관리한다. 라이브러리란? 컴퓨터 프로그램이 사용하는 비휘발성 자원의 모임. 즉, 특정 기능을 모아둔 코드 혹은 함수들의 집합이며 코드 작성 시 활용 가능한 도구들을 의미한다. Next.js SSR을 쉽게 구현하도록 도와주는 프레임워크 Next...

14장 노드 기반 자료 구조

다양한 자료 구조는 모두 노드라는 개념에 기반해 만들어졌다. 노드란 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각이다. 노드 기반 자료 구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하는데 성능상 큰 이점이 많다. 14장에서는 가장 간단한 노드 기반 자료 구조이자 이후 배울 내용의 기반인 연결 리스트 살펴본다. 14.1 연결 리스트 연결 리스트 (Linked List)는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 배열과 연결 리스트는 외견상 상당히 비슷한 모습으로 동작하지만 내부적으로는 크게 다르다. 앞서 배웠듯이 코드에서 배열을 생성하면 메모리 내에 연속된 빈 셀 그룹을 찾아 사용자 애플리케이션이 데이터를 저장할 수 있도록 할당한다. 컴퓨터는 어떤 메모리 주소든 한 번에 접근할 수 ..