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 ...

문제(링크) 문제 설명: 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 ...