세그먼트 트리17 [자바] 백준 18436 - 수열과 쿼리 37 (java) 목차문제 : boj18436 필요 알고리즘세그먼트 트리, 펜윅 트리, 제곱근 분할법위 알고리즘 혹은 자료구조 중 아무꺼나 쓰면 된다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 세그먼트 트리, 펜윅 트리, 제곱근 분할법 등 풀 수 있는 방법은 많다. 아무튼 단일 업데이트, 범위 쿼리를 유효한 시간 내에 처리 가능한 코드를 짜면 된다. 이하 코드는 펜윅 트리를 사용해 풀었다. 펜윅트리에 대한 설명은 '이 글'에서 볼 수.. 2024. 5. 24. [자바] 백준 2835 - 인기도 조사(java) 문제 : boj2835 필요 알고리즘 개념 누적합 알고리즘 약간의 배열 테크닉을 활용하면 누적합 알고리즘 만으로 풀 수 있다. 세그먼트 트리 lazy propagation 또는 range update - range query 펜윅 트리 누적합으로 풀려면 아이디어가 필요하다. 일반적으로는 세그먼트 트리 lazy propagation 혹은 펜윅 트리 응용을 통해 풀게 된다. 이하 풀이는 누적합을 통한 풀이이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도.. 2022. 11. 16. [자바] 백준 14268 - 회사 문화 2 (java) 문제 : boj14268 필요 알고리즘 개념 lazy propagation을 적용한 세그먼트 트리 혹은 펜윅 트리 세그먼트 트리 + lazy propagation 혹은 range update가 가능한 펜윅 트리를 알고 있어야 풀 수 있다. 오일러 경로 테크닉, DFS 알면 생각하기 좋은데, 바로 생각 못할만한 개념은 아니다(내 경우에도 처음 오일러 경로 테크닉을 접했을 때 풀고보니 저런 알고리즘이었다.). 어떠한 노드에서 그 아래로 내려가는 경로들을 1차원으로 펴서 연속된 구간을 생성하는 개념이다. 구할 때 DFS를 사용한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 .. 2022. 11. 4. [자바] 백준 7469 - K번째 수 (java) 문제 : boj7469 필요 알고리즘 개념 정해 : 머지 소트 트리 + 세그먼트 트리 정해는 세그먼트 트리를 응용한 머지 소트 트리로 보인다. 내 경우 : 펜윅 트리 머지 소트 트리를 펜윅 트리로 적용시켜서도 풀 수 있다. 매개 변수 탐색 (parametric search) 이분 탐색의 응용 방법인 매개 변수 탐색이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일반적으로는 대부분 세그먼트 트리에 각 노드를.. 2022. 9. 17. [자바] 백준 13544 - 수열과 쿼리 3 (java) 문제 : boj13544 필요 알고리즘 개념 정해 : 머지 소트 트리 + 세그먼트 트리 정해는 세그먼트 트리를 응용한 머지 소트 트리로 보인다. 내 경우 : 펜윅 트리 머지 소트 트리를 펜윅 트리로 적용시켜서도 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일반적으로는 대부분 세그먼트 트리에 각 노드를 배열로 처리한 머지 소트 트리를 사용해 풀었다. 내 경우엔 아직 세그먼트 트리를 정식으로 공부하지 않았으므로,.. 2022. 9. 17. [자바] 백준 17353(펜윅트리) - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 (java) 문제 : boj17353 필요 알고리즘 개념 세그먼트 트리 lazy propagation 또는 펜윅 트리 개념 세그먼트 트리를 통한 lazy propagation 혹은 range update 펜윅 트리를 알고 있어야 풀 수 있다. 또는 기본 펜윅트리로도 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1 - 펜윅 트리 range update + range query를 통한 풀이 우선 내가 처음 생각한 풀이부터 작.. 2022. 8. 23. [자바] 백준 2517 - 달리기 (java) 문제 : boj2517 필요 알고리즘 개념 세그먼트 트리, 펜윅트리 등의 구간 쿼리 알고리즘 이 문제의 경우 분할 정복을 통해서도 풀 수 있는 것으로 알고 있다. 그리고 또다른 정해로 구간 쿼리 알고리즘을 사용해서도 일반적으로 Inversion Counting이라 불리는 기법으로 풀 수 있다. 정렬 정렬하는 방법을 알아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 자신보다 실력이 좋은 사람은 이길 수 없다는 조건이.. 2022. 8. 18. [자바] 백준 1517 - 버블 소트 (java) 문제 : boj1517 필요 알고리즘 개념 세그먼트 트리, 펜윅트리 등의 구간 쿼리 알고리즘 이 문제의 경우 분할 정복을 통해서도 풀 수 있는 것으로 알고 있다. 그리고 또다른 정해로 구간 쿼리 알고리즘을 사용해서도 일반적으로 Inversion Counting이라 불리는 기법으로 풀 수 있다. 정렬 정렬하는 방법을 알아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 버블 소트의 경우 O(N^2)이 필요하다. 따라서 .. 2022. 8. 17. [자바, C++] 백준 10999 - 구간 합 구하기 2 (java cpp) 문제 : boj10999 필요 알고리즘 개념 lazy propagation을 적용한 세그먼트 트리 혹은 펜윅 트리 세그먼트 트리 + lazy propagation 혹은 range update, range query가 가능한 펜윅 트리를 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 세그먼트 트리 lazy propagation 혹은 range update, range query 펜윅 트리의 기본형태 .. 2022. 8. 15. [자바] 백준 2820 - 자동차 공장 (java) 문제 : boj2820 필요 알고리즘 개념 lazy propagation을 적용한 세그먼트 트리 혹은 펜윅 트리 세그먼트 트리 + lazy propagation 혹은 range update가 가능한 펜윅 트리를 알고 있어야 풀 수 있다. 오일러 경로 테크닉 내 경우엔 이런게 있는줄 모르고 풀고보니 내가 한게 이거였다. 그러니 필요한 알고리즘 개념은 아니다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. a의 모든 부하의.. 2022. 8. 15. 이전 1 2 다음
