WASD BLOG

문제(링크) 세그먼트 트리 레이지 프로퍼게이션 문제였습니다. TF[now] = 현재 구간에서의 왼쪽->오른쪽 방향의 최장 수열 길이 TB[now] = 현재 구간에서의 오른쪽->왼쪽 방향의 최장 수열 길이 c4[now] = 현재 구간의 4의 개수 c7[now] = 현재 구간의 7의 개수 현재 노드의 최장 수열의 길이를 구하려면 max((왼쪽 노드의 최장 수열 길이 + 오른쪽 노드의 7의 개수), (오른쪽 노드의 최장 수열 길이) + (왼쪽 노드의 4의 개수)) 가 됩니다. 왜냐하면 왼쪽에서 최장 수열의 길이를 이미 구했다고 가정하고, 오른쪽에 7의 개수만 세어주면 되는데, 오른쪽에 4가 오는 경우는 두 번째 조건에서 찾게 됩니다. 즉, 오른쪽에 4가 오는 경우는 (오른쪽 노드의 최장 수열 길이)에 포함되어 있습니다. 마찬가지로 오른쪽 최장 수열 길이를 이미 구했다면 왼쪽에 올 수 있는 건 4밖에 없습니다. 위에서 TF를 구했고, TB는 반대로만 해주면 됩니다. 위 방법만을 이용하면 결과는 TF[1](Root) 에 저장되지만, 시간 초과가 나므로 레이지 프로퍼게이션을 적용해야 합니다. 774 777 위 두개를 자식노드로 하고 있다고 가정해 봅시다. 774의 TB는 3입니다. 4->7->7 이므로 774를 뒤집으면, TF는 3이 나옵니다. 4->4->7 이므로 즉, 뒤집은 다음의 TF는 뒤집기 전 TB와 같습니다. 따라서 774777의 TF를 구하려면 (774의 TB + 777의 4의 개수)와 -- 4의 개수? = 4가 뒤집히면 7이 되므로 같은 방식으로 (777의 TB + 774의 7의 개수) 중 큰 값을 구하면 됩니다. 이제 어떤 노드 n 에 대하여 n의 구간을 모두 뒤집을 때 TF의 값을 구할 수 있었습니다. 같은 방식으로 TB도 구할 수 있습니다. 물론 자신의 c4, c7의 개수도 서로 바꿔 줍니다. 지금까지 구한 게 레이지 프로퍼게이션 중 일부인데, 이제 자식

정적 바인딩 - 컴파일 타임에 호출될 함수를 결정한다. - 객체, 타입을 보고 호출할 함수를 결정한다. 동적 바인딩 - 런 타임에 호출될 함수를 결정한다. - Virtual 을 함수 이름앞에 붙여야 한다.(Base 클래스에만 -> 자식 클래스는 자동으로) ex) 동적으로 할당된 객체가 Base 클래스의 함수를 오버라이딩하여 사용하고 있다면, virtual을 붙이지 않는다면 Base 클래스의 함수만 호출된다. virtual 함수를 사용하는 클래스들은 모두 각각 virtual 테이블을 가지게 된다. virtual 테이블은 각 클래스가 어떤 함수를 호출할 지에 대한 정보를 가지고 있다. (virtual 함수가 너무 많아지면 오버헤드가 생길 수 있다.) ※override 키워드의 역할 : Base 클래스의 함수와 자식 클래스의 override 함수의 형식이 달라질 경우 에러를 발생시킨다.( + Base 클래스에서 final로 선언 시 오버라이딩 불가) 순수 가상 함수 : Base 클래스에서 함수의 body 부분이 없는 함수로, 오로지 오버라이딩을 위해서 틀만 제공해준다. - 함수명 = 0; 과 같이 선언함. 추상 클래스 : 순수 가상 함수를 가지고 있는 클래스로, 객체 생성을 할 수 없다.(순수 가상 함수를 오버라디이 해주어야 함.)

문제(링크) 위 코드에서 반복 횟수는 j의 값에 따라 결정됩니다. 1. 만약 n % j == 0 이라면 n / j 의 값을 결과값에 더해주고, n % j ! = 0 이라면 n / j + 1 의 값을 결과값에 더해주어야 합니다. 하지만 n의 범위가 너무 크므로 횟수를 줄일 방법을 찾아야 합니다. 12 라는 숫자에서, j가 12일 떈 +1을, j 가 6 ~ 11 의 범위 내에선 +2 를 해주면 되고, 4 ~ 5의 범위에선 +3을 해주면 됩니다. 시작 범위(s) > 끝 범위(e) 가 되기 전까지는 위와 같이 계산을 해주면 됩니다. s > e 부터는 이제 e 까지만 반복문을 수행하면 되므로 시간을 단축할 수 있습니다. 1 ~ e 까지 위 1번 과정을 수행해 줍니다. 124를 계산하면 이런 느낌?입니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> #define ll long long #define vi vector<int> #define vl vector<long long> #define vii vector<pii> int n; ll ans; int last = 0 ; int main ( void ) { FIO; cin >> n; int s = n, e = n, d = 1 ; while (s <= e) { ans += (e - s + 1 ) * d; /

