Algorithm
-
자료구조와 알고리즘, Tree, Binary Search TreeData Structure & Algorithm 2024. 6. 26. 21:25
이진 탐색 트리(Binary Search Tree, BST)는 데이터의 효율적인 저장, 검색, 삽입 및 삭제를 위해 사용되는 트리 구조입니다. 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 큽니다. 이러한 특성 덕분에 이진 탐색 트리는 정렬된 데이터를 효율적으로 처리할 수 있습니다.이진 탐색 트리의 특성모든 노드의 값은 유일합니다.왼쪽 서브트리의 모든 노드 값은 부모 노드 값보다 작습니다.오른쪽 서브트리의 모든 노드 값은 부모 노드 값보다 큽니다.왼쪽 및 오른쪽 서브트리도 각각 이진 탐색 트리입니다.주요 연산삽입 (Insert): 새로운 값을 올바른 위치에 추가합니다.검색 (Search): 특정 값이 트리에 존..
-
자료구조와 알고리즘, QueueData Structure & Algorithm 2024. 6. 25. 21:12
큐(Queue)는 자료 구조의 한 형태로, 선입선출(FIFO, First In First Out) 원칙을 따릅니다. 즉, 먼저 삽입된 데이터가 먼저 삭제됩니다. 큐는 일상 생활의 줄 서기와 유사합니다. 예를 들어, 사람들이 줄을 서서 대기하는 경우, 줄의 맨 앞에 있는 사람이 가장 먼저 서비스받고 줄에서 나가며, 새로운 사람은 줄의 맨 뒤에 서게 됩니다.큐의 기본 연산enqueue: 큐의 맨 뒤에 요소를 추가합니다.dequeue: 큐의 맨 앞에서 요소를 제거하고 반환합니다.peek/front: 큐의 맨 앞 요소를 반환하지만, 제거하지는 않습니다.isEmpty: 큐가 비어 있는지 확인합니다.size: 큐의 요소 개수를 반환합니다.큐의 활용 사례운영 체제: 작업 스케줄링 및 프로세스 관리에서 사용됩니다.프린..
-
자료구조와 알고리즘, StackData Structure & Algorithm 2024. 6. 25. 21:11
스택(Stack)은 후입선출(LIFO, Last In First Out) 원칙에 따라 데이터를 관리하는 자료 구조입니다. 이는 마지막에 삽입된 데이터가 가장 먼저 제거되는 구조를 의미합니다. 스택은 주로 재귀 알고리즘, 언어의 함수 호출, 실행 취소 기능 등에서 많이 사용됩니다.주요 연산push: 스택의 맨 위에 데이터를 추가합니다.pop: 스택의 맨 위에 있는 데이터를 제거하고 반환합니다.peek (또는 top): 스택의 맨 위에 있는 데이터를 반환하지만 제거하지는 않습니다.isEmpty: 스택이 비어 있는지 확인합니다.size: 스택에 있는 데이터의 개수를 반환합니다.스택의 특징LIFO: 마지막에 삽입된 데이터가 가장 먼저 제거됩니다.제한된 접근: 스택은 오직 한쪽 끝에서만 데이터의 삽입과 제거가 가..
-
자료구조와 알고리즘, 링크드 리스트, Double Linked ListData Structure & Algorithm 2024. 6. 23. 16:47
더블 링크드 리스트(Doubly Linked List)는 각 노드가 두 개의 포인터를 가지는 링크드 리스트입니다. 하나는 다음 노드를 가리키고, 다른 하나는 이전 노드를 가리킵니다. 이를 통해 리스트의 양방향 탐색이 가능해집니다.주요 특징노드 구조(Node Structure): 각 노드는 data, next, prev 세 가지 속성을 가집니다.data: 노드가 저장하는 데이터next: 다음 노드를 가리키는 포인터prev: 이전 노드를 가리키는 포인터리스트의 구조(List Structure): 더블 링크드 리스트는 head와 tail 두 개의 포인터를 가집니다.head: 리스트의 첫 번째 노드를 가리킴tail: 리스트의 마지막 노드를 가리킴양방향 탐색: 양방향으로 탐색이 가능하여, 앞뒤로 이동하며 데이터를..
-
자료구조와 알고리즘, 링크드 리스트, Single Linked ListData Structure & Algorithm 2024. 6. 20. 17:41
JavaScript에서 링크드 리스트(Linked List)는 노드(Node)들이 포인터로 연결된 데이터 구조로, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다. 링크드 리스트는 배열(Array)과 비교했을 때 몇 가지 주요 차이점이 있습니다.기본 개념노드(Node): 링크드 리스트의 각 요소는 노드라고 불리며, 데이터와 다음 노드를 가리키는 포인터를 포함합니다.헤드(Head): 링크드 리스트의 시작 노드를 가리킵니다.테일(Tail): 링크드 리스트의 마지막 노드를 가리킵니다.포인터(Next): 각 노드는 다음 노드를 가리키는 포인터를 포함합니다.링크드 리스트의 구조링크드 리스트는 주로 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked Lis..
-
알고리즘, Sort, Radix SortData Structure & Algorithm 2024. 6. 18. 17:54
Radix Sort(기수 정렬)은 정수나 문자열의 자릿수를 기준으로 정렬하는 효율적인 정수 정렬 알고리즘입니다. 이 알고리즘은 주로 양의 정수나 고정 길이의 문자열을 정렬하는 데 사용되며, 시간 복잡도가 O(d * (n + k))로, 비교 기반 정렬 알고리즘보다 더 효율적일 수 있습니다. 여기서 d는 데이터의 최대 자릿수, n은 요소의 수, k는 기수(예: 10진법에서는 10)입니다.기본 개념기수 정렬은 LSD(Least Significant Digit)와 MSD(Most Significant Digit) 두 가지 방법으로 나뉩니다:LSD 방식: 가장 작은 자릿수부터 시작하여 큰 자릿수 방향으로 정렬합니다.MSD 방식: 가장 큰 자릿수부터 시작하여 작은 자릿수 방향으로 정렬합니다.LSD 방식은 일반적으로..
-
알고리즘, Sort, Quick SortData Structure & Algorithm 2024. 6. 18. 17:47
퀵 정렬(Quick Sort)은 Divide and Conquer 기법을 사용하는 매우 효율적인 정렬 알고리즘입니다. 평균적으로 매우 빠른 시간 복잡도인 O(n log n)을 가지며, 제자리 정렬(In-place Sort) 알고리즘입니다. 퀵 정렬은 리스트에서 피벗(pivot) 요소를 선택하고, 이를 기준으로 리스트를 두 개의 하위 리스트로 나누는 과정을 반복하여 정렬합니다.기본 개념퀵 정렬의 기본 개념은 다음과 같습니다:피벗 선택: 리스트에서 피벗 요소를 선택합니다.분할: 피벗을 기준으로 리스트를 두 개의 하위 리스트로 분할합니다. 피벗보다 작은 요소들은 피벗의 왼쪽으로, 피벗보다 큰 요소들은 피벗의 오른쪽으로 이동합니다.재귀 호출: 분할된 하위 리스트에 대해 퀵 정렬을 재귀적으로 호출합니다.결합: 하..
-
알고리즘, Sort, Merge SortData Structure & Algorithm 2024. 6. 18. 17:38
병합 정렬(Merge Sort)은 Divide and Conquer 기법을 사용하는 효율적인 정렬 알고리즘입니다. 병합 정렬은 리스트를 반으로 나누어 각각을 재귀적으로 정렬하고, 정렬된 부분 리스트를 합쳐서 전체 리스트를 정렬합니다. 이 알고리즘은 안정적이고, 시간 복잡도가 O(n log n)으로 매우 효율적입니다.기본 개념병합 정렬의 기본 개념은 다음과 같습니다:분할(Divide): 리스트를 두 개의 하위 리스트로 나눕니다.정복(Conquer): 하위 리스트를 재귀적으로 병합 정렬합니다.결합(Combine): 두 개의 정렬된 하위 리스트를 하나의 정렬된 리스트로 병합합니다.예제다음은 자바스크립트로 구현한 병합 정렬의 예제입니다.function merge(arr1, arr2) { let idx1 = 0..