본문 바로가기

누적합17

[자바] 백준 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.
[자바] 백준 2548 - 대표 자연수 (java) 문제 : boj2548 필요 알고리즘 개념 정렬 데이터를 정렬하는 방법을 알아야 한다. 누적합 누적합을 사용해 이 문제를 풀 수 있다. 수학 - 중앙값(median) 누적합을 사용하지 않고, 수학의 중앙값 개념으로도 이 문제를 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이1 : 누적합 + 카운팅 정렬을 이용한 풀이법 cnt[x]를 입력으로 주어진 N개의 수(1~10000)에 대해, x가 입력으로 들어온 횟수라고.. 2022. 8. 30.
[자바] 백준 10986 - 나머지 합 (boj java) --- 이해하기 어렵게 작성한 것 같아서 새로 작성했습니다. 이 글을 보시는게 더 나을 것 같습니다. --- 문제 : boj10986 i번 까지 누적합을 계산한 값이 arr[i]라고 하자(1 2022. 6. 7.