안 쓰던 블로그

www.acmicpc.net/problem/12995 트리나라는 n개의 도시로 이루어져 있고 각 도시 1~n은 모두 연결되어 있다 직원 k명이 전부 이사를 가야 하는데 모든 직원이 서로 다른 도시로 가야 해서 k개의 이사할 도시를 정해야 한다 k개의 도시는 모두 연결되어 있어야 한다 이사할 도시 k개를 고르는 방법의 수를 구하는 문제 k개 도시를 골라야 하면서 전부 연결되어 있어야 하니 다른 트리에서의 dp문제였던 트리의 독립집합이나 사회망 서비스와는 비슷하지만 다른 접근이 필요했다 예를 들어 k=15라고 하면 a, b서브트리에 13을 주고 c서브트리에 2를 줄 수도 있고 a에 2를 주고 b에 12를 주고 c에 1을 주는 방법도 있는 등 다양한 방법이 나올 수 있는데 이걸 어떻게 구현하느냐에 대한 문제였..

www.acmicpc.net/problem/2533 트리의 독립집합 foxtrotin.tistory.com/334 과 유사한 문제 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 아이디어를 받아들인다 모든 사람이 새로운 아이디어를 수용하기 위해 필요한 최소 얼리 아답터의 수를 구하는 문제 친구 관계가 트리이기 때문에 트리에서의 다이나믹 프로그래밍을 할 수 있다 얼리 아답터는 주변 사람에게 영향을 준다. 즉, 얼리 아답터 둘이 붙어 있으면 비효율적이므로 떨어져 있어야 한다 이 말은 어떤 정점이 얼리 아답터라면 그 자식들은 전부 얼리 아답터가 아니라는 의미이기도 하다 하지만 어떤 정점이 얼리 아답터가 아니라면, 그 자식들은 얼리 아답터일 수도, 아닐 수도 있다(적어도 1명은 얼리 아답터..

https://www.acmicpc.net/blog/view/88 펜윅 트리 200% 활용하기 흔히 lazy propagation을 사용하여 푸는 것으로 알려진 이 두 문제는 사실 펜윅 트리만으로 풀 수 있습니다. 구간 덧셈, 포인트 쿼리 다음 연산을 효율적으로 수행하는 자료구조를 만들어 봅시다. 이것으로 16975번 - 수열과 쿼리 21을 풀 수 있습니다. $A_L$, $A_{L+1}$, $\cdots$, $A_R$에 각각 x씩 더한다. $A_k$를 출력한다. $B_1 = A_1$, $B_k = A_k - A_{k-1}$이라고 두면, 각각의 쿼리 www.acmicpc.net https://blog.naver.com/jh05013/221475142152 BOJ 16975부터 16979까지 16975 수열..

this란? -객체 자신의 포인터 -각 객체 속의 this는 다른 객체의 this와 다름 -컴파일러가 묵시적으로 삽입 선언함 -클래스 멤버 함수 내에서만 사용 가능 -static 멤버 함수에서 this 사용 불가 예제를 보면서 하나씩 봅시다 평범한 this 사용 예제 class Book{ int num; public: Book() { this->num=1; } Book(int num) { this->num=num; } void setBooknum(int num) {this->num = num; } }; 1. 객체 자신의 포인터 class Go{ public: Go* f(){ return this; //this는 주소값 } }; f() 함수는 주소값을 반환해야 함 this는 자기 자신의 주소값이니까 thi..