전체 글1068 펜윅 트리(Fenwick tree, BIT) - 기본, 2D, lazy propagation(range update - point query, range update - range query) 목차 ※ References에 적어둔 여러 글을 보며 공부한걸 나중에 까먹지 않기 위해 제가 이해한 내용을 제가 이해한 방식으로 필기 해두는식으로 적은 글 입니다. 그러니 개념을 더 제대로 살펴보시려면 References의 잘써둔 글들을 참고해주세요. 그나마 이 글의 장점이라면 제가 수학에 매우 약하기 떄문에 제가 이해한 방식으로 적어두면 다른 분들은 훨씬 금방 이해하심. 틀린거 있으면 알려주세요! ※ 용어 : 이하 글에서 구간합은 'A부터 B까지의 합', 누적합은 '1부터 N까지의 합', 누적합 알고리즘은 prefix sum 알고리즘을 뜻합니다. ※ 기본적으로 중간 중간에 있는 코드 예시는 c++, java 모두 통용되는 코드로 작성했습니다. 어차피 구현이 간단한 부분들이므로 어떤 언어를 사용하던지 이.. 2022. 8. 15. [자바, 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. [자바, C++] 백준 16975 - 수열과 쿼리 21 (java cpp) 문제 : boj16975 필요 알고리즘 개념 lazy propagation을 적용한 세그먼트 트리 혹은 펜윅 트리 세그먼트 트리 + lazy propagation 혹은 range update가 가능한 펜윅 트리를 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 세그먼트 트리 lazy propagation 혹은 range update 펜윅 트리의 기본형태 문제이다. 펜윅 트리로 풀려면 작성해둔 펜윅 트.. 2022. 8. 15. [자바, C++] 백준 11658 - 구간 합 구하기 3 (java cpp) 문제 : boj11658 필요 알고리즘 개념 다차원 펜윅 트리, 세그먼트 트리 펜윅 트리 혹은 세그먼트 트리를 2차원에 대해 적용할 수 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 다차원 펜윅 트리, 세그먼트 트리 등으로 풀 수 있는 기본형태의 문제이다. 펜윅 트리로 풀려면 작성해둔 펜윅 트리 글에서 '응용 1' 부분을 읽어보면 이 문제를 풀 수 있다. 코드(C++) : github #include #.. 2022. 8. 15. [자바] 백준 24883 - 자동완성 (java) 문제 : boj24883 필요 알고리즘 개념 입력, 출력, 조건문 간단히 입력과 출력을 할 수 있고 조건문을 사용할 수 있으면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 혹시 풀이를 보러 왔다면 위 '자바로 백준 풀 때의 팁 및 주의점'을 읽어보자. 딱히 풀이할건 없을 것 같다. '알파벳 하나'가 주어진다고 했으므로, String으로 입력받은 후 'N'과 'n'을 한번에 확인하기 위해 toLowerCase(.. 2022. 8. 13. [자바] 백준 7578 - 공장 (java) 문제 : boj7578 필요 알고리즘 개념 제곱근 분할법, 펜윅 트리, 세그먼트 트리 등 구간 쿼리 알고리즘(자료구조)를 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 언제 줄이 꼬일지만 찾는다면 어떻게 해결해야할지 알 수 있다. 아래와 같이 식별번호대신 A에 나열되 있던 순서대로 번호를 매겨서 그걸 B에도 동일한 식별번호에 작성해보자. 만약 B가 A와 동일한 순서대로였다면 0-1-2-3-4가 됬을.. 2022. 8. 12. [자바, C++] 백준 2042 - 구간 합 구하기 (java cpp) 문제 : boj2042 필요 알고리즘 개념 펜윅 트리, 세그먼트 트리 등 펜윅 트리, 세그먼트 트리 등 구간 쿼리 알고리즘(자료구조)를 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 펜윅 트리, 세그먼트 트리 등으로 풀 수 있는 기본형태의 문제이다. 펜윅 트리로 풀려면 작성해둔 펜윅 트리 글에서 '기본 : 펜윅 트리' 부분을 읽어보면 이 문제를 풀 수 있다. 코드(C++ 펜윅 트리) : github.. 2022. 8. 12. [자바] 백준 20207 - 달력 (java) 문제 : boj20207 필요 알고리즘 개념 그리디 매번 통하는 일정한 규칙을 정해서, 해당 규칙을 따르면 원하는 답을 구할 수 있는걸 말한다. 보통 엄밀히 증명되기 보다는 '이렇게 하면 될 것 같은데?' 라고 해서 시도해보고 맞는 경우가 많다. 딱히 방법이 정해진 알고리즘이 아니고, 개념적인 거니 알아야 풀 수 있고 그런건 아니다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제는 문제에서 제시된대로 시뮬레이션 문제.. 2022. 8. 12. [자바] 백준 1456 - 거의 소수 (java) 문제 : boj1456 필요 알고리즘 개념 소수 판정, 에라토스테네스의 체 범위 내의 모든 소수를 찾아야 하므로 소수 판정, 더 나아가 에라토스테네스의 체를 알아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 어떤 수가 소수의 N제곱(N>=2) 꼴일 때를 찾아줘야 한다. 이 때 오른쪽 범위 B가 10^14이고 N>=2 이므로 최대 10^7까지의(sqrt(B) 까지 알아야 한다) 모든 소수를 찾아야 함을 알 수 있다... 2022. 8. 12. 이전 1 ··· 55 56 57 58 59 60 61 ··· 107 다음
