728x90

목록누적합 (3)

mondegreen

[240305] 알고리즘 리부트 24일차 - 백준 17232 자바

[Part1-Chapter05-Clip04] - 백준 17232 생명게임 이전에 푼 구간합 구하기 5의 풀이 과정을 담으면 되는 문제였다. 동일한 문제였지만 *라는 문자로 변경되었다고 누적합을 생각해내지 못해서 강의를 보고 나서야 반영할 수 있었다.. 누적합 배열을 별도로 만들지 않으면 원래 배열에서 변화를 주게되고 그럼 다음 원소를 탐색할 때 변경된 값을 참조하는 큰 문제가 있다. 또한 반복문을 순회하면서 변경사항을 반영하다보면 시간 복잡도가 커지기 때문에 변경되는 부분을 누적합을 먼저 구해주고 한번에 반영하는 것이 시간 초과하지 않는 방법이다. import java.io.*; import java.util.StringTokenizer; public class Main { public static vo..
알고리즘 풀이 및 리뷰/[패캠] 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 리뷰 2024. 3. 6. 00:41
[240303] 알고리즘 리부트 23일차 - 백준 10836 자바

- 백준 10836 여왕벌 누적합을 공부한 덕분에 풀 수 있었던 문제이다. 시간 제한이 있어서 최적화를 요하는 문제였는데 모든 누적합을 매번 계산하는 것이 아니라 태상이의 어쩌고 저쩌고 처럼 시작점과 끝점에서 계산해주고 복원하는 인덱스 접근으로 시간 복잡도를 낮추어서 처리하는 방식을 적용했다. import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static int m, n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStre..
알고리즘 풀이 및 리뷰/백준 2024. 3. 4. 01:22
[240301] 알고리즘 리부트 21일차 - 백준 11659, 11660, 19951 자바

[Part1-Chapter06-Clip01] 구간 합 계산 시 누적합 배열을 활용한다면 해당 인덱스로 접근하여 한 번에 연산이 가능하기 때문에 시간 복잡도가 현저히 낮아진다. 해당 특정 배열의 원소가 갱신된다면 해당 원소의 인덱스부터 그 이후 모든 누적합 원소에 수정이 필요하기 때문에 배열의 길이인 N만큼 순회해야 하므로 시간 복잡도는 O(N) 이다. 만약 갱신하는 것을 반영해 구간합을 구한다면 누적합 배열을 사용한다 하더라도 시간 복잡도가 크게 낮아지지 않는다는 것을 알 수 있다. - 백준 11659 구간 합 구하기 4 한 달 전에도 풀었던 문제인데 시간 초과 때문에 Scanner 대신에 BufferedReader와 StringTokenizer를 사용했고 String 대신 StringBuilder를 사..
알고리즘 풀이 및 리뷰/[패캠] 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 리뷰 2024. 3. 1. 14:03
728x90
이전 Prev 1 Next 다음