BFS2 [개념 정리] BFS(너비 우선 탐색) 너비 우선 탐색이 뭘까? 이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다. 너비 우선 탐색너비 우선 탐색인 BFS(Breath Frist Search)는 그래프를 탐색하는 알고리즘으로, 한 정점에서 시작해 다음 깊이의 정점으로 이동하기 전에 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘입니다.즉, BFS는 계층별로 레벨별로 탐색을 한다는 의미입니다. 주로 같은 가중치를 가진 그래프에서 최단 거리 알고리즘으로 사용됩니다. BFS는 아래 그림의 순서로 탐색합니다.탐색 순서는1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 가 됩니다. 너비 우선 탐색의 수도 코드를 알아볼까요? 너비 우선 탐색의 수도 코드는 2.. 2025. 2. 27. [프로그래머스] Lv3 카운트 다운 문제 풀이 방법 문제에선 구하라고 하는 값은 최선의 경우 던질 다트 수(최솟값)와 그 때의 싱글 또는 불을 맞춘 횟수(합)을 순서대로 배열에 담으라고 합니다. 다트를 던지는 방법은 싱글, 2배, 3배, 불 이렇게 4가지의 방법이 있고 최솟값을 구하라는 문제에서 백트래킹 + DP 알고리즘을 생각했습니다. 백트래킹 + DP 알고리즘은 몇몇 테스트는 통과를 했지만, 런타임 예외가 발생했습니다. 문제에서 target이 100,000이기도 하고 DFS를 사용한 경우 한 depth가 늘어날때마다 4개의 경우로 분기가 되기 때문에 재귀 호출이 매우 깊어집니다. 백트래킹을 적용할 시 이미 방문한 상태보다 더 나은 경우만 탐색해야 하지만, 싱글/볼을 최대로 하는 조건까지 고려하는 경우엔 백트래킹을 적용한다고 해도 경.. 2025. 2. 20. 이전 1 다음
