WASD BLOG

문제(링크) 문제 설명: 루트가 1인 트리가 하나 주어지고, K개의 industry 도시를 정해야 합니다.(루트도 가능) 각 industry 노드에서 루트까지 최소 경로로 갈 때, 거쳐가는 industry가 아닌 노드(tourism 노드)의 개수가 최대가 되도록 해야 합니다. 풀이: 가장 간단하게 생각하면, 모든 리프 노드가 industry 도시라면 최대가 될 것입니다. 하지만 리프 노드의 개수보다 K 가 크면, 리프가 아닌 노드도 industry 도시가 되야 하므로 그 노드의 자식 노드는 happiness가 1만큼 줄어들게 됩니다. 따라서 리프 노드부터 채워가면서, 자식이 있는 노드를 industry 노드로 추가할 때 자식의 총 개수만큼을 정답에서 빼주어야 합니다. 각 노드들을 다음과 같은 순으로 정렬해 주고, 그리디하게 정답을 구합니다. 노드의 깊이 - 자식의 총 개수 -> 큰 순서로 정렬(각 노드를 추가했을 때 얻을 수 있는 최대 값) 정답이 int 범위를 넘어갈 수 있으므로 주의합니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> #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, K; vector< int > vt[ 200001 ]; vector< int > node; bool visit[ 200001 ]; int child[ 200001 ]; int depth[ 200001 ]; int myC...

문제(링크) 문제 설명: 부수는 비콘을 최소로 하는 문제입니다. 처음엔 한번만 오른쪽부터 연속된 비콘을 부술 수 있습니다. a 포지션의 비콘을 작동시키면 왼쪽으로 b만큼의 비콘이 부숴집니다. 비콘은 오른쪽에서 왼쪽으로 작동시킵니다. 풀이: 1부터 N까지 i번째 비콘을 부수면 몇 개의 비콘이 부숴지는지 계산해 놓습니다. -> 이분 탐색, dp 이용 destroy[i] = i번째 비콘을 부술 때 부숴지는 왼쪽의 전체 비콘 수 이분 탐색으로 다음 범위에서 가장 가까운 position - 1 이 i 번째 비콘을 부쉈을 때 부숴지지 않는 마지막 비콘입니다. destroy[현재] = 범위 내의 비콘 개수 + destroy[부숴지지 않은 마지막 비콘] 다시 1부터 N까지 탐색하면서 (처음엔 부순 비콘 개수) + destroy[now] 의 최솟값을 구합니다. #include<iostream> #include<algorithm> #include<math.h> #include<string.h> #include<string> #include<vector> #include<queue> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define ll long long #define pii pair<int, int> int N; int destroy[ 1000001 ]; //destroy[i] = i position의 비콘이 파괴하는 비콘 수 vector<pii> PL; int lowerBound ( int s, int e, ll v) { while (s < e) { int mid = (s + e) / 2 ; if (PL[mid].first >= v)...

중복 정의 불가능 연산자 멤버 선택자 ( . ) 멤버 객체 선택자 ( .* ) 범위 지정 연산자 ( :: ) 조건 연산자 ( ?: ) sizeof 연산자 중복 가능하지만 헷갈릴 수 있는 연산자 operator& operator&& operator|| operator 중복 정의한 모든 연산자는 파생 클래스로 상속된다.( = 연산자 제외 ) 오버로딩의 제약사항 항 중 하나는 반드시 내가 만든 데이터형이어야 한다. 2항 연산자 -> 2항 연산자 , 1항 연산자 -> 1항 연산자 1항 연산자 -!> 2항 연산자, 2항 연산자 -!> 1항 연산자 연산자 우선순위오 결합순위는 바꿀 수 없다. 연산자 기호를 새로 만들 수 없다. 다음과 같은 함수로 만든다. (데이터 타입) operator연산자 (매개변수); a (연산자) b -> d.operator연산자(b) 와 같은 식으로 해석된다. 단항 연산자 : 형태가 거의 정해져 있다. 전위 연산자 !op, ~op, ++op, --op Type& operator++(); -> 변한 뒤 값을 반환하기 때문에 & 의 형태 후위 연산자 op++, op-- Type operator++(int); -> 변하기 전의 값을 복사했다가 반환 매개변수 int는 의미없는 매개변수 -> 전위 연산자와 구별을 위해 2항 연산자에서 앞에 다른 데이터형이 오는 경우 앞의 데이터를 첫 번째 인자로 받는 operator를 만들어야 한다. -> 전역으로 선언 Type operator연산자 ( (앞의 데이터형) op1, Type op2 ) 전역 함수에서 Type(내가 만든 객체)의 멤버 변수를 쓸 수 있게 하기 위해 -> 프렌드 선언 타입 변환 연산자 operator Type(); 객체를 원하는 Type으로 변환해주는 함수를 만들 수 있다. 객체 내부에 선언.