문제(링크) 문제 설명: 배열 a가 주어지고, 방 번호(임의의 정수) k에 대해 k -> k + a[k mod n] 으로 옮겨집니다. 즉 k 는 a[k mod n] 만큼 옮겨지게 됩니다. 이 때, 같은 방으로 옮겨진 사람이 있다면 NO 없다면 YES를 출력합니다. 풀이: 먼저 임의의 정수 k 에 대해 k mod n 은 0,1,2 ... n - 1 의 수로 좁혀집니다. n = 4 a = [5,5,5,1] 위 예제에서, k mod n 의 값은 [0,1,2,3] 으로, 배열 a와 각각 (0,5),(1,5),(2,5),(3,1)에 대응합니다. 임의의 정수 k에 대해 k mod n = 0 일 때 k + 5 번째 방으로 이동되겠죠. 그리고, k mod n = 1 일 때 -> 즉 k + 1 은 다시 5를 더한 방인 k + 5 + 1 로 이동됩니다. 즉, k부터 시작한다고 하면, k + 5, k + 5 + 1, k + 5 + 2, k + 1 + 3 ... 이렇게 방을 이동하게 됩니다. k + 1 + 3 다음엔 다시 a[0]으로 돌아가서 k + 5 + 4, k + 5 + 5 ... 이렇게 이어집니다. 즉, a[i] 값은 n번째마다 계속해서 반복되고 맨 마지막 숫자에 mod n을 하게 되면 역시 0,1,2,3 을 반복합니다. 어떤 정수 k를 가져와도 위 식을 계속 반복하게 되므로 0 ~ n-1 까지만 체크하면 됩니다. 즉, (i + a[i]) mod n 을 0 ~ n - 1 까지 수행할 때 겹치는 수가 나오는 지 여부를 체크하면 됩니다. 음수 나머지의 처리를 위해( + n) mod n 을 해줍니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<set> using namespace std; #define FIO

문제(링크) 두 번의 dfs로 해결했습니다. 첫 번째 dfs에선 각 노드마다 그 노드를 root로 했을 때 나올 수 있는 최댓값을 구해 배열에 저장합니다. 두 번째 dfs에선 root노드부터 leaf노드까지 탐색하는데, 부모의 최댓값을 전파하며 내려갑니다. 자식 노드의 최댓값이 0 이상일 경우 -> max(자식 노드의 최댓값, 부모 노드의 최댓값) 을 전파합니다. 자식 노드의 최댓값이 0 보다 작을 경우 -> max(자식 노드의 최댓값 - 1, 부모 노드의 최댓값) 을 전파합니다. (자식 노드의 최댓값이 0보다 작다는 건 아무리 최대여도 -1을 해줘야 한다는 뜻입니다.) #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<queue> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> #define ll long long int N; int color[ 200001 ]; vector< int > vt[ 200001 ]; bool visit[ 200001 ]; int maxV[ 200001 ]; int out[ 200001 ]; int dfs ( int now) { int v = color[now]; for ( int i = 0 ; i < vt[now].size(); i++) { int next = vt[now][i]; if (!visit[next]) { visit[next] = true ; v = max(v, dfs(next) + v);

문제(링크) mass의 크기는 절반으로 쪼개져도 결국 총 합은 같으므로 소수점을 고려할 필요가 없었습니다. 즉, 하루가 지날 때마다 +1 씩 늘어나는 것만 고려하면 됩니다. 박테리아가 가장 최대로 번식할 경우는 1 -> 2 -> 4 -> 8 -> 16 .... 0 1    2    3    4  .... day 위와 같이 증가하는데, 2day엔 최대 7까지 만들 수 있고, 3day엔 최대 15까지 만들 수 있습니다. 즉, N이 어느 구간에 있는지에 따라 day를 고정할 수 있습니다. N 이 8~15 일 땐 3day, 16~31 일 땐 4day 등등... day를 고정하면 그리디하게 풀이할 수 있습니다. 하루가 지날 때마다 현재 박테리아 수를 N에서 뺴주는데, 현재 박테리아 수를 구할 때 둘 중 한가지로 고릅니다. 1. (남은 N) / (남은 일 수) 2. 1에서 구한 박테리아 수를 전 날 박테리아로 만들 수 없을 때 -> 만들 수 있는 최대 박테리아를 구해야 하므로 2를 곱해줍니다. 늘어난 박테리아 - 원래 박테리아를 매번 출력해줍니다. 모든 N에 대해 구할 수 있으므로 -1을 출력할 필요가 없었습니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<queue> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> #define ll long long int T, N; int main ( void ) { FIO; cin >> T; while (T--) { cin >>