본문 바로가기
반응형

시간복잡도7

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 비교(차이점, 장단점, 예시코드, 활용도) 2024.12.19 - [알고리즘] - DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도 DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도DFS(Depth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 한 경로를 끝까지 탐색한 후에 다른 경로로 이동하는 방식으로 동작합니다. 모든 경로를 탐색하거나best-coding.tistory.com2024.12.19 - [알고리즘] - BFS(너비 우선 탐색, Breadth-First Search) 알고리즘 - C언어, Java, Python 예시코드 포함, 시간복.. 2024. 12. 19.
트리(3) - 문자열 검색 문제에 최적화된 트라이(Trie) 자료구조(C언어, Java, Python 예시코드 포함) 1. 트라이(Trie) 자료구조란?트라이(Trie)는 문자열을 효율적으로 저장하고 검색하기 위해 설계된 트리(Tree) 기반 자료구조입니다. 주로 문자열 탐색, 자동 완성, 사전(dictionary) 구현에 사용됩니다. 이번 포스팅에서는 트라이의 구조, 구현 방법, 장단점, 활용 사례를 소개합니다. 2. 트라이의 원리와 구조(1) 트라이의 기본 개념**트라이(Trie)**는 각 노드가 문자열의 문자 하나를 나타내는 자료구조입니다.루트 노드에서 시작하여 문자열의 각 문자를 따라가며 데이터를 저장하거나 탐색합니다.문자열의 끝은 특별한 "종료 노드" 또는 플래그로 표시됩니다. (2) 트라이의 특징효율적인 검색: 문자열 검색 시간이 문자열 길이에 비례합니다. (O(L), L: 문자열 길이)공간 절약: 공통 접두.. 2024. 12. 18.
STL set 구조체활용(1) - 사용법(set은 만능이다?) 이번 글에서는 set의 기본 사용법을 알아보도록 하겠습니다. 그리고 마지막에는 Set을 문제 풀이에서 어떻게 사용하면 좋을지 말씀드리겠습니다. 1. set이란?set은 이진탐색트리(Binary Search Tree, BST) 구조로 구성되어 있습니다. 실제로는 BST 중 Red-Black Tree로 구현되어 있습니다. 그래서 최악의 경우에도 삽입,삭제,조회가 O(logN)만에 가능합니다.참고로 이진탐색 트리는 항상 우선순위가 "왼쪽자식노드이진탐색 트리의 내부 원소들은 항상 정렬된 상태를 유지합니다. Set의 경우 우선순위가 같은 원소들은 존재할 수 없습니다. 모든 원소는 유일합니다!! 기억해야할 내용을 요약하자면,1) set은 삽입, 삭제, 조회가 O(logN)만에 가능합니다.2) set의 모든 원소는 .. 2023. 3. 13.
반응형

티스토리툴바