문제(링크) 문제 설명: N개의 문자열이 주어지고, 각 문자열마다 문자열을 반전시키는 비용도 주어집니다. 문자열을 반전시키거나 반전시키지 않고, 문자열을 사전식으로 정렬해야 할 때, 반전 비용의 최소값을 구하는 문제입니다. 중간에 prefix 관련 설명은 aa aab 위 순서대로 정렬해야 한다는 뜻입니다. 만약 z aa 이라면 -1을 출력해야 합니다. --> compare 함수에서 자동으로 판단해 줍니다. 풀이: 원본 문자열과 반전 문자열 두 개를 준비합니다.(문자열 길이의 총 합이 100000이하이므로 가능합니다.) dp[x][0 or 1] = x번째 문자열에서 이전 문자열을 0 = 반전x , 1 = 반전o 이전 문자열과, 현재 문자열을 반전시키거나 그대로 두면서 재귀 호출합니다. 반전시킬 경우에만 energy값을 더해줍니다. #include<iostream> #include<algorithm> #include<math.h> #include<string.h> #include<string> #include<vector> #include<queue> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define ll long long #define pii pair<int, int> #define MAX 1000000000000000000LL int N; ll energy[ 100001 ]; string str[ 100001 ][ 2 ]; ll dp[ 100002 ][ 2 ]; ll recul ( int now, int order) { if (now == N + 1 ) { return 0 ; } ll& ret = dp[now][order]; ...

문제(링크) 각 정보들을 사전 순서대로 정렬합니다. 정렬된 각 정보들을 공백마다 끊어가며 탐색합니다. 현재까지 탐색된 문자열을 map을 이용해 방문을 체크하고 만약 방문한 곳이면 "--"을 depth에 추가만 하고 더 탐색합니다. 만약 방문하지 않았다면 현재 depth + (현재 층의 문자열) 을 출력 문자열에 추가합니다. 그리고 출력 문자열에 개행 문자를 추가하고, depth 에 "--"을 추가해 층을 늘려줍니다. 모든 문자열에 대해 위 작업을 수행합니다. #include<iostream> #include<algorithm> #include<math.h> #include<string.h> #include<string> #include<vector> #include<queue> #include<map> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> int N; priority_queue<string, vector<string>, greater<string>> pq; map<string, bool > hm; int main ( void ) { FIO; cin >> N; for ( int i = 0 ; i < N; i++) { int x; cin >> x; string all = "" ; for ( int j = 0 ; j < x; j++) { string str; cin >> str; all ...

문제(링크) 볼록 껍질(Convex Hull) 문제였습니다. 다음과 같이 진행합니다. 1. 기준점을 잡는다 -> y 가 가장 작은 점, y 가 같다면 x가 가장 작은 점 2. 점들을 반시계 방향으로 정렬한다. -> CCW를 이용해 기준점, p1, p2를 비교해 세 점이 반시계 방향이라면 True, 시계 방향이라면 False, 일직선일 때 p1이 기준점과 가까우면 True, 멀면 False을 리턴하는 Comparator로 정렬합니다. 3. 정렬된 점들에 대해 그라함 스캔 알고리즘을 사용합니다. - 스택의 마지막 - 1 = first - 스택의 마지막 = second - 현재 비교하는 점 = next 위 세 점 first, second, next에 대해 CCW를 수행합니다. CCW > 0  -> 스택에 next를 넣습니다. CCW <= 0 -> 볼록껍질이 아니므로 이전의 first, second로 되돌리기 위해 스택을 pop 합니다. (이 작업을 CCW > 0 이 될 때까지 수행합니다.) 남은 스택의 크기가 정답이 됩니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<string.h> #include<vector> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> #define pll pair<long long, long long> #define ll long long int N; vector <pll> vt; pll start = make_pair( 100001 , 100001 ); void fi...

