BFS2 [알고리즘] DFS와 BFS 1. DFS(Depth-First Search) - 깊이 우선 탐색 - 루트 노드나 임의 노드에서 "다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색"하는 방법 - 스택이나 재귀함수를 이용해 구현 - 모든 경로를 방문해야 할 경우 적합 - 인접 행렬 : O(V^2) - 인접 리스트 : O(V+E) // V는 접점, E는 간선 2. BFS(Breadth-First Search) - 너비 우선 탐색 - 루트 노드나 임의 노드에서 "인접한 노드부터 먼저 탐색"하는 방법 - 큐를 이용해 구현 - 최소 비용으로 탐색을 진행할 때 적합\ - 인접 행렬 : O(V^2) - 인접 리스트 : O(V+E) 3. 소스코드(C++) // DFS #include #include using namespace std; int .. 2023. 10. 30. [면접 준비][자료구조] 스택과 큐의 차이점 1. 스택(Stack) - 나중에 들어간 것이 먼저 나오는 후입선출의 구조이다.(LIFO) - 비어있는 스택에서 원소를 추출하면 stack underflow - 스택이 넘치는 경우 stack overflow - ex) 뒤로가기, 실행취소, 역순 문자열 만들기 등 2. 큐(Queue) - 먼저 들어간 것이 먼저 나오는 선입선출의 구조(FIFO) - 한쪽 끝에서는 삽입 작업이, 다른 쪽 끝에서는 삭제 작업이 양쪽으로 이루어짐 - ex) 줄을 서서 기다려야하는 모든 행동들, 프로세스 관리, 너비우선탐색(BFS) 등 스택은 나중에 들어간 것이 먼저 나오는 후입선출, LIFO의 구조이고, 큐는 먼저 들어간 것이 먼저 나오는 선입선출, FIFO의 구조입니다. 스택의 예시로는 실행취소 등이 있고, 큐의 예시로는 줄을.. 2023. 7. 22. 이전 1 다음
