백트래킹?모든 가능한 방문 조합을 재귀적으로 시도해보고, 그중에서 유효한 것만 정답 후보로 선택모든 경우를 탐색하되, 중간에 불가능한 경로는 더 이상 가지 않고 돌아가는 알고리즘 해당 문제를 보고 백트래킹을 써야겠다는 생각이 들었다.하지만 구현하는 데에 좀 어려움을 겪었다.처음에 dx, dy로 한칸씩 이동하면서 초코우유를 먹으면서 체력을 늘리고 2를 0으로 바꾼 뒤에 다시 탐색해보는 방향으로 생각했는데 아주 잘못된 생각이었다. 이 문제의 목표는 최대한 많은 민트초코우유를 먹고, 집에 돌아올 수 있는 경우 중 우유의 최대 개수를 구하는 것이다.조건은 아래와 같다. N x N 크기의 마을 (map)진우의 집은 1, 민트초코우유는 2, 빈칸은 0진우는 상하좌우 한 칸 이동에 체력 1 소모민트초코우유를 먹으면..

https://www.acmicpc.net/problem/32387 문제를 읽으면서 대충 요약하면서 정리해보았다.Node 클래스가 필요하다는 것을 먼저 파악하고 어떤 값이 들어갈지 고민해보았고,먼저, 인덱스와 전력 그리고 행동 순서 를 기억하고 있어야겠다고 생각했다.그리고 예시를 직접 테스트해보면서 내가 이해한 바가 맞는지 확인하였다.첫 코드package baekjoon._32387;//https://www.acmicpc.net/problem/32387import java.util.*;import java.io.*;public class Main { static int N, Q; static List multitab; public static void main(String[] args) throws E..

https://www.acmicpc.net/problem/20040 유니온 파인드 관련된 문제를 찾아서 진행했다.두 점을 연결하는 과정을 거치면서 사이클이 완성되면 끝나는 게임이다. 두 점을 union하면서 isSameParent 로직으로 확인하면서 cycle이 발생하면 몇 번째 union 에서 발생했는지 출력하면 된다.* 중요 -> union하면서 parent[] 배열로 부모 점을 계속 변경해주어야 한다. 이때는 둘 중 작은 수로 부모를 변경해야 한다.union -> 두 점을 연결하고 같은 부모를 바라보게 한다.find -> 각 점의 부모를 찾는다.isSameParent -> 부모가 같은지 확인한다. 최종 코드package baekjoon._20040;import java.io.*;import java..

https://www.acmicpc.net/problem/2638처음 문제를 보았을 때 아래와 같이 판단하였다.1. BFS를 통해서 먼저 외부 공기(-1)를 구분한다.2. 배열을 순회하면서 외부 공기랑 2면 이상 닿으면 0으로 표시한다.3. 치즈가 없는지 판단한다.(1이 하나라도 있으면 true 반환) * 문제를 풀 때, 초기화 단계를 잊어버리는 경우가 많아서 체크하기 위해 따로 적어둔다. 하지만 while문을 통과하지 못하는 오류가 발생하였다.확인해보니 치즈를 녹이는 단계에서 외부 공기랑 2면 이상 닿았을 때 바로 0으로 바꾸는 것 때문에 제대로 다음 치즈들에 대해서 처리가 되지 않았다.또한 외부 공기를 한 번 확인하고 치즈를 녹이는데 다시 외부 공기를 확인할 때 외부 공기를 다시 판단해야하는데 초기화..

문제접근이 문제는 문자열 S 안에서 특정 패턴 Pn이 몇 번 등장하는지 확인하는 문제입니다.처음엔 입력 값을 제대로 확인하지 않고 서브 태스크1에 있는 것을 보고 1. i번째에서 i+3까지 자르고 i를 1개씩 올려가면서2. Substring한 문자열이 Pn과 같은지 확인하였습니다.이 경우 N이 매우 커졌을 경우에 2N+1 크기의 문자열을 M 번 확인해야하는 큰 연산이 걸려 매우 큰 시간복잡도가 나오게 됩니다.그렇기 때문에 다른 방법을 사용하여야겠다고 생각하였습니다.- 슬라이딩 윈도우 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘슬라이딩 윈도우를 사용하여 Pn 문자열에서는 공통된 pattern이 존재하기 때문에 'IOI'를 고정 윈도우로 지정하여 윈도 내에 있..

