WASD BLOG

C++ 에서 unique_ptr, shared_ptr, weak_ptr 세 가지 종류의 스마트 포인터가 추가됨. <memory> 헤더 파일에 저장되어 있음. 따로 delete를 해주지 않아도 해당 객체가 scope를 벗어나면 자동으로 메모리가 해제된다. **scope를 벗어난다 = 지역 변수가 함수가 끝나 사라진다. 1. unique_ptr : 한번 선언된 객체를 다른 포인터가 가르킬 수 없음. 선언 unique_ptr<int> p(new int(5)); unique_ptr<int> p = make_unique<int>(5); 메소드 get() : 가르키는 주소를 반환. reset() : 인자x = null포인터로 변환, 인자o = 새로운 값을 가르킴. release() : 유니크 포인터를 다른 포인터 변수에게 넘겨주고, 유니크 포인터는 null로 바뀌게 됨. 2. shared_ptr : 하나의 객체에 대한 포인터 대입이 일어날 때마다 카운트가 증가함, scope를 벗어날 때마다 카운트가 감소, 카운트가 0이 되면 객체 삭제. 선언 shared_ptr<int> p(new int(5)); --> 카운터 변수의 메모리가 별개로 존재. shared_ptr<int> p = make_shared<int>(5); --> 카운터 변수와 객체 같이 컨트롤. 메소드 use_count() : 카운트 값을 반환. get() : 위와 동일 reset() : 포인터가 끊어지지만 카운트가 0이 아닌 이상 해당 객체가 사라지진 않음. 서로가 서로를 참조하는 순환 참조의 경우 카운트가 0이 되지 않아 메모리를 해제할 수 없는 단점이 있다. 3. weak_ptr : shared_ptr의 순환 참조를 피하기 위해 shared_ptr을 감시(?)하는 포인터. 선언 shared_ptr<int> p(s_ptr) --> s_ptr은 미리 선

학교 강의를 들으면서 or 공부하면서 새롭게 알게 된 내용 정리. 1. 컴파일 시 xxx vs 런타임 시 xxx ( const 와 constexpr 에 대해) - 컴파일 시 : 코드를 실행하기 전, 컴파일 과정에서 이루어져야(조건이 만족되야?) 한다. ex) constexpr 의 경우 constexpr int x = 3 * a; <-- 처럼 a에 어떤 수가 들어올 지 모르기 때문에 빌드 시 오류가 발생한다.(즉, 컴파일 시 값을 알고 있어야 함.) - 런타임 시 : 코드를 실행해서 프로그램이 돌아가는 과정에 조건이 만족되면 된다. ex) const 의 경우 const int x = 3 * a; <-- 처럼 a에 어떤 수가 들어올 지 모르지만 실행과정에 알 수 있게 되므로 오류가 나지 않는다.(즉, 컴파일 시 값을 몰라도 됨.) 2. 1) 맵은 iterator로 for(auto& i : m) 를 통해 각 객체를 가져올 수 있다. i 에 pair가 담기게 됨. 2) cin의 EOF 처리 = while(cin >> s) 로 하면 EOF를 만나면 false를 반환한다. 3. 동적 메모리 할당 데이터타입* 포인터변수 = new  데이터타입 메모리 반납 : delete 포인터변수 delete 시 주의 사항 1) 할당받지 않은 메모리를 delete 시 오류 2) 이미 반환한 메모리를 다시 delete 시 오류 new 로 배열 초기화 시 int* arr = new int[5]{1,2,3,4,5} 와 같이 초기화한다. (배열의 크기를 생략하면 안됨.) n차원 배열을 동적할당 시 가장 높은 차원부터 낮은차원 순으로 할당, delete 시엔 반대의 순서로 반환한다. int (*arr)[b] = new int[a][b]; --> x ( 왼쪽은 정적으로 표현되어야 함.) int (*arr)[4] = new int[a][4]; --> o 4. 메모리 누수 체크 #ifdef DEBUG #i

문제(링크) 문제 설명: N개의 숫자를 세 부분으로 나눴을 때 나눈 3개의 부분의 합이 모두 같을 경우의 수를 구하는 문제입니다. 풀이: 만약 세 구간이 위 조건을 만족한다면 다음과 같이 나타낼 수 있습니다. 1. 첫 번째 구간의 합 = A 2. 처음부터 두 번째 구간의 끝까지의 합 = 2A 3. 처음부터 세 번째 구간의 끝까지의 합 = 3A 위에서 3번의 경우는 N개의 수에 대해 prefix sum을 구했을 때 sum[N] 으로 나타내어 집니다. 즉, sum[N]이 3의 배수일 경우에만 조건을 만족할 수 있습니다. sum[N]이 3의 배수일 경우부턴 다음과 같은 패턴을 찾습니다. (A = sum[N] / 3 으로 구할 수 있습니다.) 맨 왼쪽부터 prefix sum을 탐색하면서 A , 2A , 3A 의 순서인 경우의 수를 세어주면 됩니다. #include<iostream> #include<string> #include<algorithm> #include<math.h> #include<vector> #include<queue> #include<stdio.h> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define pii pair<int, int> int N; long long sum[ 500001 ]; int main ( void ) { FIO; cin >> N; for ( int i = 1 ; i <= N; i++) { long long v; cin >> v; sum[i] = sum[i - 1 ] + v; } if (sum[N] % 3 == 0 )

