본문 바로가기

Computer Science74

[백준 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.
[C++] Segment Tree 라이브러리 만들기 Segment Tree는 PS에서 정말 자주 사용되는 자료구조 중 하나다. 그러나 Segment Tree에 들어갈 타입도 int, long long, derived-type 등 제각각, 연산도 add, multiply, min, max 등 제각각이므로 그냥 Generic programming으로 클래스 하나를 만들었다. 이 Segment Tree는 타입 T와 함수객체 BinaryOP를 받는다. T에 타입 넣고 BinaryOP에 인자 2개 받는 operator() 정의하면 끝. /* * Segment-tree! */ template class Segment_tree { std::vector tree; int size; public: explicit Segment_tree(const std::vector &.. 2022. 8. 16.
C++로 문서 작성 프로그램 만들기 [객체 지향 프로그래밍 과제 가이드] 많은 대학에서 객체 지향 프로그래밍을 가르칠 때 프로젝트를 시킨다. 그러나 16주라는 짧은 기간 안에 4 Pillars of OOP도 끝까지 가르치기는 힘들다. 교수님이 잘못하셨다는 게 아니라, 원래 4 Pillars of OOP에 익숙해지는 과정에서 신문법을 다수 익혀야 하다 보니... 그래서 신문법 배우기에 바빠 설계법까지 미처 배울 시간이 없는 경우가 종종 있다. 그래서, 내가 본 어떤 프로젝트에서는 '여자' 클래스를 만든 뒤 '여자' 클래스를 상속받는 '사람' 클래스를 만들기도 하더라. 그래서 훗날 객체 지향 프로그래밍 과제를 하게 될 불쌍한 사람들을 위해 이 게시글을 쓰게 되었다. 프로그램의 소스 코드 길이는 과제를 마친 2022년 6월 19일 기준으로 2280줄이다. 그 중 약 200줄 정도가.. 2022. 8. 15.
유용한 비트 연산들 출처 : , 안티 라크소넨 x | (1 2022. 8. 11.
[C++] 볼록 껍질 클래스 구현 임의의 개수의 2차원 점을 input으로 받아, 볼록 껍질 객체를 만들어 주는 클래스이다. using namespace std; class Point { public: long long x, y; Point(long long _x, long long _y) : x(_x), y(_y) {} Point operator-(const Point& rhs) const { return Point(x - rhs.x, y - rhs.y); } bool operator x * rhs.y) { return false; } else { return x * x + y * y < rhs.x * rhs.x + rhs.y * rhs.y; } } bool operator==(const Point& rhs) const { return.. 2022. 8. 7.
[C++] 다항식 클래스와 라그랑주 보간법(Lagrange Interpolation) 구현 다음 문제를 풀다가 다이나믹 프로그래밍으로 푸는 법이 생각이 안 나서 Lagrange Interpolation으로 밀어붙이려고 했다. 사실 생긴 것만 봐도 다이나믹 어쩌고저쩌고보다는 수학 문제를 닮아 있는 것 같지 않은가? 사실 이 문제에 대한 일반화는 이미 존재하고, 베르누이 수열인가 뭔가를 쓴다고 알고 있지만 그걸 굳이 알고 싶지는 않았다. 그리고 도전 중인 문제가 하나 더 있는데 그 문제에서도 Lagrange Interpolation을 쓰기 때문에 어차피 한 번은 이걸 구현해야 해서, 그냥 오늘 구현하기로 했다. 특이사항으로, class Polynomial을 구현할 때 std::vector를 쓰지 않았다. C++의 이동 연산에 대해 공부하고 있었기 때문에 이동 연산을 구현해야 했기 때문이다. 시간복.. 2022. 8. 7.
[C++] SCC Maker class 타잔 알고리즘으로 SCC를 만들어주는 클래스. 설명은 나중에 적어야지... class SCCMaker { public: std::vector adj; std::vector id; int next_id; std::stack s; std::vector is_in_scc; std::vector scc; SCCMaker(std::vector &vvi) : id(vvi.size(), -1), next_id(0), is_in_scc(vvi.size(), false) { adj.swap(vvi); for (int i = 0; i < adj.size(); ++i) { if (id[i] == -1) { id[i] = next_id++; dfs(i); } } std::sort(scc.begin(), scc.end(), [.. 2022. 8. 6.
[백준 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.
[C++] AVL Tree와 이를 이용한 Ordered-Set 구현 C++을 컴파일할 때 G++ 컴파일러를 쓰는 사람은 PBDS(Policy-Based Data Structure)라고 해서 유용한 연산들을 많이 제공해 주는 자료 구조를 쓸 수 있다. 하지만 난 Xcode를 쓰기 때문에 PBDS를 못 쓴다! 그래서 그냥 내가 만들기로 했다. 밑의 코드는 AVL Tree를 통해 Ordered-Set을 구현한 것이다. Ordered-Set이란? 기존의 Balanced Binary Search Tree 기반의 Set에 몇몇 기능을 추가한 것이다. 주요 기능으로 다음 두 가지 기능이 있다. find-by-order : Set의 n번째 원소가 무엇인지를 O(log n) 안에 찾아준다. order-of-key : Set의 원소 k가 몇 번째로 작은 원소인지를 O(log n) 안에 찾.. 2022. 8. 4.
[C++] class Modulo: 나머지환에서의 사칙연산을 구현해 보자 설명은 나중에 써야겠다. template class Modulo { private: long long n; public: Modulo() = default; constexpr Modulo(long long _n) : n(_n >= 0 ? _n % P : (P - (-_n % P)) % P) {} constexpr Modulo operator+(const Modulo& rhs) const {return Modulo((n + rhs.n) % P);} constexpr Modulo& operator+=(const Modulo& rhs) {*this = *this + rhs; return *this;} constexpr Modulo operator-() const {return n == 0 ? Modulo(0).. 2022. 8. 4.

티스토리툴바