아롱이의 PS하는 블로그

https://www.acmicpc.net/problem/16995풀이이전 포스팅에서 다룬 신발끈 공식의 특성을 창의적으로 이용하는 문제이다. 처음에는 이런 생각을 했다.볼록 K각형은 K-2개의 삼각형으로 이루어져있음을 이용해서"대칭적으로, 가능한 모든 조합의 삼각형을 다 더했을 때 전체 다각형의 넓이와 관련해서 간단하게 식이 나오지 않을까?" 안나왔다. 이것때문에 몇시간을 고민했다.사실 나오긴 나오는데 이걸 수학적으로 계산하려니 머리가 아팠다. 그래서 조금 다른 접근을 소개한다. 신발끈 공식과 넓이 계산 예를 들어서 N = 6, K = 4라고 해보자.즉, 육각형(여섯모) 내에서 4개의 점을 잡아 사각형(네모)를 만드는 것이다. 예를 들어서, A, C, D, F의 사각형을 골랐다고 해보자.그러면 우리는 ..

백준 16995번 문제를 풀다가 신발끈 공식의 특성(정확히는 외적의 특성)이 이용되는 것을 알게 되었다.앞으로도 이런 기하 문제를 자유자재로 다루기 위해서는 외적과 신발끈 공식에 대해 완전한 이해를 하고 있어야 한다는 것을 알게 되었다. 외적두 개의 벡터가 있으면 외적으로 삼각형의 넓이를 구할 수 있다.원점을 O라고 잡고, 삼각형 OAB의 넓이를 구해보자. OA, OB벡터 각각에 대해 외적을 이용하면 삼각형의 넓이가 다음과 같이 됨이 알려져있다. 그런데, 어차피 원점이 껴있으므로 넓이의 식은 A, B 두 개의 점의 성분들로만 표현이 된다는 것을 알 수 있다. 그렇다면 여기서 우리가 다음과 같이 새롭게 정의를 해보자.$x_{1}y_{2} - x_{2}y_{1}$은 벡터 AB의 외적이다. (실제로 이렇게 말..

https://www.acmicpc.net/problem/1492https://www.acmicpc.net/problem/25974풀이수학 심층을 열심히 대비하고있는데, 분명 어디선가 본 것같기도 하고 아닌 것 같기도 한 점화식.아마 운 좋으면 대입에도 나올 수도....? 한 번 유도해보자.우리가 원하는 값을 $S_k$라고 정의하자. 우리는 위와 같은 이항계수 전개식을 생각해줄 수 있을 것이다. 심심하니까 x 대신 N을 넣어보자. 우리는 1부터 N까지의 거듭제곱들을 원하기 때문에, 거듭제곱의 밑을 바꿔주어야겠다는 생각을 할 수 있다.이제 1+N 대신 N, N-1, N-2 .... 3, 2를 대입하고 쭉 적어보자. 맨 마지막 끝부분이 kCk인데, 이는 1과 같다. 그러니까 다음과 같이 전부 더해주면 ..

이번 글에서 다뤄볼 주제는 FFT를 구현 안하고 FFT 문제를 빨리 푸는 방법이다.얼마전에 FFT를 알고리즘 스터디 시간에 열심히 증명하고, 파이썬으로 구현체를 열심히 만들었던 기억이 있다.물론, 구현체는 아직도 외우지 못해서 내가 예전에 만든걸 복붙하고 있다. 하지만, , , , , 가끔씩 숏코딩을 들어가보면 터무니없이 짧은 길이의 코드들이 있다.도대체 어떻게 푼 것일까???? 1. 파이썬 언어의 특징파이썬에서는 C++과 달리 매우 큰 수 연산이 쉽게 가능하다.파이썬 내부적으로 큰 수 연산을 어떠한 방법을 써서 하기 때문이다.곱셈을 예를 들자면, 자리수가 적당히 작으면 파이썬은 그냥 우리가 알고있는 곱셈 방법을 쓴다.다만, 자리수가 적당히 커지면파이썬은 FFT를 기반으로 한 알고리즘이나 카라추바 알고..

https://www.acmicpc.net/problem/1655풀이우선순위 큐 두 개를 활용해서 해결할 수 있다.최대 힙과 최소 힙 두 종류를 각각 만들고, 각각 '작은 수'와 '큰 수'를 저장한다. (두 힙의 이름은 각각 small, big라고 하자.)현재 들어오는 수가 big의 top보다 작거나 같으면 small로 보내고, 아니면 big으로 보낸다.그리고 두 우선순위 큐의 크기(균형)을 맞춰준다. 항상 두 큐의 크기가 같거나, 아니면 small이 하나 더 크게 만들 수 있다.그러면 각 단계에서 small의 top이 정답이 된다. 이게 무슨 소리냐면,예제 1, 5, 2, 10, -99, 7, 5를 예를 들어보자. 1이 들어왔을 때는 다음과 같다. small 1big(답: 1) 5가 들어오면, smal..

https://www.acmicpc.net/problem/24276풀이처음에는 4색문제인가? 하고 생각했는데 문제를 잘 읽어보면 조금 그래프가 특수한 경우라는 것을 알 수 있다.내부에 교차점이 없다!그러면 그래프는 여러 개의 볼록 다각형이(또는 선분이) 변을 맞대고 붙어있는 구조라는 것을 알 수 있고, 조금만 그림을 그려보면 3색으로 충분히 색칠 가능하다는 것을 알 수 있다. 하지만 이 문제는 애드혹, 해 구성하기 없이 그냥 그래프 탐색으로 풀 수 있다. 내가 생각한 첫 번째 알고리즘(틀림)은 이렇다. 1. 1부터 시작해서 2, 3, 4, ... 순서대로 노드를 방문한다.2. 각 노드에서 연결된 다른 노드들의 색깔을 조사하고, 거기에 안 쓰인 가장 작은 색깔로 노드를 색칠한다. 몇 개의 테스트케이스를 해..

오늘은 집합 자료 구조에 대해 배운다.파이썬에서는 보통 set을 이용해서 집합을 만들고, in을 이용해서 O(1) 안에 원소가 있는지 없는지 찾을 수 있었다.C++에서는 어떻게 할까? 셋과 멀티셋C++ 표준 라이브러리에는 경진 프로그래밍에서 자주 쓰는 집합 자료 구조가 두 개 있다. set균형 잡힌 이진 탐색 트리를 기반으로 만들어졌으며, 연산은 O(log n) 시간에 동작한다. unordered_set해시 테이블을 기반으로 만들어졌으며(python 에서 set과 비슷), 연산은 평균적으로(최악의 경우 O(N)) O(1)에 동작한다. 위 둘 다 중복된 원소는 허용하지 않는다. 둘 다 사용법은 비슷하니 set를 통해 예시를 보도록 하겠다. set s;s.insert(3);s.insert(2);s.inser..

스택다음과 같이 쓸 수 있다.#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); stack st; st.push(3); st.push(4); st.pop(); cout 파이썬과의 차이점이 있다면, pop() 연산자는 그 값을 반환하지 않는다. 그냥 말 그대로 pop하고 사라진다. 큐다음과 같이 쓸 수 있다.#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); queue Q; Q...

배열배열은 파이썬과 다르게 선언한 자료형의 값만 저장할 수 있다.인덱스를 통해 값에 바로 접근할 수 있고,새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.배열의 크기는 처음에 생성할 때 지정할 수 있고 이후 못 바꾼다. 구조가 간단하고 빨라서 PS에서 가장 많이 이용된다. 선언하려면 이렇게 하면 된다.int arr[1001]; 아래는 C++17에서는 지원하지 않는 문법인데, 백준 환경이 GCC 어쩌구여서 가능한 간단한 배열 초기화 방법이다.(위처럼 그냥 선언만 해주면 배열 안에 뭐가 들어있을지 모른다)int arr[1001] = {0}; 이렇게 아예 처음부터 초기값을 정할 수도 있다.int arr[3] = {3, 4, 5}; 아래는 내가 파이썬을 쓰면서 유일하게 C++이 부러웠던 점이다...

조건문 기본적인 틀은 이렇다. 파이썬과의 차이점이라고 하면 elif가 없어서 직접 else if라고 해야한다는 것. 그리고 콜론이 없다는 것.괄호 안에는 불리언 타입이 올 수 있다. int a = 3;if (a == 3) { cout switch문 (25.08.04)if 문을 연달아 쓰는 것도 좋지만, C++에서는 다음과 같은 switch 문법을 지원한다.for (int x = 0; x 반복문1. for 문일단, 파이썬에서 가장 많이 썼던 for i in range(N) 구문은 다음과 같다.for (int i = 0; i 보아하니 저 반복문 자체를 define해서 약어처럼 쓰시는 분들도 계시더라. 혹시 파이썬에서 이터레이터를 for문을 통해서 순회했던 것 처럼 C++에서도 배열이나 문자열 등..