문제접근이 문제는 문자열 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), 바이러스가 ..

문제접근가중치 O방향 O방향과 가중치가 있는 그래프이기 때문에 클래스를 활용한 인접리스트를 구현하였다.그 후에 모든 학생이 위치한 노드로부터 X(파티 장소) 까지로의 최단 거리와 X(파티 장소) 에서 다시 자신이 위치한 마을로 돌아가는 최단 거리를 합친 것 중 가장 큰 값을 출력해야 하기 때문에 다익스트라 알고리즘을 사용하였다.다익스트라 알고리즘은 그래프에서 하나의 시작 노드로부터 다른 모든 노드까지의 최단 경로를 구하는 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 동작하며, 음의 가중치가 없는 그래프에 적합합니다.다익스트라 알고리즘은 음의 가중치를 가진 그래프에서 사용할 수 없습니다. 음의 가중치가 있는 경우, 벨만-포드 알고리즘과 같은 다른 알고리즘을 사용해야 합니다.문제 풀이가중치 있는 ..

[백준 1167] 트리의 지름접근트리의 지름트리 내의 두 노드 사이의 가장 긴 경로이다.문제 풀이입력을 트리로 변환인접 리스트에 Point클래스 (목적지 노드, 가중치) 자료형 사용해서 가중치 있는 그래프 표현.DFS 를 통해서 1에서 가장 멀리 떨어진 노드 탐색가장 멀리 떨어진 노드를 기준으로 다시 DFS를 진행해서 트리의 지름을 구함.사용한 알고리즘DFS시간 복잡도O(n)막힌 부분.DFS를 통해서 가장 멀리 떨어진 노드를 탐색하는 것까지는 생각함.그 이후에 어떻게 지름을 구하는지에 대해서 막혔다.지름을 구하기 위해서 다시 DFS 탐색이 필요하다는 것까지 생각을 못했다.. ㅜㅜ2-1. 모든 경로의 경우의 수를 탐색해서 지름을 구하는 것도 생각했는데 이때 노드가 많아질수록 모든 경로를 탐색하는데 드는 시..

백준 16953 A -> B접근처음에는 이진 트리로 1차원 배열에 두 연산을 저장하면서 진행하려고 했으나 메모리 초과가 발생한다는 것을 깨닫고 방향을 전환하였다.BFS 를 통해서 B까지 도달할 수 있는 가능한 연산 횟숫를 찾고자 하였다.만약 가능한 연산이 없을 경우에는 -1을 출력해야 한다.전체 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = ne..

구간 합 구하기 5참고 : https://www.acmicpc.net/problem/11660접근해당 문제는 이차원 배열에서 누적합을 구해서 주어진 구간의 합을 구해야 한다고 생각했습니다.map이라는 N * N 의 2차원 배열에 누적합을 계산해서 저장시간 복잡도 : O(N^2)(i열 , j-1행의 누적합) + (i-1열, j행의 누적합) - (i-1열, j-1행의 누적합) + (i열, j행)i 열 j 행 의 누적합은 아래 식을 통해서 구할 수 있습니다.주어진 구간에서의 합 구하기해당 과정을 통해서 점화식을 구하면 아래와 같습니다.- 코드를 구현할 때는 map, sumMap의 크기를 N+1로 해서 진행.전체 코드package baekjoon_day01;import java.io.*;import java.u..