1. 트라이(Trie)란 무엇인가?트라이는 문자열을 저장하고 탐색하는 데 특화된 트리 기반 자료구조이다.트라이는 문자열의 길이를 $L$이라 할 때, 탐색 및 삽입 연산을 $O(L)$ 시간에 수행할 수 있다.이는 해시 테이블과 유사한 성능을 가지며, 접두사 기반 검색이 자연스럽게 가능하다는 점에서 유리하다. 2. 트라이 구조트라이는 루트 노드에서 시작하여 각 문자마다 분기하는 구조를 가진다.각 노드는 다음과 같은 속성을 가진다:children: 자식 노드를 저장하는 딕셔너리 (dict)is_end: 단어의 끝을 나타내는 불리언 값 (bool) 트라이 구조 예시다음과 같은 단어들을 저장한다고 가정한다:apple, april, bus, busy, beer, best해당 단어들을 삽입한 트라이 구조는 다음과 ..

1. 정의 위상 정렬은 방향 비순환 그래프(DAG)에서 노드를 순서대로 나열하여, 모든 간선 (u → v)에 대해 u가 v보다 먼저 오도록 만드는 알고리즘 위상정렬은 '과목 이수체계도'로 생각하면 이해하기 쉽다 예를 들어 아래와 같은 과목 이수 체계도가 있다고 하자:기초천문학 → 전자기학 → 우주환경 → 우주플라즈마유체역학미분적분학 → 선형대수학 → 미분방정식 → 해석학 또한, 우주플라즈마유체역학을 듣기 위해 다음과 같은 선행 조건 중 하나를 만족해야 한다:기초천문학 → 천체물리학 → 우주플라즈마유체역학또는기초천문학 + 전자기학 + 우주환경 → 우주플라즈마유체역학 한편, 선형대수학은 우주플라즈마유체역학과 직접적인 선후 관계가 없기 때문에 이 정렬 순서 중 어디에 위치해도 정렬 조건을 만족하게 ..

Chapter 3 읽는 방법(챕터 서문)“대충 원리는 알아, 디테일은 생략할래” 식으로 접근하면 안 되고, 디테일을 정확히 익히는 것이 필수다.따라서, 예제를 직접 따라 해보고, 연습문제를 풀어보고, 해답과 비교하면서 학습하는 것이 중요하다추가로, C의 pointer 개념을 알고 있어야 아래 내용을 이해하기 쉽다 3.1 역사적 관점 (생략)3.2 머신 코드Chapter 1에서 간략하게 서술하였듯이, 우리는 사람이 이해할 수 있는 '프로그래밍 언어'를 사용한다. 프로그래밍 언어는 실제, 컴퓨터가 동작하는 세밀하고 복잡한 과정들을 '추상화'하였기 때문에, 컴퓨터가 어떻게 동작하는지를 '제대로' 이해하기 위해서는 3장의 어셈블리 언어를 학습해야하는 것이다 어셈블리 언어란?사람이 이해할 수 있는 '프로그래..

1. 그래프란 무엇인가?그래프(Graph)란 노드(정점, Vertex)들의 집합이며,이 노드들은 간선(Edge)을 통해 서로 연결되어 있다. 그래프는 트리(Tree) 자료구조와 유사하지만, 연결 방식에서 차이가 있는데, 예를 들어, N개의 노드를 가진 트리는 항상 N-1개의 간선을 가지며, 각 간선은 부모-자식 관계를 형성한다.트리에서는 모든 노드가 루트 노드로부터 단 하나의 경로로 연결될 수 있다. 반면, 그래프에서는 노드 간에 정해진 관계(부모-자식)가 없으며, 이로 인해 노드들이 다양한 방식으로 자유롭게 연결될 수 있다. 간선은 2가지 타입으로 나뉘는데, Directed edges는 연결이 한 방향(단방향)인 간선을 의미이때 한쪽 끝점은 출발지, 다른 한쪽 끝점은 도착지Undirected ed..

