DFS4 [Java] 프로그래머스 - 피로도 최소 필요 피로도와 소모 피로도가 있는 여러 던전 중, 현재 피로도 k로 탐험할 수 있는 최대 던전 수를 구하는 문제 1. 문제 유형DFS, 백트래킹, 완전탐색 2. 내가 놓친 포인트처음 떠올린 접근 : 처음에는 index + 1, index - 1처럼 배열의 위치를 이동하면서 던전을 탐색하려고 했다.오답 원인: DFS를 다음 index로 이동하는 방식으로 생각했는데, 이 문제의 핵심은 index 이동이 아니라 방문 여부를 관리하면서 모든 순서를 탐색하는 것이었다. 3. 핵심 로직 & 해결 방법핵심 조건: 아직 방문하지 않은 던전이고, 현재 피로도가 해당 던전의 최소 필요 피로도 이상이면 탐험할 수 있다. 풀이 아이디어:DFS에 현재 피로도 k와 현재까지 탐험한 던전 수 count를 넘긴다.DFS에 들.. 2026. 5. 6. [Java] 프로그래머스 - N-Queen n x n 체스판에서 서로 공격할 수 없도록 퀸 n개를 배치하는 경우의 수를 구하는 문제 1. 문제 유형백트래킹, DFS, 재귀 2. 내가 놓친 포인트처음 떠올린 접근 : 처음에는 int[][] map으로 체스판 전체를 만들고, 퀸을 놓을 수 있는지 매번 검사하려고 했다. 이 방식 자체가 틀린 것은 아니지만, 문제를 너무 체스판 전체 탐색으로 바라봐서 복잡하게 느껴졌다.특히 현재 위치에 퀸을 놓을 수 있는지 검사할 때 위쪽 행의 모든 칸을 다시 확인해야 해서 흐름이 잘 안 잡혔다.오답 원인: 처음에는 dfs()가 체스판 전체를 탐색하는 함수처럼 느껴졌는데, 한 번의 DFS 호출은 현재 행에 퀸을 어디에 둘지 선택하는 단계였다. 3. 핵심 로직 & 해결 방법핵심 조건: 퀸은 같은 열, 같은 대각선에 있으.. 2026. 4. 29. [Java] 프로그래머스 - 타겟 넘버 각 숫자에 + 또는 - 를 붙여 만들 수 있는 모든 합 중에서, 타겟 넘버와 같은 경우의 수를 구하는 문제. 1. 문제 유형DFS 2. 내가 놓친 포인트처음 떠올린 접근 : 처음에는 visited 같은 방문 체크가 필요한 문제인가 생각했고, 숫자를 선택하는 방식처럼 접근하려 했다. 오답 원인: dfs를 구현할 때 현재 숫자 하나만 보는 게 아니라, 현재 인덱스와 현재까지의 누적합을 같이 넘겨야 한다는 점을 놓쳤다. 3. 핵심 로직 & 해결 방법핵심 조건: 각 숫자는 한 번씩 순서대로 사용하고, 매 위치마다 + 또는 - 두 경우로 나뉜다. 풀이 아이디어:dfs 함수에 index와 currentSum을 넘긴다.현재 위치의 숫자에 대해 +numbers[index], -numbers[index] 두 방향으로 .. 2026. 4. 17. [Java] 프로그래머스 - 소수 찾기 숫자 조각으로 만들 수 있는 모든 수를 완전탐색으로 생성한 뒤, 중복을 제거하고 소수 개수를 구하는 문제 1. 문제 유형완전탐색, 백트래킹(DFS), 구현 2. 내가 놓친 포인트처음 떠올린 접근 : 문자 하나씩 조합해서 숫자를 만들고, set에 넣어서 중복을 제거한 뒤에 그 숫자가 소수인지 검사하면 될 것 같았다. 오답 원인: 풀이 아이디어는 맞았는데 코드로 구현을 못했다. 3. 핵심 로직 & 해결 방법핵심 조건: 주어진 숫자 조각들로 만들 수 있는 모든 길이의 숫자를 만들어야 하며 같은 숫자는 한 번만 세야 한다. 풀이 아이디어:visited[]를 사용해 현재 경로에서 이미 사용한 숫자 조각을 체크한다.dfs를 돌면서 숫자를 한 자리씩 이어 붙여 current를 만든다.current가 비어있지 않다면 .. 2026. 4. 17. 이전 1 다음