Prefix Sum28 [자바] 백준 23827 - 수열 (Easy) (java) 문제 : boj23827 필요 알고리즘 개념 누적 합 (prefix sum) 누적 합 개념을 알고 있으면 더 편하게 풀 수 있다. 기본적인 수학 수식을 편한 방식으로 짤 수 있도록 바꿀 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N=4에 대해 A1, A2, A3, A4를 생각해보자. i=1에 대해, A1*A2+A1*A3+A1*A4 = A1(A2+A3+A4) 이다. 마찬가지로 i=2에 대해, A2(A3+A.. 2022. 8. 19. 누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java 목차 ※ 배열의 인덱스는 알다시피 0부터 시작한다. 예를들어 N개의 데이터가 있다면 0번 인덱스부터 N-1번 인덱스까지 존재한다. 다만 구현에 있어 누적 합을 구현할 때는 인덱스 1번부터 사용하는게 훨씬 편하다. 즉, N개의 데이터가 존재할 경우, N+1크기의 배열을 만든 후 1번 인덱스부터 N번 인덱스까지를 사용하는게 구현하기 편하다. 따라서 이하 글에서는 후자의 방식을 사용해 서술한다. ※ 코드는 자바 기준으로 작성했지만, 어려운 코드가 아니므로 다른 언어 사용자도 문제없이 볼 수 있어요. 누적 합 (prefix sum) 1. 반복문으로 구간 합을 구할때의 문제점 특정 구간의 합을 구하는 경우를 생각해보자. 예를들어 백준의 구간 합 구하기 4 문제를 보자. 최대 10만개짜리 배열에서, 최대 10만개의.. 2022. 8. 9. [자바, 코틀린] 백준 17390 - 이건 꼭 풀어야 해! (java, kotlin) 문제 : boj17390 필요 알고리즘 개념 누적 합 (prefix sum) 연속된 범위의 합을 O(1)로 구하기 위해 누적 합을 사용한다. 누적 합에 대한 개념이 있어야 풀 수 있다. 정렬 정렬이 무엇인지, 자바나 코틀린으로 정렬은 어떻게 하는지 알아야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 비내림차순으로 정렬해야 한다. 비내림차순이 생소할 수 있다. 그냥 이 문제에서는 오름차순이라고 생각하면 된.. 2022. 8. 8. [자바] 백준 10986 - 나머지 합 (boj java) --- 이해하기 어렵게 작성한 것 같아서 새로 작성했습니다. 이 글(링크)을 보시는게 더 나을 것 같습니다. --- 문제 : boj10986 i번 까지 누적합을 계산한 값이 arr[i]라고 하자(1 2022. 6. 7. [자바] 백준 2559 - 수열 (boj java) 문제 : boj2559 이하 설명에서 arr[i]는 입력으로 주어진 i번째 수를 뜻한다. 총 세 가지 방식으로 풀이를 진행한다. 1. 누적합 (prefix sum) prefix sum (누적합)을 미리 구해둬보자. 누적합 배열을 sumArr이라고 하고, sumArr[i]는 arr[1]+arr[2]+...+arr[i] 라고 하자. 그렇다면 sumArr[i] = arr[i] + sumArr[i-1]이 될 것이다. 이렇게 누적합 배열을 구해둔다면, 이후 아래의 공식을 통해 각각 O(1)로 arr[i]부터 이전 K개의 합을 구할 수 있다. 따라서 O(N)으로 답을 구할 수 있다. 코드1 : github - prefix sum import java.io.BufferedReader; import java.io.In.. 2022. 5. 27. [자바] 백준 11660 - 구간 합 구하기 5 (boj java) 문제 : boj11660 prefix sum을 이용하는 문제이다. 1차원 배열에 대해 prefix sum을 계산해두면 1차원 배열의 모든 구간에 대한 구간합을 O(1)로 구할 수 있다. 따라서 모든 행에 포함된 열에 대해 행의 개수만큼 prefix sum을 계산해둔다면, O(MN)으로 문제를 풀 수 있다. 이렇게 짠 코드는 여기(github)에 있다. 이하 풀이는 2차원 prefix sum을 사용한 풀이이다. 2차원 배열에 대해 prefix sum을 유지한다면 O(M)으로도 가능하다. arr[a][b]를 (1, 1)부터 (a, b) 까지의 합이라고 정의하자. 그럼 arr[a][b] = '[a. b]의 값' + arr[a-1][j] + arr[a][b-1] - arr[a-1][b-1] 이라고 할 수 있다... 2022. 5. 26. [자바] 백준 18221 - 교수님 저는 취업할래요 (boj java) 문제 : boj18221 문제 제목이 상당히 무섭고, 지문이 길긴 하지만 정리해보면 결국 알아야 하는건 어렵지 않다. 알아내야 하는걸 정리해보자. 1. 성규가 앉은 위치의 좌표 2. 교수님이 앉은 위치의 좌표 3. '1'과 '2'의 거리가 5이상인지 4. '1'과 '2'로 만들어지는 직사각형 혹은 선 위에 몇 명의 학생이 있는지 위와 같이 알 수 있으면 풀 수 있다. '1'과 '2'는 입력을 받으면서 알 수 있다. '3'은 문제에서 제시된 공식으로 알 수 있다. 다만, double로 처리하는건 항상 소수점 오차의 문제가 생길 가능성이 있다. 따라서 아래와 같이 공식을 바꿔서 int내에서 처리가 되도록 하자. 이하의 조건을 만족하지 않는다면 바로 0을 출력하고 종료하면 된다. '4'의 경우엔 결국 직사각형.. 2022. 5. 24. [자바] 백준 5591 - 最大の和 (boj java) 문제 : boj5591 n개의 데이터에서 연속된 k개의 합이 최대인 지점을 찾으면 된다. 두 가지 정도로 해볼 수 있다. 이하 예시는 다음 입력을 이용해 설명하겠다. 5 3 2 5 -4 10 3 1. 슬라이딩 윈도우 처음 k개의 합을 구한다(A). k개의 윈도우를 옆으로 옮겨다니듯이 생각하면 된다. 그럼 윈도우를 우측으로 한 칸 이동한다면, 직전 윈도우 위치의 첫번째 위치의 값을 빼고 이번에 새로 추가된 값을 더해주면 된다. 이런식으로 이동하면서 최대값을 구하면 된다. O(N) 2. prefix sum 입력을 받을 때 미리 누적합을 계산해둔다. 그렇다면 i번 인덱스에서 이전 k개 원소들의 합은 arr[i]-arr[i-k]가 된다. 이걸 i를 k부터(그래야 i-k가 0 미만으로 안내려갈테니) n까지 증가시.. 2022. 5. 12. 백준 17550 자바 - Inquiry I (boj 17550 java) 문제 : boj17550 prefix sum (누적합)을 안다면 쉽게 풀 수 있다. 누적합 배열을 하나는 n개를 원래 값 대로, 하나는 n개를 제곱해서 합한 누적합 배열을 만든다. 전자를 a, 후자를 b라고 하겠다. 그럼 이후 특정 범위의 합을 O(1)로 알 수 있으므로, b[i] * (a[n]-a[i])에 대해 i를 1부터 n까지 진행하면서 가장 큰 값을 찾으면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputS.. 2022. 4. 18. [종만북] FESTIVAL - 록 페스티벌 (자바 java) 문제 : FESTIVAL N이 최대 1000 이므로 O(N^2)의 알고리즘이라도 충분히 통과할 수 있다. 따라서 단순히 차이가 L 이상인 모든 구간에 대해 O(N^2)으로 확인해주면 된다. (코드의 24~25 line 참고) 주의점은 10^(-7) 이하의 절대/상대 오차가 있어야 하므로, 그냥 바로 출력하면 안되고 소수점 8자리 이상을 출력하도록 해야 한다. 자바의 경우 String.format("%.8f", answer)과 같은 코드로(c언어와 비슷한 출력 방식) 소수점 8자리까지 출력할 수 있다. 그리고 모든 구간에 대해 직접 더해봐도 시간 제한에 충분히 맞출 수 있긴 하지만(O(N)), prefix sum을 미리 구해둘 경우 [a, b] 구간의 합은 arr[b]-arr[a-1] 과 같이 O(1)로 .. 2022. 4. 5. 이전 1 2 3 다음
