그래프 탐색 알고리즘 : DFS/BFS
** 코테에서 매우 자주 등장하는 유형!
- 스택/큐 자료구조
스택
> 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)
> 입구와 출구가 동일한 형태. (박스쌓기 형태로 기억하면 좋음)
스택쌓기 예시코드 (파이썬)
자바스크립트로 구현하는 법 (push, pop을 이용)
[알고리즘/자료구조] JavaScript 스택(Stack) 구현하기
스택은 자료구조형에 속한다.먼저 들어간 자료가 나중에 나오는 후입선출 자료구조로, LIFO(Last In First Out)라고도 부른다.데이터를 입력하는 push()와 데이터를 제거하는 pop() 등의 작업을 할 수 있
velog.io
stack = []
#삽입(5) - 삽입(2) - 삽입(3)- 삭제
stack.append(5)
stack.append(2)
stack.append(3)
stack.pop()
print(stack[::-1] #최상단 원소부터 출력 > 실행결과: 2,5
print(stack) #최하단 원소부터 출력큐
- 먼저들어온 데이터가 먼저 나가는 형식(선입선출)
- 입구와 출구가 모두 뚫려 있는 터널 같은 형태로
큐 구현예제(C++)
참고) 자바스크립트에서 Queue를 독립적으로 자체 제공하지는 않지만 배열(Array)를 이용하여 큐의 기능을 흉내낼 수 있다. (ㅎ...) 흉내내는 법
#include <bits/stdc++.h>
using namespace std;
que<int> q;
int main (void) {
q.push(5);
q.push(2);
q.push(3);
q.pop();
//먼저 들어온 원소부터 추출
while (!q.empty()){
cout << q.front() << ' ';
q.pop();
}
}front 메서드는 que에 들어온 원소 중에서 앞쪽에 원소부터 추출하게 만드는 메서드
재귀함수
- 재귀함수는 자기자신을 다시 호출하는 함수를 의미.
- 재귀 깊이 제한을 걸어둘 수도 있음.
>> 재귀함수를 문제 풀이에서 사용할 때는 재귀함수의 종료 조건을 *반드시 명시해야 함*
-재귀와 반복문의 다른점? > 재귀함수는 return 값에서 자기 자신을 부른다는 것.
>> 장점 - 반복문보다 간결하게 작성 가능. but 반복문보다 불리한 경우도 있음.
>>스택은 스택프레임이 쌓이기 때문에 스택 라이브러리 대신 재귀함수 이용 많이 함.
DFS
-깊이 우선 탐색. 깊은 부분을 우선적으로 탐색
-스택 or 재귀함수 이용.
-인접 노드를 따라가서 더이상 인접 노드가 없을 때까지 가다가(깊게) 올라와서 인접노드로 가는
BFS
- 너비우선탐색
- 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조를 이용함.
[JS] BFS, DFS
원래 c++로 알고리즘을 공부하다가 웹 프론트엔드만 주구장창 하다보니 Javascript가 익숙해서 알고리즘 언어를 바꿨다..c++로 BFS, DFS 처음 이해 할 때 복잡했었는데 Javascript로 BFS, DFS를 구현해보니
velog.io
* 문제를 보고 어떤 알고리즘을 써야하는지 생각하기
- 아이스크림 > 연결요소 찾기 > DFS or BFS 로 연결 요소를 찾는 것 > 그래프 형태로 모델링해서 찾을 수 있으므로. > 특정 지점에서 연결된 모든 노드를 방문처리
- 간선의 길이가 같을 때 최단거리구하기 : BFS
-
댓글