문제접근이 문제는 문자열 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..

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

백준 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..