문제(링크) 문제 설명: 배열의 총 합보다 자기 자신이 아닌 연속된 부분 배열의 합이 총 합보다 크거나 같으면 "NO", 아니라면 "YES"를 출력합니다. 풀이: 왼쪽과 오른쪽에서 부터 각각 prefix sum을 구하여 0보다 작거나 같아질 때가 "NO" 입니다. prefix sum이 0이하가 된다는 의미는 그 감소하는 구간이 없었다면 기존의 총합이 더 커질 수 있었다는 의미입니다. 따라서 감소하는 구간을 제외한 부분 배열이 총합보다 커지는 구간이 반드시 존재합니다. #include<iostream> #include<string> #include<algorithm> #include<math .h=""> #include<vector> #include<queue> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int int=""> int T, N; long long arr[ 100000 ]; int main ( void ) { FIO; cin &gt;&gt; T; while (T--) { cin &gt;&gt; N; long long sum = 0 ; for ( int i = 0 ; i &lt; N; i++) { cin &gt;&gt; arr[i]; sum += arr[i]; } long long leftSum = 0 ; long long rightSum = 0 ; bool flag = false ; for ( int i

문제(링크) 모든 점을 포함하는 직사각형을 하나 그립니다. 그 직사각형의 두 대각선 중 최대값(L1-metric으로)이 구하고자 하는 값입니다. 각 꼭지점은 임의의 점이므로 각 꼭짓점에서 L1-metric이 가장 가까운 점을 찾아 새로운 꼭짓점으로 생각하여 풀이합니다. #include<iostream> #include<string> #include<algorithm> #include<math.h> #include<vector> #include<queue> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> int N; vector<pii> point; int L1met ( int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2); } int main ( void ) { FIO; cin >> N; int left = 1000001 ; int up = - 1000001 ; int right = - 1000001 ; int down = 1000001 ; for ( int i = 0 ; i < N; i++) { int x, y; cin >> x >> y; point.push_back(make_pair(x, y)); //직사각형의 4개의 변을 구합니다. left = min(left, x); up = max(up, y); right = max(right, x); down = min(down, y); }

문제(링크) 문과 스위치의 값을 bitset을 이용해 bit값으로 바꿔줍니다. 그 뒤, 스위치들에 대하여 모든 경우를 탐색하면서 현재 문의 상태로 갈 수 있는 년도를 구합니다. (문을 바꿔가며 -> 문과 스위치의 ^ 연산) 년도는 n 이 100이하이므로 100년을 시작년도로 생각하였습니다. 방문 배열을 만들어 현재 어떤 스위치를 켰는지(bitMask 이용)에 대한 방문 여부를 걸러줍니다. 그렇게 하면 하나의 스위치 상태에 대해 하나의 년도만 나오게 됩니다. 즉, rt[해당 년도] = 스위치의 bitMask 100 - N 년부터 100 + N 년까지 스위치의 bitMask를 적절히 출력하면 됩니다. #include<iostream> #include<string> #include<algorithm> #include<math.h> #include<vector> #include<bitset> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); #define pii pair<int, int>; int N, M; bitset< 101 > swit[ 21 ]; bitset< 101 > door; int rt[ 202 ]; int sizeY[ 202 ]; bool visit[ 1048577 ]; void BF (bitset< 101 > now, int cnt, int switBit) { if (cnt > M) return ; if (visit[switBit]) return ; visit[switBit] = true ; for ( int i = 1 ; i <= M; i++) { int bit = ( 1 <<

문제(링크) n개의 알파벳 중 모르는 단어가 하나라도 포함되어 있는지 판단하는 문제였습니다. 처음엔 Trie 알고리즘으로 접근했으나 메모리 초과가 떴습니다. 알파벳의 개수가 26개밖에 안되므로 알파벳을 아는지(1) 모르는지(0) 를 비트마스크로 나타내서 풀면 간단해지는 문제입니다. 처음엔 모든 알파벳을 알고 있다고 했으므로 know = 11111111111... 로 초기화 해줍니다. 문자를 잊는 연산은 ^ , 문자를 기억하는 연산은 | 로 쉽게 구할 수 있습니다. 마지막으로 각 쿼리마다 모든 문자열에 대해  (아는 문자들 & 문자열) == 문자열  인 경우에 대해 카운트하여 출력하면 됩니다. #include<iostream> #include<string> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); #define pii pair<int, int>; int N, M; int bit[ 10000 ]; int main ( void ) { FIO; cin >> N >> M; for ( int i = 0 ; i < N; i++) { string str; cin >> str; for ( int j = 0 ; j < str.size(); j++) { bit[i] = bit[i] | ( 1 << (str.at(j) - 'a' )); } } int know = 67108863 ; for ( int i = 0 ; i < M; i++) { int q; char x; int cnt = 0 ; cin &

