4luv1015

https://www.acmicpc.net/problem/1280 1280번: 나무 심기 첫째 줄에 나무의 개수 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 1번 나무의 좌표부터 차례대로 주어진다. 각각의 좌표는 200,000보다 작은 자연수 또는 0이다. www.acmicpc.net 나무를 심을때 기존에 심었던 나무들 각각과의 거리가 비용이 되므로 기존에 심은 나무들 각각으로 인해 생기는 비용을 따로 계산하여 생각해보자 나무를 임의의 수인 a번째로 심었을 때 나무의 위치를 L(a)라고 하자 i번째 나무를 심을 때의 k번째 나무로 인해 생기는 비용을 생각해보면 다음과 같이 세 가지 경우가 존재한다. (kL(i)이면 비용은 L(k)-L(i) 증가 ② L(k)=left&&end>..

https://www.acmicpc.net/problem/14417 14417번: 팰린드롬과 쿼리 2 첫째 줄에 문자열 S가 주어진다. 문자열의 길이는 100,000을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 둘째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 셋째 줄부터 M개의 줄에는 쿼 www.acmicpc.net 쿼리에서 체크해야 될 펠린드롬의 조건은 다음과 같다 ① S의 index번째에서 시작할 것 ② 길이가 적어도 len일 것 쿼리에서 입력받는 index를 i, 길이를 L이라고 할 때 조건 ①은 it1>>t2; t1++; int tmp=query(1,1,N,t2?(t1*2+t2-2):(t1*2-1),N,-t1); if(!t2)tmp++; cout

일반화 세그먼트 트리 구현 - 3. 업데이트와 쿼리 구현 일반화 세그먼트 트리 구현 - 2. 초기화와 생성자 구현 일반화 세그먼트 트리 구현 - 1. 일반화 프로그래밍이란? 평소와 다름없이 stl로 알고리즘 문제를 풀다가 문득 궁금증이 생겼다. stl은 queue, v 4luv1015.tistory.com 저번 글에서 완성한 세그먼트 트리 하나로 원래라면 전혀 다른 종류의 세그먼트 트리를 구현해야했던 2가지 문제를 아주 간단히 풀어보겠다. 1. 구간 합 세그먼트 트리 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다..

일반화 세그먼트 트리 구현 - 2. 초기화와 생성자 구현 일반화 세그먼트 트리 구현 - 1. 일반화 프로그래밍이란? 평소와 다름없이 stl로 알고리즘 문제를 풀다가 문득 궁금증이 생겼다. stl은 queue, vector 등등과 같이 어떤 자료형이든 사용할 수 있게 일 4luv1015.tistory.com 저번 글에 이어서 이번에는 세그먼트 트리의 업데이트와 쿼리 부분을 구현하여 세그먼트 트리를 완성해보았다. 1. 업데이트 업데이트의 구현의 기본적으로 트리 초기화와 크게 다르지 않다. 다만 특정 값을 더하거나 곱한다던지 아니면 아예 다른 값으로 대체한다던지 업데이트의 방식이 그때그때 다르므로 업데이트하는 방식 또한 함수 포인터로 받도록 했다. void update(int idx,vector val,T (..

일반화 세그먼트 트리 구현 - 1. 일반화 프로그래밍이란? 평소와 다름없이 stl로 알고리즘 문제를 풀다가 문득 궁금증이 생겼다. stl은 queue, vector 등등과 같이 어떤 자료형이든 사용할 수 있게 일반화되 있는데 어떻게 이런 것이 가능할까? 언뜻 보기에 4luv1015.tistory.com 저번 글에 이어서 이번에는 세그먼트 트리의 생성자와 초기화 부분을 구현해보았다. 1. 멤버 변수 세그먼트 트리의 구조체를 만든다면 필요한 멤버 변수가 뭐가 있을지 생각해보았다. ① 트리로 사용할 vector ② 쿼리를 처리하기 위해 필요한 원본 배열의 시작점과 끝점의 index ③ 두 구간의 값을 합할 때 사용할 함수의 포인터 따라서 아래와 같이 구조체를 만들어 주었다. template struct seg..

평소와 다름없이 stl로 알고리즘 문제를 풀다가 문득 궁금증이 생겼다. stl은 queue, vector 등등과 같이 어떤 자료형이든 사용할 수 있게 일반화되어 있는데 어떻게 이런 것이 가능할까? 언뜻 보기에 자바의 제네릭과 같은 기능을 하고 있었기에 찾아보니 c++에도 제네릭과 비슷한 template라는 것이 존재했다. 아래는 template의 구조체와 함수 각각에서의 사용 예시이다. #include using namespace std; template struct s { T val; }; //구조체에서의 사용 template T mySum(T a,T b) { return a+b; } // 함수에서의 사용 int main() { s s1={3}; cout