mondegreen

[Part1-Chapter05-Clip04] - 백준 17232 생명게임 이전에 푼 구간합 구하기 5의 풀이 과정을 담으면 되는 문제였다. 동일한 문제였지만 *라는 문자로 변경되었다고 누적합을 생각해내지 못해서 강의를 보고 나서야 반영할 수 있었다.. 누적합 배열을 별도로 만들지 않으면 원래 배열에서 변화를 주게되고 그럼 다음 원소를 탐색할 때 변경된 값을 참조하는 큰 문제가 있다. 또한 반복문을 순회하면서 변경사항을 반영하다보면 시간 복잡도가 커지기 때문에 변경되는 부분을 누적합을 먼저 구해주고 한번에 반영하는 것이 시간 초과하지 않는 방법이다. import java.io.*; import java.util.StringTokenizer; public class Main { public static vo..

[Part1-Chapter06-Clip01] 구간 합 계산 시 누적합 배열을 활용한다면 해당 인덱스로 접근하여 한 번에 연산이 가능하기 때문에 시간 복잡도가 현저히 낮아진다. 해당 특정 배열의 원소가 갱신된다면 해당 원소의 인덱스부터 그 이후 모든 누적합 원소에 수정이 필요하기 때문에 배열의 길이인 N만큼 순회해야 하므로 시간 복잡도는 O(N) 이다. 만약 갱신하는 것을 반영해 구간합을 구한다면 누적합 배열을 사용한다 하더라도 시간 복잡도가 크게 낮아지지 않는다는 것을 알 수 있다. - 백준 11659 구간 합 구하기 4 한 달 전에도 풀었던 문제인데 시간 초과 때문에 Scanner 대신에 BufferedReader와 StringTokenizer를 사용했고 String 대신 StringBuilder를 사..