[ 알고리즘 ] 완전탐색(재귀) - 백트래킹, pruning

완전탐색(Exhaustive Search)재귀를 활용한 의사결정 트리 탐색정답이 될 가능성이 있는 모든 후보(candidates)를 탬색하여 정답을 찾는 알고리즘 패러다임의사결정 트리(possibility tree) 사용의사결정 트리 : 문제를 해결하는 모든 경우의 수를 트리 형태로 나타낸 것, DFS 방식으로 탐색하면 가능한 모든 경우를 빠짐없이 확인 가능 1️⃣ 완전탐색(재귀), DFS의사결정 트리를 DFS 방식 으로 순회하는 과정이라고 할 수 있음각 단계에서 가능한 선택지를 탐색하며 하나의 경로를 끝까지 탐색한 수 원래 상태로 되돌아 가는 방식1. 모든 가능한 경우를 표현2. DFS 방식으로 탐색3. 모든 Leaf 노드까지 도달 2️⃣ Backtracking(백트래킹)완전탐색으로 순회하면서 이전 ..

• format_list_bulleted 코딩테스트/개념정리
• · 2025. 6. 13.
• textsms

[ 알고리즘 ] BackTracking

재귀적으로 문제를 해결하되 상태가 제한조건에 위반되는지 판단확인 중인 상태가 제한 조건에 위배된다면 그 상태 이후의 탐색을 하지 않고 다음 단계로 탐색을 진행함🔍 백트래킹 vs. DFS(Depth First Search)공통점원하는 값을 찾기 위해서 탐색하는 알고리즘차이점백트래킹 : 불필요한 탐색을 하지 않고 조건에 맞지 않으면 더 이상 탐색을 진행하지 않음, 확인해야하는 경우의 수 줄일 수 있음DFS : 모든 경우의 수를 탐색[ 프로그래머스 ] #1835 : 단체사진 찍기 - JAVA

• format_list_bulleted 코딩테스트/개념정리
• · 2024. 12. 30.
• textsms

[ 프로그래머스 ] #1835 : 단체사진 찍기 - JAVA

🔗단체사진 찍기import java.util.ArrayList;import java.util.List;class Solution { static char[]friends={'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'}; static int count =0; public int solution(int n, String[] data) { //{조건을 제시한 프렌즈}~{상대방}{=,}{두 프렌즈 사이 사른 프렌즈의 수} //모든 조건을 만족할 수 있도록 서는 경우의 수를 계산 count =0; boolean[]visited=new boolean[friends.length]; List arrange=new ..

• format_list_bulleted 코딩테스트/문제풀이
• · 2024. 12. 30.
• textsms