슬라이딩 윈도우5 [자바] 백준 21921 - 블로그 (java) 목차 문제 : boj21921 필요 알고리즘 슬라이딩 윈도우 또는 누적합 둘 중 하나로 풀면 쉽게 풀 수 있다. 다른 방법들도 많을 것 같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 슬라이딩 윈도우로 풀었다. 그림으로 보면 쉽게 이해될 것 같다. 5 3 1 4 2 5 1 위의 예시의 경우 그림으로 풀이를 그려보면 다음과 같다. 저 X칸짜리 주황색 부분을 옆으로 그대로 움직이듯이 움직이므로 '슬라이딩 윈도우'.. 2023. 3. 13. [자바] 백준 14465 - 소가 길을 건너간 이유 5 (java) 문제 : boj14465 필요 알고리즘 개념 슬라이딩 윈도우, 누적합 알고리즘, 투 포인터 중 하나 세가지 방식 모두 구현이 가능하다. 당연히 다른 방법도 있을 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1부터 N까지 나타낼 수 있는 배열을 만들고, 고장난 신호등은 1, 정상인건 0이라고 하자. 이 경우 연속된 모든 K개의 구간의 합이 곧 해당 구간의 고장난 신호등의 갯수 = 수리해야 하는 신호등의 갯수가 된다.. 2022. 9. 18. [자바] 백준 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. [자바] 백준 10025 - 게으른 백곰 (boj java) 문제 : boj10025 x는 0부터 1000000까지의 좌표값이다. 그리고 [x-k, x+k] 구간내에 있는 얼음의 합을 구할 수 있다면, 모든 구간을 보면서 최대치만 찾으면 된다. 슬라이딩 윈도우 혹은 prefix sum을 계산해서 구하면 된다. prefix sum으로 할 경우, 좌표별로 prefix sum 배열(이하 ps[])을 만들고 이후 좌표 a에서 잡을 수 있는 얼음의 합은 ps[a+k]-ps[a-k-1]가 될 것이다. 따라서 a를 k부터 n-k까지 증가시키면서 각 O(1)로 a 위치에서의 얼음의 합을 구할 수 있으므로 O(|x|) (x의 크기는 1000000)으로 답을 구할 수 있다. 이하 코드는 슬라이딩 윈도우 방식으로 짠 코드이다. 슬라이딩 윈도우도 비슷하다. a를 k부터 n-k까지 증가.. 2022. 5. 14. [자바] 백준 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. 이전 1 다음
