본문 바로가기
반응형

2

너비 우선 탐색(BFS) 🤔 BFS란?그래프 완전 탐색 기법 중 하나이다.큐 자료구조의 특징인 FIFO 탐색을 사용한다.시작 노드에서 출발하여 시작 노드와 가까운 노드를 먼저 방문하여 탐색을 진행한다.시간 복잡도는 O(노드 수 +  에지 수)이다.👉 BFS 수행 방식✔️ BFS 과정BFS에 시작할 노드를 정한 후 큐 자료구조에 초기화한다.큐에서 노드를 꺼내고, 해당 노드의 인접 노드를 다시 큐에 추가한다.큐에 값이 없을 때까지 반복한다.DFS 탐색 순서 결과가 다른 것을 확인해볼 수 있다. 2023.03.20 - [알고리즘/탐색] - 깊이 우선 탐색(DFS) 깊이 우선 탐색(DFS)🤔 DFS란? 그래프 완전 탐색 기법 중 하나이다. 스택 자료구조를 이용하여 재귀 함수로 구현이 가능하다. 시작 노드에서 출발하여 탐색할 한 쪽.. 2023. 3. 20.
스택 & 큐 🤔스택이란?스택(Stack)은 삽입과 삭제 연산이 후입선출(LIFO; Last-in First-out)로 이루어지는 자료구조이다.후입선출의 경우, 삽입과 삭제는 한 쪽에서만 발생된다.📌리스트를 이용한 스택top : 삽입과 삭제가 일어나는 위치를 의미한다.append() : top 위치에 새로운 데이터를 추가하는 연산이다.pop() : top 위치에 현재 들어있는 데이터를 삭제하고 확인하는 연산이다.✔️ 스택 활용재귀 함수깊이 우선 탐색; DFS백트래킹🤔큐 란?큐(queue)는 삽입과 삭제 연산인 선입선출(FIFO; First-in First-out)로 이루어진 자료구조이다.선입선출의 경우 삽입과 삭제가 양방향에서 이루어진다.📌deque를 이용한 큐rear : 큐의 가장 끝 데이터를 가리키는 것이다.. 2023. 3. 18.
반응형