본문 바로가기

C++16

충격!) C++에서 Rust의 블록 표현식과 유사한 구문을 사용할 수 있다?! Rust는 {}으로 감싸지는 코드 블록이 단순한 문장들의 나열이 아니라 하나의 표현식(Expression)으로 사용될 수 있다. let x = ??? let result = { let x0 = if x >= 0 {x} else {0}; x0 * x0 * x0 + 3 * x0 }; 코드블록의 마지막 문장인 x0 * x0 * x0 + 3 * x0 뒤에 세미콜론이 찍혀 있지 않으므로, 코드블록은 x0 * x0 * x0 + 3 * x0으로 평가되는 표현식(Expression)이 된다. 따라서 result에 해당 값이 들어간다. 이런 구문은 이름공간의 오염을 줄이는 역할을 한다. result를 계산할 때 말고는 절대로 x0가 다시 사용되지 않는다는 것을 알고 있다면 코드 블록을 사용하여 x0을 특정 영역 안에 가.. 2024. 3. 4.
[백준 1285] 동전 뒤집기 \( N \leq 20\)이므로 \(2^N\) 또는 그에 준하는 풀이를 생각해볼 만하다. 가로 \(N\)개의 줄, 세로 \(N\)개 줄 중 무엇을 뒤집을 것인지 생각하는 문제이므로 존재할 수 있는 선택의 개수는 \(2^{2N}\)이다. 그중에서 가로줄과 세로줄 중 하나가 몇 번 줄을 뒤집을지 그 상태가 이미 정해졌다면(편의상 세로줄이라 하겠다), 가로줄에 H가 더 많으면 가만히 놔두는 것을 선택하고 T가 더 많으면 뒤집는 것을 선택하는 그리디 알고리즘을 생각할 수 있다. 이것이 성립하는 이유는 세로줄이 이미 선택된 이상 모든 가로줄은 서로 영향을 주지 않는 독립이므로 순간의 최적 선택이 전체 최적 선택을 담보하기 때문이다. 한 번 그리디 알고리즘을 시행할 때마다 전체 셀 개수인 \(O(N^2)\)의 시간.. 2024. 1. 10.
Heap과 Priority Queue의 차이, 그리고 Abstract Data Type이란 무엇인가 얼마 전까지만 해도 나도 헷갈렸던 부분이다. 일단 배경지식이 어느 정도 필요하다. C++에서 스택(std::stack)은 어떻게 구현되어 있을까? std::vector 구현체처럼 그냥 공간을 뭉탱이로 할당해 놓고 공간 부족해지면 늘려서 할당하고 그런 식으로 구현되어 있지 않을까? 대부분의 자료 구조 강의에서도 stack을 그런 식으로 구현하니 말이다. 하지만 실제로는 이렇게 생겼다. 왜 이렇게 끔찍하게 생긴 방식으로 구현되었을까? 사실 이 구현은 양쪽에서 모두 원소를 뽑아 쓸 수 있는 큐인 deque(double-ended queue)에서 한쪽을 막아놓는다는 이상한(?) 방식이다. std::queue 구현도 마찬가지다. 대체 왜 그냥 자료 구조 교과서에 있는 스택을 안 만들고 굳이 deque를 만든 다음.. 2023. 2. 7.
C++ 버전이 바뀌면서 의미가 달라진 키워드들 C++에는 이렇게 많은 키워드가 있다. C++은 C에서 처음 시작했지만 시대가 발전하면서 Python, Haskell 등 프로그래밍의 패러다임을 바꾼 수많은 언어가 튀어나왔고 C++는 30년 동안 그 수많은 패러다임을 다 먹어치울 기세로 커졌기 때문이다. 그 과정에서 C++의 몇몇 키워드는 의미가 바뀌기도 했다. 가장 대표적인 키워드가 inline으로, 이 키워드는 C++에서 함수 실행 오버헤드를 줄이기 위해 함수 호출하는 부분을 그냥 함수 본문으로 대체하는 것과는 전혀 관련이 없다. 모든 C++ 개발자들은 바뀐 키워드의 내용을 숙지하여 모던한 프로그래밍 습관을 기르도록 하자. auto (C에서) storage duration을 auto로 설정함 (C++11부터) 정의된 변수의 타입을 컴파일러가 알아서 .. 2023. 1. 9.
[C++] class Matrix 구현 내가 class Matrix를 아직도 이 블로그에 안 올려놨다니,,, 덧셈, 뺄셈, 곱셈, 스칼라배, 기본행/기본열 연산 등의 기능을 지원한다. 근데 뭐 이거 구현한다고 250줄을 잡아먹냐. template class Matrix { private: T** p; unsigned int n; // size public: explicit Matrix(int _n) : n(_n) { this->init(); } ~Matrix() { if (p) { for (int i = 0; i init(); for (int i = 0; i < n; ++i) { fo.. 2022. 9. 24.
[C++] 프록시(Proxy) 디자인 패턴 (feat. bitset) 프록시(Proxy)는 대리자라는 뜻을 갖고 있다. 즉 어떤 객체가 하는 일을 그대로 흉내내는 객체이다. C++에서 프록시의 가장 유명한 예시는 바로 스마트 포인터(Smart Pointer)일 것이다. 스마트 포인터는 자신이 소멸될 때 delete 연산자를 알아서 호출해서 메모리 누수를 막는 똑똑한 객체인데, 당연하지만 스마트 포인터 그 자체는 포인터가 아니라 객체이다. 그럼에도 스마트 포인터는 일단 포인터가 할 수 있는 모든 일을 할 수 있도록 설계되어 있다(unique_ptr 같은 경우 복사 연산과 복사 대입 연산이 안 되기는 하지만). 특히 * 연산자와 -> 연산자를 제공하므로 사용자는 스마트 포인터를 그냥 포인터 쓰듯이 쾌적하게 사용할 수 있을 것이다. 이 글에서는 비트셋(bitset)에서 프록시 .. 2022. 9. 18.
[C++] Disjoint Set 기초 구현 이건 솔직히 너무 쉬워서 뭐 설명할 게 없음 class DisjointSet { std::vector parent; public: explicit DisjointSet(int n); int get_parent(int idx); bool join(int i, int j); bool _joined_(int i, int j); }; DisjointSet::DisjointSet(int n) : parent(n) { for (int i = 0; i < n; ++i) { parent[i] = i; } } int DisjointSet::get_parent(int idx) { if (idx == parent[idx]) { return idx; } return parent[idx] = get_parent(parent[i.. 2022. 9. 9.
[백준 5615] 아파트 임대 (Feat. 밀러-라빈 소수 판정법) (Platinum I) https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 매우 자명한 어떤 절차에 의해, 2N + 1이 소수가 되는 N을 찾는 문제임을 알 수 있다. Naive한 소수 판별을 짜면 시간복잡도 \(O(T \sqrt{N})\)이 나와서 TLE가 난다. 시간복잡도를 줄일 수 있는 방법으로 밀러-라빈 소수 판정법을 이용하자. a = 2, 7, 61에 대하여 \( n - 1 = 2^s d \)로 놓는다. \( a^d \ne 1 \mod n \)이고, 모든 r : 0 ~ s.. 2022. 8. 28.
[백준 9206] 나무 말고 꽃 (Platinum II) https://www.acmicpc.net/problem/9206 9206번: 나무 말고 꽃 선영이와 남자친구의 2주년이 얼마 남지 않았다. 선영이는 그를 위해 특별한 것을 사주려고 한다. 남자친구는 나무에 관심이 매우 많다. 하지만, 선영이는 나무는 선물로 매우 크다고 생각한다. www.acmicpc.net 수치해석 문제들이 다 그렇듯이 수많은 시도를 해야 풀 수 있다... 일단 constexpr로 각종 상수를 정의해 주자. constexpr value들은 컴파일 시점에 평가되기 때문에, #define 같은 매크로의 기능을 거의 모두 쓸 수 있으면서 그것보다 더 안전하다고 할 수 있겠다. constexpr long double PI = 3.1415926535897932384626l; constexpr .. 2022. 8. 26.
C++로 문서 작성 프로그램 만들기 - 1. 클래스 다이어그램 짜기 [객체 지향 프로그래밍 프로젝트 가이드] Motivation 객체 지향 프로그래밍 과제 프로젝트라 함은 무언가 엄청난 발명을 해서 실용적인 것을 추구하기보다는, 객체 지향 프로그래밍을 잘 이해할 목적으로 만들어지는 것이다. 그러므로 기본적으로 주제 선정에 있어서 4 Pillars of OOP를 마음에 새기는 것이 중요하다. 캡슐화(Encapsulation) 상속(Inheritance) 추상화(Abstraction) 다형성(Polymorphism) 개인적으로 나는 Polymorphism을 써서 만들 수 있는 프로그램이 뭐가 있을지 떠올리는 게 가장 힘들었다. 그러다가, "print() 멤버 함수로 문자열도 출력하고 표도 출력하고 그래프도 출력하는 프로그램이 있으면 재미있지 않을까?"라는 생각이 갑자기 들어서, 그때부터 보고서 작성 프로그램의 기획.. 2022. 8. 26.
[백준 18222] 투에-모스 문자열 (Silver II) 5줄 안으로 구현하기 https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 문제에서는 숫자를 1부터 세지만 우리는 편의상 숫자를 0부터 세도록 하자. 임의의 자연수 n에 대해, n의 2진수 표현에서 비트 값을 (아무 위치에서나) 1만큼 바꿔 준 수 m을 고려하자. 그러면 n번째 투에-모스 문자열과 m번째 투에-모스 문자열 값은 그 parity가 반대임을 알 수 있다. 따라서 n의 2진수 표현의 비트 수를 세 준 뒤 2로 나눈 나머지를 출력하기만.. 2022. 8. 20.
[백준 25323] 수 정렬하기, 근데 이제 제곱수를 곁들인 [UCPC 2022 예선] (Platinum V) https://www.acmicpc.net/problem/25323 25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인 양의 정수로 이루어진 길이가 $N$ 인 수열 $A_1,A_2,\cdots ,A_N$이 존재할 때, 다음 행동을 원하는 만큼 반복할 수 있다. $1\leq i,j\leq N;i\neq j$이면서 $A_i\times A_j$가 제곱수인 $i$, $j$를 선택해, $A_i$와 $A_j$ www.acmicpc.net AB가 제곱수이고, AC가 제곱수이면 BC도 제곱수이다. 증명 : (A^2)BC가 제곱수고, 제곱수를 제곱수로 나누면 제곱수라는 사실로부터 자명하다. 반대로 AB가 제곱수이고, AC가 제곱수가 아니면, BC도 제곱수가 아니다. (증명은 위와 똑같이 하면 된다) -> 수열이 몇 .. 2022. 8. 20.
[백준 1168] 요세푸스 문제 2 (Platinum III) (Feat. PBDS) - 세그먼트 트리 없이 풀기 https://www.acmicpc.net/problem/1168 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 컴퓨터공학과에서 를 수강한 학생들이라면 std::set이 레드-블랙 트리로 구현되어 있다는 것을 알 것이다. 레드-블랙 트리는 Binary Search Tree다. 즉 원소들이 나름의 순서를 갖추고 정렬되어 있다는 것이다. 정렬되어 있다는 것은, 마치 Binary Search 하듯이 k번째 원소를 O(logn) 안에 접근할 수 있음을 함의한다. 그러나 그것을 하기 위해서는 rb-tree의 각 노드들이 subtree의 개수를 저장하고 있어야 한다. std::set은 이 기능을 제공하.. 2022. 8. 17.
[백준 18542] Permutant (Ruby III) 풀이 https://www.acmicpc.net/problem/18542 18542번: Permutant Consider an \(n \times n\) matrix \(A\). Let us denote element in \(i\)-th row and \(j\)-th column as \(A_j^{(i)}\). You are given a sequence \(a_1, \dots , a_n\) and a permutation \(π_1, \dots , π_n\) such that the first row is formed by sequence \(a_k www.acmicpc.net 먼저 주어진 Permutation는 Linear Transform의 일종임을 파악해야 한다. 예를 들어, Permutation {.. 2022. 8. 4.
[C++] 선분 교차 판정 선분 교차 판정이란 말 그대로 두 선분이 교차하는지 아닌지 판정하는 것이다. 선분 교차 판정을 효율적으로 하기 위해서는 CCW(또는 signed area)에 대한 지식이 필요하다. CCW(또는 signed area)란? 세 점 A, B, C에 대하여 선분 BC가 AB에 대하여 시계 방향으로 휘어져 있는지 반시계 방향으로 휘어져 있는지 판정하는 것으로, 2차원에서 determinant의 개념을 응용하는 기술이다. 두 2차원 벡터 u, v의 determinant는 2가지 정보를 담고 있다. 그 절댓값은 두 벡터 u, v가 생성하는 평행사변형의 넓이를 알려주고, 그 부호는 v가 u에 대하여 시계 방향으로 휘어져 있는지 반시계 방향으로 휘어져 있는지를 알려준다(+: 반시계, -: 시계). PS계에서는 CCW라는.. 2022. 8. 4.
[C++] 유리수 클래스(class Fraction) 구현 프로그래밍을 할 때 실수를 쓸 일이 있으면 대부분 double을 사용하지만 PS계에서는 스페셜 저지가 붙어 있지 않은 한 이런 행위는 죄악에 가깝다. 대표적인 예시가 바로 4225번. square-root를 다루는 주제에 스페셜 저지도 안 붙어 있어서, 입력값이 10000 이하임에도 불구하고 int128을 써야 하는 괴상한 문제다. 어쨌든 높은 정밀도를 위해서는, long double에 안주하지 말고 더 정확한 값을 얻을 수 있는 방법이 무엇일지를 생각해 놓아야 한다. 오차는 계산할 때마다 계속해서 불어나는 성질이 있다. 2.5를 반올림해서 3으로 표현한다면, 2.5 * 2.5는 실제로는 6.25지만 데이터 상으로는 3 * 3 해서 9가 되는 것이다. double을 쓰면 어쩔 수 없이 오차가 있을 수밖에.. 2022. 8. 4.

티스토리툴바