자료구조5 [알고리즘] DFS와 BFS(개념, 특징, 동작 원리, 파이썬 예시) DFS(깊이 우선 탐색) DFS(깊이 우선 탐색)는 그래프의 모든 정점을 방문하는 데 사용되는 알고리즘 중 하나입니다. 이 방법은 가능한 한 깊게 그래프를 탐색하며, 더 이상 진행할 수 없는 지점에 도달하면 이전 분기점으로 되돌아가 다른 경로를 탐색합니다. DFS는 스택 또는 재귀함수를 이용할 수 있으며, 그래프의 구조를 이해하거나 복잡한 문제를 단순화하는 데 유용합니다. 동작 원리탐색 시작점 선택: DFS는 그래프의 한 정점에서 시작합니다. 시작점은 그래프의 구조나 문제의 요구에 따라 달라질 수 있습니다.인접 정점 탐색: 현재 정점에서 방문하지 않은 인접 정점을 선택합니다. 인접 정점 중에서 선택하는 기준은 그래프의 표현 방식(ex: 인접 리스트, 인접 행렬)에 따라 다를 수 있습니다.깊이 우선 탐색 .. 2024. 5. 7. [자료 구조] 해시테이블(Hash Table)이란? (특징, 시간복잡도, 파이썬 사용, 사용 사례) 해시테이블은 효율적인 데이터 검색을 가능하게 하는 자료구조 중 하나입니다. 키(Key)를 값(Value)에 매핑하여 데이터를 저장하는 방식으로, 해시함수를 사용해 데이터의 저장 위치를 결정합니다. 해시함수는 키를 고유한 숫자(해시코드)로 변환하여, 이 숫자를 기반으로 데이터가 저장될 위치를 빠르게 찾을 수 있게 합니다. 주요 특징빠른 데이터 접근 속도: 해시 함수를 통해 데이터의 저장 위치를 바로 찾을 수 있기 때문에, 평균적으로 상수 시간 O(1) 내에 데이터에 접근할 수 있습니다. 하지만, 해시 충돌(Hash Collision)이 발생하는 경우, 이 시간은 늘어날 수 있습니다.해시 충돌(Hash Collision): 서로 다른 키가 동일한 해시값을 가질 때 발생합니다. 해시 테이블은 충돌을 관리하.. 2024. 5. 2. [자료구조] Tree(트리)? (개념, 특징, 활용, 파이썬 사용) 트리(Tree)는 컴퓨터 과학에서 데이터를 다루기 위한 중요한 자료구조 중 하나입니다. 트리는 노드(Node)들이 가지(branch)를 통해 연결된 계층적 구조를 가지며, 여러 응용 분야에서 활용됩니다. 특히, 계층적 데이터를 다루거나 데이터를 효율적으로 검색, 추가, 삭제하는 작업에 유용하게 쓰입니다. 기본 개념노드(Node): 트리를 구성하는 기본 요소입니다. 데이터를 저장하며 하나 이상의 자식 노드를 가질 수 있습니다.루트 노드(Root Node): 트리의 최상위에 위치하는 노드입니다. 하나의 트리에는 단 하나의 루트 노드만 존재합니다.부모 노드(Parent Node): 특정 노드의 바로 윗 단계에 위치하는 노드입니다.자식 노드(Child Node): 특정 노드의 하위에 위치하는 노드입니다.형제.. 2024. 5. 1. [자료구조] Stack과 Queue? (특징, 사용 사례, 예시) Stack(스택)스택(Stack)은 컴퓨터 과학에서 너리 사용되는 기본적인 자료구조 중 하나입니다. 스택은 데이터를 일시적으로 저장하기 위한 선형 구조로, 가장 마지막에 들어온 데이터가 가장 먼저 나가는 '후입선출'(LIFO, Last In First Out)의 특성을 가지고 있습니다. 이러한 특성 때문에 스택은 데이터의 역순 저장, 실행 취소 기능 등에 유용하게 사용됩니다. 특징후입선출(LIFO) 특성: 스택에 데이터를 추가하거나 제거할 때, 항상 스택의 맨 위에서만 작업이 이루어집니다. 이는 책을 쌓아 올린 후 가장 위에 있는 책을 먼저 꺼내는 것과 유사합니다.용도: 스택은 프로그램에서 함수 호출과 반환 주소를 관리하는 데 사용되며, 괄호 검사, 역순 문자열 생성, 웹 브라우저의 뒤로 가기 기능 .. 2024. 4. 30. 이전 1 2 다음
