Prefix Sum28 [자바] 백준 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. [자바] 백준 1048 - 유니콘 (java) 문제 : boj1048 필요 알고리즘 개념 다이나믹 프로그래밍 (DP, 동적계획법) 대부분의 경우의 수 문제는 DP로 풀 수 있다. 이 문제도 DP로 풀 수 있다. 누적합 유니콘의 이동 범위 내의 누적합을 구하기 위해 2차원 누적합을 사용하면 빠르다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제 설명이 약간 부족한데, 시작은 어느지점에서 해도 된다! 이것때매 좀 헷갈렸다. 우선 DP를 어떤식으로 진행하는지는 알아야.. 2023. 3. 2. [자바] 백준 2571 - 색종이 - 3 (java) 문제 : boj2571 필요 알고리즘 개념 누적 합 (prefix sum) 2차원 누적합 문제인데, 빈 공간을 포함하지 않기 위한 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우 누적합 알고리즘으로 O(N^4)으로 풀었다. 다만 실제로 N^4은 아니고, 약간의 백트래킹도 포함되었고, 한쪽 방향으로 탐색 범위를 고정했으므로 4중 반복문이긴 하지만 N^4보단 낮다. 우선 2차원 누적합 알고리즘으로 직.. 2023. 1. 10. [자바] 백준 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. [자바, C++] 백준 11659 - 구간 합 구하기 4 (java cpp) 문제 : boj11659 필요 알고리즘 개념 누적합 알고리즘 (prefix sum) 누적합 알고리즘을 사용해 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 누적합 알고리즘의 가장 기본이 되는 문제이다. 설명은 적어둔게 있으므로, 누적합 알고리즘을 모른다면 이 글을 읽어보고 풀면 바로 풀 수 있다. 코드 (Java) : github import java.io.BufferedReader; import ja.. 2022. 9. 10. [자바] 백준 2548 - 대표 자연수 (java) 문제 : boj2548 필요 알고리즘 개념 정렬 데이터를 정렬하는 방법을 알아야 한다. 누적합 누적합을 사용해 이 문제를 풀 수 있다. 수학 - 중앙값(median) 누적합을 사용하지 않고, 수학의 중앙값 개념으로도 이 문제를 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이1 : 누적합 + 카운팅 정렬을 이용한 풀이법 cnt[x]를 입력으로 주어진 N개의 수(1~10000)에 대해, x가 입력으로 들어온 횟수라고.. 2022. 8. 30. 이전 1 2 3 다음
