누적 합7 [자바] 백준 2571 - 색종이 - 3 (java) 문제 : boj2571 필요 알고리즘 개념 누적 합 (prefix sum) 2차원 누적합 문제인데, 빈 공간을 포함하지 않기 위한 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우 누적합 알고리즘으로 O(N^4)으로 풀었다. 다만 실제로 N^4은 아니고, 약간의 백트래킹도 포함되었고, 한쪽 방향으로 탐색 범위를 고정했으므로 4중 반복문이긴 하지만 N^4보단 낮다. 우선 2차원 누적합 알고리즘으로 직.. 2023. 1. 10. [자바] 백준 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. [자바, 코틀린] 백준 17390 - 이건 꼭 풀어야 해! (java, kotlin) 문제 : boj17390 필요 알고리즘 개념 누적 합 (prefix sum) 연속된 범위의 합을 O(1)로 구하기 위해 누적 합을 사용한다. 누적 합에 대한 개념이 있어야 풀 수 있다. 정렬 정렬이 무엇인지, 자바나 코틀린으로 정렬은 어떻게 하는지 알아야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 비내림차순으로 정렬해야 한다. 비내림차순이 생소할 수 있다. 그냥 이 문제에서는 오름차순이라고 생각하면 된.. 2022. 8. 8. [자바] 백준 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. [자바] 백준 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. 백준 2003 자바 - 수들의 합 2 (BOJ 2003 JAVA) 문제 : boj2003 우선 i번째 수 부터 j번째 수까지의 합을 쉽게 알 수 있는 방법을 생각해보자. 누적합을 미리 구해둔다면 O(1)에 i번째 수부터 j번째 수까지의 합을 구할 수 있다. 예를들어 '4 7 2 1'을 확인해보자. 다음과 같이 누적합 배열(arr)을 마련해두면, i번째부터 j번째 수까지의 합은 arr[j]-arr[i-1]로 O(1)에 바로 구할 수 있다. 그럼 이제 합이 m이 되는 경우의 수를 구해야 한다. 더 효율적으로 하려면 투 포인터 개념을 활용하면 되지만, 이 문제의 경우 그냥 모든 경우를 확인하면 된다. 즉 i=1일 때 j=i~n의 모든 경우, i=2일 때 j=i~n의 모든 경우, ... i=n일 때 j=i~n인 모든 경우를 다 보면 된다. 코드 : github import j.. 2022. 3. 23. 백준 2143 자바 - 두 배열의 합 (BOJ 2143 JAVA) 문제 : boj2143 1. 부 배열을 이따 생각하고, 일단 X랑 Y라는 두 배열이 있는데 두 배열의 각 원소를 하나씩 더한 합이 T가 되는 경우부터 생각해보자. 아래와 같은 X, Y 배열이 있다. 1.1 가장 간단히 X[i] + Y[j] 가 T가 되는걸 찾는 방법은 모든 X의 원소에 대해 Y의 모든 경우의 수를 전부 확인해보면 된다. X[0]+Y[0] 확인, X[0]+Y[1] 확인, ... , X[1]+Y[0] 확인, X[1]+Y[1]확인, ... X[2]+Y[3] 확인. 이 경우 X의 개수 * Y의 개수 만큼 봐야 한다. O(XY) 1.2 1.1보다 더 빠르게 할 수 있는 방법이 있다. Y를 정렬한 후 O(YlogY), 각 X에 대해 T-X[i]가 Y에 있는지를 이분탐색으로 찾는 방식이다. 이 경우 .. 2021. 12. 13. 이전 1 다음