문제접근DP 사용해서 이전의 결과값을 사용해서 효율적인 계산을 진행하였다.예시스티커를 뗀 부분이 O이고찢겨진 부분은 X라고 하자.(0,2) 위치의 스티커를 뗀 경우는 아래와 같이 나누어진다. 지금 목표는 스티커를 뗀 경우 중 가장 큰 값을 얻었을 때이기 때문에 이때 둘 중에 큰 값을 선택하고 (0,2) 위치의 스티커 값을 더해주면 된다.이외에 아무것도 떼지 않은 경우(1,1) 위치의 스티커를 뗀 경우 (0,3) 위치의 스티커를 뗀 경우는 아래와 같이 나누어진다. (1,2) 위치의 스티커를 뗀 경우(1,1) 위치의 스티커를 뗀 경우해당 값 중에 큰 값을 선택하고 (0,3) 위치의 스티커 값을 더해주면 된다. 그러면 아래와 같은 점화식을 얻을 수 있다.구한 점화식을 코드에 적용하면 아래 코드와 같다.코드im..

문제접근DFS 탐색을 통해서 말을 이동할 수 있는 경로 탐색이때, alphabets 배열을 통해서 중복된 알파벳의 경로로 가지 않도록 해야 한다고 생각하였다.alphabets 배열을 A~Z까지의 26의 크기를 가진 배열로 설정하였다.해당 알파벳의 정수 값에서 'A'의 정수값을 빼면 해당 알파벳의 인덱스 값이 되기 때문에 탐색한 경우 해당 배열 인덱스에 위치한 값을 true로 변환해주었다.백트래킹!!!!알파벳을 탐색하면서 중복 처리를 한 map에서 말의 움직임을 count한다.이때 다른 경로를 탐색하기 위해 중복 처리를 한 부분을 다시 원복시킨다.원복 시킨 것에서 다른 경로로 탐색하고 다시 중복처리를 진행하면서 말의 움직임을 또 count한다.탐색할 때마다 maxCount를 최댓값으로 갱신해주면서 최종 값..

문제접근2*1 의 경우는 1가지2*2의 경우는 2가지2*3의 경우는 3가지...규칙이 있는 것을 찾아냈다.예를 들어 n=5인 경우, 마지막 2*1 부분  빼고 모두 차있는 경우 + 마지막 2*2 부분이 가로로 채워져 있고 모두 차있는 경우두 가지 경우를 더한 경우의 수가 모든 경우의 수이다.점화식 : dp[i] = dp[i-1] + dp[i-2]코드import java.util.*;public class Main { static int[] dp; static int N; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); dp = n..

문제https://www.acmicpc.net/problem/11725접근인접 리스트로 트리 생성DFS 로 루트 노드 1부터 탐색탐색 시 해당 노드의 부모를 parents 배열에 기록한다.노드 탐색 시 다시 부모 노드를 탐색하지 않기 위해 주의!코드import java.util.*;import java.io.*;public class TreeParent_11725 { static List[] tree; static int[] parents; static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRe..

문제접근완전 탐색을 통해서 현재 주어진 맵에서 벽 3개를 세우는 모든 경우의 수를 구해야 한다고 생각했다. -> 백트래킹경우의 수 별로 바이러스가 퍼진 것을 파악해 안전지대가 최대 크기인 경우를 출력해야 한다고 생각했다.이 때 바이러스가 퍼진 것은 BFS를 통해서 구현하고자 했다.풀이입력 처리 및 초기화:BufferedReader와 StringTokenizer를 사용하여 입력을 처리하고, 격자 크기(N x M)와 map 배열을 초기화합니다.map 배열에는 현재 연구소의 상태를 저장하고, tempMap 배열은 바이러스가 퍼졌을 때의 상태를 저장합니다.벽 설치 (buildWalls 메소드):3개의 벽을 세우기 위해 백트래킹을 사용합니다.벽이 3개 설치되면 (count == WALL_COUNT), 바이러스가 ..