4luv1015

https://www.acmicpc.net/problem/14401 14401번: 악덕 나라 남규 나라의 왕 zych는 도로 정비 계획을 만들고 있다. 남규나라의 도시는 2차원 평면에 존재하며, 각 도시는 (xi,yi)에 위치한다. 새롭게 고속도로를 만들어 모든 도시를 고속도로를 통하여 다른 www.acmicpc.net MST(최소 스패닝 트리)+ CCW(선분 교차 판정) 아무 생각 없이 MST문제인 줄 알고 풀었는데 틀리고 뒤늦게 기하적인 요소가 있다는 걸 깨달았다. 문제의 기본 틀은 MST 변형과 같다. 노드들의 좌표를 받아 모든 간선을 다 계산하고(N^2) 기존에 연결된 간선들에 맞게 유니온 한 뒤 disjoint set의 개수(부모가 자신인 노도의 개수)를 세고 크루스칼 알고리즘을 이용해 그 개수..

https://www.acmicpc.net/problem/25582 25582번: pqbd 천재적인 수학적 재능을 타고난 7살 철수의 영어 교육을 위해 철수의 어머니는 알파벳 소문자 모양 장난감 블럭을 구입하였다. 하지만 철수는 영어 공부보단 알파벳의 생김새에 대한 기하학적 www.acmicpc.net 문제에 나오는 거울 대칭과 점 대칭은 일종의 특수한 조건의 펠린드롬이라고 이해할 수 있다. 그래서 부분 문자열 최장 펠린드롬 알고리즘을 살짝 수정하여 점 대칭과 거울 대칭 각각의 최대 길이를 구하고 둘 중에 큰값을 출력하면 되는 문제이다. 그러나 N>s; len=s.length(); for(int i=0;i

일반화 세그먼트 트리 구현 - 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