우선 내가 작성한 코드이다. import java.io.*; public class P2851 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int i = 10; int[] numArr = new int[i]; int[] prefixSum = new int[i+1]; for(int j = 0; j = ..
이 문제는 1차원 배열을 입력 받고, 단순히 가장 큰 값을 찾는 것이 아닌, 배열의 요소들중에서 가장 큰 값을 찾는 것이다. 일단 각 요소들의 합을 계산하기 위해서, 간단히 1차원 배열의 누적합을 구현한다. 그 이후, 서브 배열의 요소중 가장 큰 값을 구해야 하는데, 나는 위와 같이, 최대 길이에서, 1개씩 줄여가면서 max를 구하고 대입하는 방식으로 했다. 이번 문제는 배열의 길이가 1000이하라서 이런 알고리즘으로 구현이 됐지만, 내가 작성한 위 코드는 시간 복잡도가 O(T*N^2)이므로 효율적인 알고리즘이 아니다. 다이나믹 프로그래밍?을 공부하면 시간 복잡도를 효율적으로 코드를 짤수 있다는데, 나중에 공부하고 코드를 바꿔보는 식으로 해야겠다. import java.io.*; import java.u..
이번 문제는 간단한 2차원 배열의 누적합을 구현하는 문제이다. 이 문제를 구간 합 구하기라는 문제에서 구현해본 적이 있지만 복습할 겸 다시 풀어보았다. 우선 기본적인 수를 입력 받는 방법이나 변수 선언, 누적합 기본 로직에 대해선 언급하지 않을 예정이다. import java.io.*; import java.util.StringTokenizer; public class P2167 { static int[][] matrix; static int[][] prefixSum; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..
누적합을 2D에서도 적용시킬 수 있다. 이번 문제를 말로 설명하기엔 제약이 있을 거 같다. 따라서 유튜브와 같은 곳에서 이런 문제와 관련된 걸 찾아보는 걸 추천한다. 일단 이 문제는 규칙만 알아내면 정말 별거 없었다. 이 문제 역시 누적합 배열을 만들 때, 한칸 씩 더 만들어주면 예외가 뜨는걸 쉽게 막을 수 있다. 따라서 x,y 한칸 씩 더 만들어줬고, 이차원 배열에 누적합을 만드는 방법은 자신의 윗 배열 값과 왼쪽 배열의 값을 더한 후, 대각선 배열의 값을 빼고, 마지막으로 자신의 위치의 값을 더하는 방식으로 하면 이차원 누적합 배열을 만들 수 있다. 이런 문제를 풀지 않았다면 이 말이 잘 이해가 안갈 수 있으므로, 노트에 그려보면서 이해해보는걸 추천한다. 위 공식이 이차원 누적합 배열을 만드는 방법이..
쉬운 문제이므로 설명은 생략한다. import java.io.*; import java.util.StringTokenizer; public class P11441 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] numArr = new int[N]; int[] preSum = new int[N+1]; StringTokenizer st = new StringTokenizer(br.readLine()," "); for(int i = 0..
이번 문제는 50점까지밖에 구현하지 못했다.. 따라서 누적합 문제를 더 풀다가, 나중에 다시 풀어야겠다. import java.io.*; import java.util.StringTokenizer; public class P16139 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력 받은 문자열을 문자 배열 String source = br.readLine().trim(); // 누적합을 저장할 배열 int[] prefixSum = new int[source.length()+1]; // 질문 횟수 > 즉..
나는 오늘 누적합을 오늘 처음 풀어봤는데 앞전 문제에서도 그렇고 알고리즘 능력이 올라갔다는 생각이 들었다, 내 생각에 누적합은 확실히 매우 효율적이라는거다. package Algo.Queue; import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class S2558 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " ..
이번 문제는 누적합을 이용하여 문제를 풀어야 한다. 누적합이란 한번에 입력값들의 합을 저장하고 필요한 부분만 골라 쓰는거 라고 생각하면 된다. import java.util.Scanner; public class S11659 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); StringBuilder sb = new StringBuilder(); int N = sc.nextInt(), M = sc.nextInt(); int[] numArr = new int[N]; int[] preSum = new int[N+1]; for(int i = 0; i < N; i++) { numArr[i] = sc.nextInt(); p..
