728x90 알고리즘10 [알고리즘] 그래프: 이해와 활용하는 자료구조 그래프는 현대의 정보 시대에서 다양한 분야에서 활발히 사용되는 중요한 자료구조입니다. 이 글에서는 그래프의 기본 개념과 그래프를 활용하는 방법에 대해 알아보겠습니다. 또한, 이를 통해 다양한 분야에서 그래프가 어떻게 활용되는지에 대해 살펴보겠습니다.그래프의 기본 개념그래프는 노드(정점)와 간선(엣지)으로 이루어진 자료구조입니다. 이 노드들은 서로 연결되어 있으며, 이 연결 관계가 그래프의 핵심입니다. 무방향 그래프는 간선에 방향이 없는 경우이며, 양쪽으로 이동할 수 있습니다. 반면에 유향 그래프는 간선에 방향이 있는 경우로, 한 방향으로만 이동할 수 있습니다.Adjacency정점을 연결하는 모서리가 있는 경우 정점이 다른정점과 인접하다고 함Path(경로)정점 A에서 정점 B로 이동할 수 있는 일련의 가장.. 2024. 5. 7. [알고리즘] 레드-블랙 트리: 이진 탐색 트리에 균형을 더한 자료구조 JS로 레드 블랙트리 구현하기 레드-블랙 트리는 이진 탐색 트리에 균형을 더한 자료구조입니다. 이 트리는 각 노드가 블랙 또는 레드의 색을 가지며, 몇 가지 규칙에 따라 구성됩니다. 이 규칙들은 트리가 균형을 유지하도록 하며, 검색, 삽입, 삭제 등의 연산에서 최악의 경우 시간 복잡도를 O(log n)에 유지할 수 있도록 합니다. 레드-블랙 트리의 규칙1. 노드 색깔각 노드는 블랙 또는 레드의 색깔을 가집니다.2. 루트 노드루트 노드는 무조건 블랙입니다.3. 새로운 추가 노드새로운 추가 노드는 레드로 추가됩니다.4. 연속된 레드 노드연속된 레드 노드가 올 수 없습니다. 즉, 부모-자식 간에 레드-레드 연결이 발생할 수 없습니다.5. 자식 노드레드 노드의 자식은 모두 블랙입니다.6. 블랙 노드 수루트에서 리프(leaf) 노드까지의 경로.. 2024. 5. 6. [알고리즘] 트라이(Trie) 자료구조: 문자열 검색의 효율적인 해결책 문자열 검색은 컴퓨터 과학에서 중요한 문제 중 하나입니다. 특히, 대용량의 텍스트 데이터베이스나 자연어 처리 시스템에서 문자열을 효율적으로 찾아야 할 때 매우 중요한 역할을 합니다. 이를 위해 다양한 자료구조가 고안되었는데, 그 중에서도 트라이(Trie)는 문자열 검색을 위한 효율적인 해결책으로 널리 사용되고 있습니다. 이번 글에서는 트라이의 원리와 구현, 그리고 실제 응용 사례에 대해 알아보겠습니다.트라이(Trie)란?트라이는 검색 트리의 일종으로, 일련의 문자열을 저장하고 탐색하는 데 사용됩니다. 트라이는 각 문자열을 공통된 접두사(prefix)를 기준으로 묶어서 트리 구조로 나타냅니다. 이를 통해 문자열의 검색이 매우 빠르게 이루어지며, 시간 복잡도는 입력 문자열의 길이에 선형적으로 비례합니다. 즉.. 2024. 5. 5. [알고리즘] 우선순위 큐를 이진힙(Heap)으로 구현하기 우선순위 큐(Priority Queue)는 각 요소가 우선순위 값과 연관되어 있는 특별한 유형의 대기열입니다. 이것은 FIFO(First-In-First-Out) 대기열과는 다르게, 요소들이 우선순위에 따라 처리됩니다. 즉, 높은 우선순위를 갖는 요소가 낮은 우선순위를 갖는 요소보다 먼저 처리됩니다. 이것은 일상생활에서 VIP가 다른 사람들보다 먼저 서비스를 받는 것과 유사합니다. 우선순위 큐를 구현할 때, 이진힙(Heap) 자료구조를 사용하는 것이 일반적입니다. 이진힙은 완전이진트리(Complete Binary Tree)로서, 부모 노드의 값이 자식 노드의 값보다 항상 크거나 작은 성질을 가집니다. 이를 통해 우선순위 큐의 삽입(insert)과 삭제(delete) 연산을 O(logn)의 시간 복잡도로 .. 2024. 5. 3. [알고리즘] 힙 데이터 구조: Complete Binary Tree와 우선순위 큐의 핵심 힙(Heap)은 컴퓨터 과학에서 널리 사용되는 중요한 데이터 구조 중 하나입니다. 이번 글에서는 힙이 무엇인지, 어떻게 구성되는지, 그리고 어떻게 활용되는지에 대해 알아보겠습니다. 특히, 힙이 Complete Binary Tree(완전 이진 트리)라는 속성을 가지고 있으며, 우선순위 큐(priority queue)를 구현하는 데 사용된다는 점을 강조할 것입니다.힙 데이터 구조 소개 힙은 완전 이진 트리로 구성됩니다. 여기서 완전 이진 트리란 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨의 노드들이 왼쪽부터 차례대로 채워진 트리를 말합니다. 이러한 특성은 배열을 사용하여 효율적으로 구현할 수 있습니다.Max Heap과 Min Heap힙은 두 가지 주요 유형으로 나뉩니다: Max Heap과 M.. 2024. 5. 2. [알고리즘] 이진트리 유형 : Complete Binary Tree, Balanced Binary Tree, Full Binary Tree, Perfect Binary Tree 이진트리에는 4가지 유형이 주로 있습니다. Complete Binary Tree, Balanced Binary Tree, Full Binary Tree, Perfect Binary Tree 입니다. 이러한 4가지 유형의 트리를 알아야하는 이유는 데이터를 검색속도를 향상시키고 정확하고 빠르게 해당 데이터에 접근하기 위해서입니다. 각 유형별로 특징이 있기 때문에 해당 상황에 맞게 쓰시면 됩니다. 컴플리트 이진트리는 메모리 효율적인 데이터 구조로 사용됩니다. 배열을 기반으로 구현되어 메모리적으로 활용할 수 있으며, 우선순위큐 및 힙자료 구조 구현 등에도 사용됩니다.균형이진트리는 검색 및 삽입 작업을 효율적으로 수행해야하는 경우에 사용됩니다. 균형이진트리는 AVL 트리 레드블랙트리 형태로 사용됩니다. .. 2024. 5. 1. [알고리즘] 이진 트리 순회 방법: 중위, 전위, 후위 순회에 대한 이해 이진 트리는 컴퓨터 과학에서 널리 사용되는 중요한 자료 구조 중 하나입니다. 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 이진 트리는 데이터를 효율적으로 저장하고 탐색하는 데 사용됩니다. 이진 트리를 순회하는 것은 트리의 모든 노드를 방문하는 과정으로, 그 중에서도 중위, 전위, 후위 순회는 가장 흔히 사용되는 방법입니다.따라서 각 서브트리를 찾을때는 순회방식을 채택하여 알고리즘을 짜면 됩니다. ㅎㅎ 1. 중위 순회 (Inorder) 중위 순회는 왼쪽 하위 트리의 모든 노드를 먼저 방문한 후에 루트 노드를 방문하고, 마지막으로 오른쪽 하위 트리의 모든 노드를 방문하는 방식입니다. 이를 통해 트리의 노드를 오름차순으로 순회할 수 있습니다. 이러한 특성은 이진 탐색 트리(BST)에서 데이터를 검색.. 2024. 4. 30. [알고리즘] 이해하기 쉬운 트리 자료구조의 속성과 활용 트리 자료구조는 계층적인 구조를 표현하는 데 사용되며, 단방향 그래프의 한 종류로 볼 수 있습니다. 그 모양이 나무와 유사하여 트리라고 불립니다. 이 구조는 하나의 뿌리(root)에서부터 여러 가지 가지(branch)가 뻗어나가는 형태를 가지며, 데이터를 순차적으로 나열하는 선형 구조가 아니기 때문에 비선형 구조입니다. 또한, 트리는 아래로만 뻗어나가기 때문에 사이클이 없습니다.트리 자료구조는 여러 가지 속성을 가지고 있습니다. 루트(Root): 트리의 가장 위에 있는 노드로, 다른 모든 노드들은 이 루트 노드에서부터 시작합니다.노드(Node): 트리의 각 요소를 나타냅니다. 노드는 데이터를 저장하고 다른 노드와 연결된 엣지(Edge)를 가질 수 있습니다.엣지(Edge): 노드와 노드를 연결하는 선입니다.. 2024. 4. 29. [알고리즘] 빅O 표기법 & 왜 공간 복잡도가 시간 복잡도 보다 중요도가 낮을까? 알고리즘의 시간 복잡도는 알고리즘의 효율성을 이해하고 비교하는 데 중요한 지표 중 하나입니다. 이것은 알고리즘이 입력 크기에 따라 얼마나 빨리 실행되는지를 나타내는데, 일반적으로 "O 표기법"을 사용하여 표현됩니다. 여러 가지 표기법이 있지만, 주로 사용되는 표기법에 대해 알아보겠습니다. O 표기법: 최악의 경우에도 알고리즘이 얼마나 빨리 실행될 수 있는지에 대한 상한을 나타냅니다. 이것은 주어진 알고리즘이 얼마나 빠르게 실행될 수 있는지에 대한 상한을 제공합니다.Θ 표기법: 평균 복잡도를 나타냅니다. 이것은 알고리즘이 실행될 때 기대되는 작업량의 증가율을 나타냅니다.Ω 표기법: 최선의 경우에도 알고리즘이 얼마나 빨리 실행될 수 있는지에 대한 하한을 나타냅니다. 이것은 주어진 알고리즘이 최상의 경우에 얼.. 2024. 4. 28. 정보처리기사 실기 2020년 1회 : 데이터베이스, 네트워크, 알고리즘 1. 다음 ( ) 안에 들어갈 단어를 쓰시오. ( )은(는) 웹브라우저 간 HTML 문법이 호환되지 않는 문제와 SGML의 복잡함을 해결하기 위하여 개발된 다목적 마크업 언어이다. XML 2. 다음 ( ) 안에 들어갈 단어를 쓰시오. ( )은 속성-값 쌍(attribute-value pairs)으로 이루어진 데이터 오브젝트를 전달하기 위해 사용하는 개방형 표준 포맷이다. AJAX에서 많이 사용되고 XML을 대체하는 주요 데이터 포맷이다. 언어 독립형 데이터 포맷으로 다양한 프로그래밍 언어에서 사용되고 있다. JSON 3. 다음은 릴리즈 노트의 구성 항목에 관한 설명이다. 설명하는 항목은 무엇인가? 릴리즈 노트 이름, 소프트웨어 이름, 릴리즈 버전, 릴리즈 날짜, 릴리즈 노트 날짜, 릴리즈 노트 버전 등.. 2024. 3. 30. 이전 1 다음 728x90
