Algorithm

Algorithm

[Algorithm/Swift] 깊이 우선 탐색 (DFS)

📚 벌써 6월입니다 🫠 오늘은 알고리즘에서 꼭 알아야 하는 DFS !! 저번 글에서 아주 짧게 언급했었는데 오늘은 개념 + 코드로 잘근잘근 씹어봅시다 😬 깊이 우선 탐색 (DFS, Depth-First Search) 그래프 탐색 알고리즘 중 하나로, 주어진 그래프에서 한 정점을 시작으로 그래프를 탐색하는 방법이다. 그래프는 정점(노드)과 간선의 집합으로 이루어진 자료구조로, 각 정점은 다른 정점과 연결될 수 있다. 탐색하려는 노드의 자식 노드부터 우선 탐색(깊이를 우선하여 탐색)하는 방식이다. 탐색 과정에서 선택한 노드에 연결된 노드들을 모두 방문한 후에는 이전 노드(부모 노드)로 돌아가서 다른 연결된 노드를 선택한다. 이 과정을 반복하여 그래프의 모든 정점을 방문한다. DFS는 주로 그래프 순회나 스도..

Algorithm

[Algorithm] 백트래킹(Backtracking)과 브루트포스(Brute Force)

📚 안녕하시렵니까앍 - ! (feat. 주우재) 오늘은 백트래킹 알고리즘에 브루트포스 알고리즘을 사알짝 곁들인 글을 가져왔습니다앍 🐓 백트래킹(Backtracking) 백트래킹(Backtracking)이란, 해를 찾는 도중에 현재 경로의 유망성을 판단하여 해가 될 것 같지 않으면 되돌아가서 다시 해를 찾아가는 기법이다. 백트래킹 알고리즘은 탐색 과정에서 불필요한 경우를 배제하여 실행시간을 단축시키는 특징을 가지고 있다. 즉, 가능한 경우의 수를 순차적으로 시도하다가 조건을 만족하지 않는 경우에 이전 단계로 돌아가 다음 경우를 시도한다. 이러한 과정을 재귀적으로 진행하며 최적의 해를 찾을 때까지 탐색을 진행 ! 주로 조합적인 문제나 제약 조건이 있는 문제를 해결하는 데 사용된다. 대표적인 예로는 스도쿠, ..

Algorithm

[Algorithm/Swift] 동적계획법(DP)

📚 알고리즘 문제를 풀다가 기록해둬야 할 것 같아서 오랜만에 글 끄적끄적 📝 동적 계획법(DP; Dynamic Programming)이란 ? 큰 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법으로, 주어진 문제를 여러 개의 하위 문제로 분할하고 각 하위 문제의 결과를 저장하여 저장한 값을 이용해 상위 문제를 점진적으로 해결하는 방식을 사용한다. DP는 중복되는 하위 문제들이 존재할 때 효과적으로 사용된다. 동일한 하위 문제가 여러 번 반복해서 계산되는 경우, DP는 이전에 계산한 값을 저장해 두었다가 재사용함으로써 중복 계산을 피할 수 있다. 이를 "Memoization"이라고도 부른다. 💡 메모이제이션(Memoization)은 이전에 계산한 값을 메모리에 저장하는 방식으로 중복 수행을 제거..

릴 루
'Algorithm' 카테고리의 글 목록