쿠쿠의 개발일지

[문제] 출처 - https://programmers.co.kr/learn/courses/30/lessons/42839?language=java 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr [문제 풀이] 이 문제는 소수를 판단하는 함수와 dfs방식으로 찾는 함수를 만들어서 구현을 해준다. dfs함수를 구현할때 String 값을 Integer값으로 변경하여 찾을 수 있는 값 전부를 중복없이 리스트에 담아주고 리스트에 담긴 값들을 소수판단하여 세주면 된다. 백트래킹 방법 사용 for문을 사용해 ..

퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다. -출처 위키백과 백트래킹(Backtracking) 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아갑니다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미 입니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다. 즉 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 입니다. 주로 문제 풀이에서는 재귀로 모든 경우의 수를 탐색하는 과정에서 답이 절대로 될 수 없는 상황을 정의하고 그 경우 ..