1. 트리(Tree)란?데이터가 수직적으로 이루어진 비선형 자료구조 트리는 노드(node)들의 집합으로 이루어져있으며, 노드들은 edge로 연결되어있다 각각의 노드들은 데이터를 포함하고 있다. 트리의 첫번째 노드(가장 위)는 루트 노드(root node)라고 지칭하위 노드들은 자식 노드(children node)라고 칭한다 자식 노드가 없는 노드는 리프 노드(leaf nodes) 또는 외부 노드(external nodes)라고 한다.리프 노드가 아닌 노드는 내부 노드(internal nodes)라고 한다.같은 부모를 가진 노드들은 형제 노드(sibling nodes)라고 한다. A는 B와 C의 부모 노드이다B는 A의 자식 노드이다B와 C는 형제 노드 관계이다E,F,H,I 그리고 J는 리프 노드이..

1. Hashing이란?해싱(hashing)은 각각의 데이터를 해시 함수를 통해 '고유한 값(해시값)'으로 변환하는 과정을 의미합니다. 이 해시값은 데이터의 식별자(index)로 사용되어, 데이터 탐색에 활용됩니다해싱 개념을 기반으로 만들어진 자료구조가 바로 해시 테이블(Hash Table)입니다. 2. 해시 함수(Hash Function)해시 함수는 입력값을 고정된 길이의 고유한 값으로 변환하는 함수입니다.예를 들어, "Hello World!"라는 문자열을 해시 함수에 입력하면 다음과 같은 해시값(문자열)이 생성됩니다."Hello World!"의 해시 값 : 2ef7 bde6 08ce 5404 e97d 5f04 2f95 f89f 1c23 2871 만약 입력값 중 한 글자라도 바뀌면, (ex. "H..

1. 우선순위 큐 정의큐는 먼저 들어온 데이터가 먼저 출력됩니다. 반면, 우선순위 큐는 모든 데이터가 우선순위를 가지고 있고, 이로 인해 들어온 순서에 관계 없이 우선순위가 높은 순으로 데이터가 나가는 형태의 자료구조입니다. 우선순위 큐의 특징모든 요소들은 우선순위를 가지고 있어, 요소를 삽입할 때, 우선순위에 따라 정렬됩니다가장 높은 우선순위 요소가 먼저 삭제됩니다힙으로 구현된 자료구조입니다 위 사진과 같은 상황에서 12가 들어온다고 가정해봅시다삽입(enqueue) 시, 가장 높은 우선순위인 12가 배열의 가장 앞쪽에 위치삭제(dequeue) 시, 가장 높은 우선순위인 12가 배열의 앞쪽에 위치해있기 때문에 삭제합니다삭제 후, 자식 요소 중 다음으로 높은 우선순위를 가진 요소가 앞에 위치합니다 우선..

1. 부동 소수점 정의부동 소수점(floating point)이란? 부동(浮動) : 뜰 부(浮)에 움직일 동(動) => 떠서 움직인다 즉, 소수점의 위치가 정해지지 않은 소수를 '부동 소수점'이라고 합니다.컴퓨터가 메모리를 효율적으로 사용하면서, 더 많은 수를 표현하기 위한 방식입니다 2. 고정 소수점 vs 부동 소수점고정 소수점과 부동 소수점은 어떤 차이가 있을까요? 우선, 고정 소수점은 소수점을 기준으로 정수부와 소수부로 나뉩니다 이는 저희가 수학 시간에 배웠던 기본적인 실수 표현 방식이죠 부동소수점은 이와 다르게 가수과 지수로 수를 표현합니다대략적으로 설명하자면, 가수는 수를 나타내는 영역이고, 지수는 수가 얼마나 큰지를 나타냅니다 예를 들어, 위 사진에서 12.345 x 10^1을 1.2345 ..