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

문제(링크) 구간합 세그먼트 트리를 구현하고, 트리를 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...