문제(링크) 문제 설명: N의 길이 리본이 주어지고, A, B, C의 필요한 리본 길이가 주어집니다. N을 A, B, C 외의 다른 길이가 남지 않게 하면서 가장 많은 리본 조각의 개수를 구해야 합니다. ex) 7 5 5 2 에서 2만큼 3 번 자르면 2,2,2,1 4개의 조각이 남지만, 1의 길이는 필요없는 조각이므로 2,5 만 남게 자르는게 최대값입니다. 풀이: 재귀 호출을 이용하여 풀이했습니다. N부터 주어진 길이만큼 잘라보면서 카운트를 늘려갑니다. now 가 0보다 작아지면 안되므로 걸러줍니다. dp[now]에 now 길이일 때 카운트 값을 넣어주는데, 이미 값이 들어가 있고 그 값이 현재 카운트보다 높거나 같다면 더 탐색할 필요가 없습니다.(걸러줍니다.) 위 작업을 하지 않으면 중복으로 탐색하게 되어 시간이 매우 오래 걸립니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<string.h> #include<queue> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> int N; int P[ 3 ]; int dp[ 4001 ]; void recul ( int now, int cnt) { if (now < 0 ) return ; if (dp[now] >= cnt) return ; dp[now] = cnt; if (now == 0 ) return ; for ( int i = 0 ; i < 3 ; i++) { recul(now - P[i], cnt + 1 ); ...

문제(링크) 풀이: 12865번 평범한 배낭 문제와 같은 냅색 문제였습니다. 냅색 문제에서 배낭의 무게 = 비용, 물건의 가치 = 메모리 로 바꾸어 풀이하면 됩니다. 가치(메모리)가 M 보다 크거나 같을 때 비용을 출력하고 종료합니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<string.h> #include<queue> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> int N, M; int dp[ 10001 ][ 101 ]; int mem[ 101 ]; int cost[ 101 ]; int main ( void ) { FIO; cin >> N >> M; for ( int i = 1 ; i <= N; i++) { cin >> mem[i]; } for ( int i = 1 ; i <= N; i++) { cin >> cost[i]; } for ( int i = 0 ; i <= 10000 ; i++) { for ( int j = 1 ; j <= N; j++) { if (cost[j] <= i) { dp[i][j] = max(dp[i][j - 1 ], dp[i - cost[j]][j - 1 ] + mem[j]); } else { dp[i][j] = dp[i][j - 1 ]; } if (d...

문제(링크) 문제 설명 : N, L, R 이 주어집니다. 2보다 크거나 같은 모든 수 x에 대해 다음 작업을 수행합니다. 왼쪽 = x / 2 중간 = x % 2 오른쪽 = x / 2 가장 마지막엔 0 과 1 로만 구성된 배열이 나오개 되는데, 이때 L번째~R번째에 있는 1의 개수를 구하는 문제입니다. 풀이: 먼저, 가장 간단하게 생각하면 0 과 1 의 최종 배열을 구한 뒤 구간을 돌며 1의 개수를 구하는 법을 생각해 볼 수 있습니다. 하지만 N 값이 2^50 이기 때문에 최종 배열의 길이가 2^50을 훌쩍 넘어갑니다.(최종 배열의 1의 개수는 항상 N개 입니다.) 따라서 배열을 만들지 않고 재귀함수를 이용하여 L, R 구간에 포함될 경우 1의 개수를 카운트하는 식으로 풀이하였습니다.(세그먼트 트리의 탐색과 유사합니다.) 10에 대해 최종 배열까지의 과정을 나타내면 다음과 같습니다. 여기서 각 노드마다 자신의 start, mid, end 값을 지정해줍니다. 즉, 노드 10의 start = 1, mid = 8, end = 15 입니다. 또 왼쪽 노드 5의 start = 1, mid = 4, end = 7 입니다. 이제 각 노드들을 왼쪽, 자기 자신(now % 2) , 오른쪽으로 탐색해가며 leaf노드까지 내려갑니다. R < start || L > end 인 경우 자신의 자식 노드들도 구간에 포함되지 않으므로 더 이상 탐색할 필요가 없어 시간을 단축할 수 있습니다. 또, 자기 자신의 인덱스인 mid도 구간에 포함되는지 여부를 판단하여 더해주어야 합니다. 위 방법을 쓰려면 최종 배열의 총 길이를 알아야 하는데, 위 트리의 대칭성을 이용해 재귀 함수로 구할 수 있었습니다.(getLeng()) #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<strin...