728x90 반응형 DFS12 프로그래머스 Level 2 – 소수 찾기(Java, 완전탐색 + 백트래킹) 🔢 프로그래머스 Level 2 – 소수 찾기(Java, 완전탐색 + 백트래킹)이번에 정리한 문제는 완전탐색의 대표 문제인 **‘소수 찾기’**다.문자열로 주어진 숫자들로 만들 수 있는 모든 조합을 생성하고,그 안에서 소수인 숫자들의 개수를 세는 문제다.언뜻 쉬워 보이지만,자리수를 마음대로 섞을 수 있고길이도 1자리 ~ 전체 길이까지 모두 고려해야 하며중복 숫자 조합은 제거해야 한다라는 조건 때문에 생각보다 구현 포인트가 많다.📌 문제 핵심 요약주어진 문자열 "numbers" 안의 숫자로 만들 수 있는 모든 수 중**소수(prime number)**가 몇 개인지 구하는 문제다.예시: "17"가능한 조합 → 1, 7, 17, 71소수 → 7, 17, 71 → 총 3개🧠 풀이 핵심 아이디어✔ 1. 백트래.. 2025. 11. 18. 프로그래머스 Level 3 – 여행경로(Java, DFS 백트래킹) 풀이 ✈️ 프로그래머스 Level 3 – 여행경로(Java, DFS 백트래킹) 풀이오늘은 프로그래머스에서 정말 자주 등장하는 그래프/백트래킹 문제,바로 “여행경로” 문제를 정리해봤다.이 문제의 핵심은 아주 단순하다.주어진 항공권들을 모두 사용해서 만들 수 있는 경로 중사전순으로 가장 앞서는 경로를 찾는 것.그래서 DFS + 백트래킹을 이용해"항공권을 사용했다가 다시 되돌리기" 작업을 하면서모든 경우의 수를 탐색한다.📌 문제 핵심 포인트✔️ 1. 항상 "ICN"에서 출발문제에서 출발점이 고정되어 있다.✔️ 2. 티켓을 사전순으로 정렬해야 함왜?→ DFS 진행 중 여러 경로가 생기는데,사전순으로 정렬해두면 가장 먼저 완성되는 경로가 곧 정답이기 때문이다.✔️ 3. 모든 티켓을 사용했을 때가 종료 조건티켓 개수가.. 2025. 11. 18. 프로그래머스 Level 2 – 타겟 넘버(Java, DFS) 🎯 프로그래머스 Level 2 – 타겟 넘버(Java, DFS)이번에 정리한 문제는 프로그래머스에서 정말 많이 나오는 대표적인 DFS 문제,바로 **‘타겟 넘버(Target Number)’**다.문제 자체는 간단해 보이지만,모든 숫자에 대해 + 또는 - 를 붙여서 모든 경우의 수를 탐색해야 한다는 점 때문에 DFS가 가장 깔끔하게 들어맞는 문제다.📌 문제 요약숫자 배열(numbers)이 주어진다.각 숫자 앞에 + 또는 - 를 붙여 만들 수 있는 모든 경우의 수 중합이 target이 되는 경우의 수를 구하는 문제.즉,각 숫자마다 두 갈래로 뻗어나가는 완전탐색(DFS)을 구현하면 끝!🧠 풀이 핵심 아이디어✔ 1. DFS로 모든 조합 탐색각 숫자에는+numbers[i]-numbers[i]두 가지 경우가 .. 2025. 11. 18. 2022.04.24 [백준] (python 파이썬) N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 https://blog.encrypted.gg/945 [실전 알고리즘] 0x0C강 - 백트래킹 이번에는 백트래킹을 배워보도록 하겠습니다. 백트래킹도 재귀와 더불어 많은 사람들이 고통을 호소하는 알고리즘 중 하나이지만 의외로 그 재귀적인 구조에 매료되어서 참재미를 알아버리는 blog.encrypted.gg 해당 문제는 위의 블로그에서 공부한 후, 참고하여 해결했습니다. 이 문제를 해결할 때, 퀸이 놓일때마다 .. 2022. 4. 24. 이전 1 2 3 다음 728x90 반응형
