DFS 란 무엇인가? 앞에 복잡한 미로가 있다고 상상해본다. 출구를 찾기 위해 어떻게 할것 인가.. 아마 많은 사람들이 일단 한 갈래 길을 선택해서 막다른 길이 나올때 까지 쭉 가본다고 생각한다. 만약 막다른 길을 만나면, 직전 갈림길로 돌아와서 아직 가보지 않은 길을 선택해 다시 끝까지 가보겠죠?  이게 DFS 이다. 왜 DFS를 사용할까? ⏰ 시간 복잡도- 인접 행렬: 모든 노드(V) 간의 연결을 확인해야 할 수 있어 O(V²) 시간이 소요됩니다.- 인접 리스트: 실제 연결된 노드(V)와 간선(E)만 탐색하므로 O(V+E) 시간이 걸려 보통 더 효율적입니다.(V: 노드 개수, E: 간선 개수) 👍 장점- 현재 경로만 기억하므로 메모리 사용량이 적습니다.- 너비 우선 탐색(BFS)에 비해 구현이 상대..

알고리즘 공부를 하다 보면 자주 등장하는 '백트레킹(Backtracking)'이란 알고리즘을 만나게 된다.    👀 백트레킹(Backtracking) 이란?해를 찾는 도중 해가 아니어서 막히면 더이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 다시 해를 찾아내는 기법이라고 설명 할 수 있다.현재 상태에서 가능한 모든 선택지를 하나씩 시도해보고, 조건에 맞지 않으면 이전 상태로 돌아가 다른 선택지를 탐색하는 방식으로 작동한다.  쉽게 말해, 문제를 해결하기 위해 하나의 길을 따라 탐색하다가 원하는 해답에 도달하지 못할 경우, 그 지점에서 "뒤로 돌아가(backtrack)" 다른 경로를 시도하는 방식이다. 백트레킹 알고리즘에서 가장 중요한 개념 중 하나가 "가지치기" 이다.만족하지 못할 것으로 판단되는 ..