반응형 스택2 깊이 우선 탐색(DFS) 🤔 DFS란?그래프 완전 탐색 기법 중 하나이다.스택 자료구조를 이용하여 재귀 함수로 구현이 가능하다.시작 노드에서 출발하여 탐색할 한 쪽 루트를 최대 깊이까지 탐색을 마친 후, 다음 루트로 이동하여 탐색하는 알고리즘이다.시간 복잡도는 O(노드 수 + 에지 수)이다.👉 DFS 수행 방식✔️ DFS 과정스택의 후입선출 특성을 가지고 DFS 탐색 방식을 표현할 수 있다.DFS 시작할 노드를 정하고, 스택 자료구조에 초기화시켜준다. (DFS 수행 과정 1)방문 리스트에는 스택 자료구조에 추가됨과 동시에 방문 기록을 남긴다.스택에서 초기화한 노드를 꺼내고, 꺼낸 노드의 이웃 노드를 다시 스택에 추가시켜준다.마찬가지로 방문 리스트에 방문 기록을 남겨 재방문하지 않도록 설정해준다.스택 자료구조에 값이 없을 때.. 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. 이전 1 다음 반응형
