누적합23 [자바] 백준 2015 - 수들의 합 4 (java) 목차 문제 : boj2015 필요 알고리즘 누적 합 (prefix sum), 해시를 사용한 집합과 맵 (hashmap) 누적합과 해시를 사용해 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제에서 A배열에서 1부터 X번까지의 누적합을 f(x)라 해보자. 즉 f(x)는 다음과 같다. 이 때 1 2024. 4. 3. [자바] 백준 30646 -최대 합 순서쌍의 개수(java) 목차 문제 : boj30646 필요 알고리즘 누적 합(prefix sum), 해시를 사용한 집합과 맵 누적합과 해시맵을 사용해 풀 수 있다. 물론 언제나 다른 방법들도 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 누적합을 모른다면 '누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java' 글을 보자. 이 문제를 풀기위한 로직을 생각해보면 다음을 알 수 있어야 한다.. 2023. 12. 6. [자바] 백준 11066 - 파일 합치기 (java) 목차 문제 : boj11066 필요 알고리즘 다이나믹 프로그래밍 (DP, 동적 계획법), 누적합 분할정복 느낌으로 생각해보면 풀이법을 찾을 수 있다. 그리고 구현을 위해 DP와 누적합을 사용해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선, 이 문제의 경우 연속된 파일끼리만 합칠 수 있다는 점을 주의해야 한다. 만약 아무 파일이나 합칠 수 있었다면 그리디로 매번 합쳐진 파일들 중 가장 가중치가 낮은 2개를 합치.. 2023. 8. 10. [자바] 백준 21921 - 블로그 (java) 목차 문제 : boj21921 필요 알고리즘 슬라이딩 윈도우 또는 누적합 둘 중 하나로 풀면 쉽게 풀 수 있다. 다른 방법들도 많을 것 같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 슬라이딩 윈도우로 풀었다. 그림으로 보면 쉽게 이해될 것 같다. 5 3 1 4 2 5 1 위의 예시의 경우 그림으로 풀이를 그려보면 다음과 같다. 저 X칸짜리 주황색 부분을 옆으로 그대로 움직이듯이 움직이므로 '슬라이딩 윈도우'.. 2023. 3. 13. [자바] 백준 1048 - 유니콘 (java) 문제 : boj1048 필요 알고리즘 개념 다이나믹 프로그래밍 (DP, 동적계획법) 대부분의 경우의 수 문제는 DP로 풀 수 있다. 이 문제도 DP로 풀 수 있다. 누적합 유니콘의 이동 범위 내의 누적합을 구하기 위해 2차원 누적합을 사용하면 빠르다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제 설명이 약간 부족한데, 시작은 어느지점에서 해도 된다! 이것때매 좀 헷갈렸다. 우선 DP를 어떤식으로 진행하는지는 알아야.. 2023. 3. 2. [자바] 백준 25822 - 2000문제 푼 임스 (java) 문제 : boj25822 필요 알고리즘 개념 누적 합(prefix sum) 내 경우엔 이걸 메인 아이디어로 사용했다. 문제 태그에 없긴하다. 투 포인터 (two pointer) 누적합을 사용한 아이디어에 대해 시간복잡도를 줄이기 위해 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 누적합을 사용해 특정 구간에 대해 스트릭이 유지됬다고 가정할 때 필요한 스트릭 프리즈의 수를 O(1)로 알 수 있게 하는게 메.. 2022. 12. 15. [자바] 백준 2835 - 인기도 조사(java) 문제 : boj2835 필요 알고리즘 개념 누적합 알고리즘 약간의 배열 테크닉을 활용하면 누적합 알고리즘 만으로 풀 수 있다. 세그먼트 트리 lazy propagation 또는 range update - range query 펜윅 트리 누적합으로 풀려면 아이디어가 필요하다. 일반적으로는 세그먼트 트리 lazy propagation 혹은 펜윅 트리 응용을 통해 풀게 된다. 이하 풀이는 누적합을 통한 풀이이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도.. 2022. 11. 16. [자바] 백준 10986 - 나머지 합 (java) 문제 : boj10986 필요 알고리즘 개념 수학, 누적 합 수학적 사고를 통해 어떻게 구할 수 있을지 생각할 수 있어야 한다. 내 경우엔 해당 풀이를 구현하기 위해 누적합 알고리즘을 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 필요 개념 이하 풀이에는 누적합 알고리즘이 필요하므로 모른다면 이 글을 참고하자. 2차원 누적합까진 안봐도 된다. 또 이 문제를 풀기 위해 알고있어야 하는 법칙이 있다. 나머지를 가지고 노는 .. 2022. 10. 20. [자바] 백준 14465 - 소가 길을 건너간 이유 5 (java) 문제 : boj14465 필요 알고리즘 개념 슬라이딩 윈도우, 누적합 알고리즘, 투 포인터 중 하나 세가지 방식 모두 구현이 가능하다. 당연히 다른 방법도 있을 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1부터 N까지 나타낼 수 있는 배열을 만들고, 고장난 신호등은 1, 정상인건 0이라고 하자. 이 경우 연속된 모든 K개의 구간의 합이 곧 해당 구간의 고장난 신호등의 갯수 = 수리해야 하는 신호등의 갯수가 된다.. 2022. 9. 18. [자바, C++] 백준 11659 - 구간 합 구하기 4 (java cpp) 문제 : boj11659 필요 알고리즘 개념 누적합 알고리즘 (prefix sum) 누적합 알고리즘을 사용해 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 누적합 알고리즘의 가장 기본이 되는 문제이다. 설명은 적어둔게 있으므로, 누적합 알고리즘을 모른다면 이 글을 읽어보고 풀면 바로 풀 수 있다. 코드 (Java) : github import java.io.BufferedReader; import ja.. 2022. 9. 10. 이전 1 2 3 다음