문제(링크) 구간합 세그먼트 트리를 구현하고, 트리를 update 해가며 풀이합니다. 2번 질의에 대해 루트부터 왼쪽 오른쪽 구간합과 군번을 비교해가며 내려갑니다. 1번부터 봐야하므로 왼쪽 먼저 탐색하며, 왼쪽 구간합에 해당하지 않는다면 오른쪽 구간합을 볼 때 왼쪽 구간합의 값을 빼줍니다. #include<iostream> #include<vector> #include<math.h> #include<algorithm> #include<stdlib.h> #include<memory.h> using namespace std; int N, M; int * tree; void update ( int now, int l, int r, int idx, int diff) { if (idx > r || idx < l) return ; tree[now] += diff; if (r == l) return ; update(now * 2 , l, (l + r) / 2 , idx, diff); update(now * 2 + 1 , (l + r) / 2 + 1 , r, idx, diff); } int searchNum ( int now, int l, int r, int v) { if (r == l) { return l; } if (tree[now * 2 ] >= v) { return searchNum(now * 2 , l, (l + r) / 2 , v); } else { //오른쪽의 구간합은 왼쪽값이 들어있지 않으므로 (v - 왼쪽 구간합) return searchNum(now * 2 + 1 , (l + r) / 2 + 1 ,

문제(링크) 조건이 많이 까다로운 BFS 문제였습니다. 먼저, 빌딩 밖으로 나갈 수 있기 때문에 입력받는 배열 외에 겉에 한 줄을 더 감싸주었습니다.( 이렇게 하면 (0,0)에서 시작하여 항상 어디든지 갈 수 있습니다.) 열쇠와 문에 관련된 조건이 까다로웠는데, 다음과 같이 해결했습니다. - 열쇠를 만날 시 해당 열쇠를 배열에 추가하고(havekey[]), 리스트에 저장된 문들 중 열쇠에 해당하는 문들을 큐에 다시 넣습니다.( 그 문부터 다시 탐색합니다. ) - 문을 만날 시 1. havekey[] 배열에 등록된 열쇠라면(열린 문이라면) 통과합니다. 2. 잠긴 문이라면 문 리스트에 해당 좌표를 추가합니다.(다시 올 수 있게) 나머지는 일반적인 BFS와 같습니다. import java.io.*; import java.util.*; public class Main { public static int T, N, M; public static char [][] map; public static boolean[][] visit; public static int [] mv1 = { 0 , 0 , 1 ,- 1 }; public static int [] mv2 = { 1 ,- 1 , 0 , 0 }; public static boolean[] havekey; public static void main (String[] argc) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out)); T =

문제(링크) 좌표 압축 + 세그먼트 트리를 사용해 오프라인으로 해결하는 문제였습니다. 문제에서 퀘스트의 번호가 -10억 ~ 10억이기 때문에 퀘스트의 번호를 모두 세그먼트 트리에 저장하기엔 무리가 있습니다. 하지만 퀘스트의 총 개수는 100만개이기 때문에 사용된 모든 퀘스트들을 따로 리스트에 담아 압축시키면 됩니다. 즉, 모든 쿼리를 쭉 받아 1번 질의에 해당하는 퀘스트(새롭게 업데이트되는 퀘스트)를 저장합니다. 다음과 같은 퀘스트 번호가 주어진다면 Q1 = -1000000 , Q2 = 1524421 , Q3 = 23 , Q4 = -999999999 리스트에 정렬하여 담으면 다음과 같이 됩니다. list[0] = -999999999 (Q4) , list[1] = -1000000(Q1) , list[2] = 23(Q3) , list[3] = 1524421(Q2) 즉, list의 인덱스가 새로운 퀘스트 번호가 됩니다. 그리고 퀘스트의 원래 번호가 주어졌을 때 lowerBound or upperBound 를 이용하면 쉽게 인덱스를 찾을 수 있습니다. ex) lowerBound(1524421) -> 3 다음엔 list를 가지고 세그먼트 트리를 만드는데, 푼 문제는 1, 안 푼 문제는 0으로 하여 구간합을 구하면 해당 구간의 푼 문제의 개수를 구할 수 있습니다. 막혔던 부분 : 1. 처음 쿼리를 받을 때 1,2번 질의에 대한 퀘스트를 모두 받아 시간 초과, 메모리 초과가 났습니다.(2번 질의는 해당 범위의 푼 문제만 카운트하면 되므로 따로 저장할 필요가 없었습니다.) 2. 2번 질의를 해결할 때 Left, Right 모두 lowerBound로 찾아서 틀렸습니다.(RIght는 upperBound - 1로 해야 항상 가장 가까운 값을 찾을 수 있습니다.) import java.io.*; import java.util.*; public class Main { public static int