티스토리

파이도의 끄적끄적

검색하기

블로그 홈

파이도의 끄적끄적

paido.tistory.com/m

파이도 님의 블로그입니다.

구독자: 3

방명록 방문하기

주요 글 목록

고속 푸리에 변환(FFT)의 빠른 구현체 PS에서 고속 푸리에 변환(Fast Fourier Transform, FFT)을 쓰는 문제를 이따금씩 볼 수 있다. 컨볼루션은 주파수 영역에서 원소별 곱 연산(elementwise multiplication)으로 바뀌는 특성을 기반으로, FFT를 통해 \(O(n^2)\) 대신 \(O(n \lg n)\) 시간에 컨볼루션이 가능함을 이용하는 문제들이다. FFT는 크게 Cooley-Tukey, Split-Radix, Tangent의 세 가지 방법이 있다. Cooley-Tukey가 가장 간단하지만 비교적 느리고, Tangent가 가장 빠르지만 구현이 가장 복잡하다. 따라서 PS에서는 Cooley-Tukey를 쓰는 것이 일반적이다. 하지만 Cooley-Tukey는 구현 방법에 따라 실행 시간의 편차가 크게 수십 .. 공감수 1 댓글수 0 2021. 2. 14.
\( \det(AB) = \det(A) \det(B)\)의 증명 행렬식에 관한 항등식 \( \det(AB) = \det(A) \det(B) \)를 증명하는 보통의 방법은 기본행렬 \(E\)에 대해 \( \det(EB) = \det(E)\det(B)\)가 됨을 보인 다음, 행렬 \(A\)가 기본행렬들의 곱으로 쪼개질 수 있음을 보이는 것이다. \(A\)가 singular인 경우 기본행렬 분해가 불가능하지만, 이때는 행렬 \(AB\)와 \(A\)가 모두 singular이므로 양변이 모두 0이 되어 성립한다. 하지만 행렬식의 수식을 직접 조작해 보인 것이 아니므로, 식을 직접 조작하는 증명을 해 봐야 명쾌할 것이다. 어차피 행렬식도 행렬원소들에 대한 다항식인데, 두 다항식이 같음을 보이는 증명은 기본행렬 같은 선형대수 논리 없이도 가능해야 하지 않을까? 그 증명은 다음과 .. 공감수 2 댓글수 0 2020. 12. 7.
SCPC 2020 2차예선 + 본선 후기 2차예선 후기 1,2번은 쉬운 문제라 빨리 풀고 3번을 잡았는데, \(O(N \lg N)\) 풀이를 구현해도 계속 시간초과가 났다. 스플레이 트리, 평방 분할, multiset 등 다양한 구현체를 계속 시도해보다가, 계속 TLE가 발생하길래 로컬에서 벤치마크를 시도했더니 100개 테스트 케이스를 돌리면 6초를 넘어서 한 15초 내외가 나왔다. 상수커팅이란 느낌이 들어서 좌표압축을 하고 압축된 좌표로 세그먼트 트리를 돌렸더니 7-8초 내외가 나왔다. 여기서 다시 좌표압축을 할 때 정렬하는 과정을 counting sort로 바꿨더니 3-4초로 줄었다. 이걸 제출해서 AC를 받았다. 문제는 삽질을 너무 많이 해서 3번을 AC 받은 시간이 오후 7시가 넘었다는 점. 그래서 일단 5번 부분점수 37점을 확보해서 .. 공감수 0 댓글수 0 2020. 11. 16.
POI 18회 스테이지3 문제2. Monotonicity 2 문제 설명 https://www.acmicpc.net/problem/8195 풀이 * 아래 풀이는 POI 공식 사이트에서 볼 수 있는 풀이(폴란드어로 쓰여 있음)를 참조했습니다. (https://oi.edu.pl/) 1. 개요 우리가 해결할 문제는, 주어진 수열 \(a_1, a_2, \dots, a_n\)의 부분수열 \(a_{b_1}, a_{b_2}, \dots, a_{b_k}\) 중, 모든 \(1 \le i \le n-1\)에 대해 \(i\)번째 항과 \(i+1\)번째 항 사이에 \(a_{b_i} \,\langle s_i \rangle\, a_{b_{i+1}}\)이 성립하는 것 중 가장 긴 것을 찾는 것이다. 여기서 \(\langle s_i \rangle \)는 부등호 또는 등호인 \(s_i\)를 \(.. 공감수 0 댓글수 0 2020. 11. 1.
SCPC 2017 2차예선 5번 풀이. 자석 문제 설명 \(N\)개의 폐구간에 대해, 각 구간 \(i\) (\(1 \le i \le N\))의 끝점 \(L[i]\), \(R[i]\)가 주어진다. 또한, 각 구간의 활성화 비용 \(W[i]\)가 주어진다. 하나의 구간 \(i\)를 비용 \(W[i]\)를 들여 활성화하면, 이 구간은 '활성구간'이 되고, 구간 \(i\) 및 구간 \(i\)와 한 점이라도 겹치는 모든 구간이 '커버'된다. 각 구간은 하나 이상의 구간에 의해 커버될 수 있다. 모든 구간을 커버하기 위한 최소 비용을 구하면? 제한조건: \(N \le 100,000\), \(0 \le L[i], R[i] \le 10^9\), \(1 \le W[i] \le 10^5\) 실행조건: 90개 이하 테스트 케이스에 대한 실행시간 총합 3초 이내 (자세.. 공감수 0 댓글수 0 2020. 8. 23.
SCPC 2020 1차예선 5번 구현 소스 코드 풀이 설명은 https://paido.tistory.com/21을 참고해 주세요. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 .. 공감수 0 댓글수 0 2020. 8. 22.
SCPC 2020 1차예선 4번 구현 소스 코드 풀이 설명은 https://paido.tistory.com/21을 참고해 주세요. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531.. 공감수 0 댓글수 0 2020. 8. 22.
SCPC 2020 1차예선 풀이, 후기 올해 SCPC는 작년보다 푸는 시간이 더 빨라진 것 같다! 알고리즘에 따라 나누어 보면 1번 그리디, 2번 DP, 3번 DP, 4번 세그먼트 트리, 5번 기하가 출제되었다. 구현 소스 코드 링크: 1번, 2번, 3번, 4번(별도의 글), 5번(별도의 글) 문제 1. 다이어트 설명 길이 \(N\)인 두 수열 \(A[1..N]\), \(B[1..N]\)이 주어져 있을 때, 두 수열에서 숫자를 각각 하나씩 뽑아 순서쌍 \((A[i], B[j])\)를 만드는 작업을 \(K\)번 반복하였다. 만들어진 \(K\)개의 순서쌍에서 두 수의 합의 최댓값을 최소화하도록 순서쌍들을 뽑으면 그 값은 얼마인가? (단, 한 번 쓴 수는 다시 쓰지 않는다.) 제한조건: \(1 \le N \le 200,000\), \(1 \le K.. 공감수 5 댓글수 11 2020. 8. 22.
SCPC 2019 본선 5번 풀이. 정육면체 재구성 문제 설명(요약) 3차원 공간에 \(N\)개의 점 \(P_1(x_1,y_1,z_1)\), \(\cdots\), \(P_N(x_N,y_N,z_N)\)이 주어져 있다. (정수좌표) 다음 조건을 만족하는 두 정육면체 \(Q\), \(Q'\)을 생각하자. \(Q\)와 \(Q'\)의 중심은 서로 일치한다. 주어진 \(N\)개의 점은 \(Q\)의 내부 또는 경계에 있으며, 동시에 \(Q'\)의 외부 또는 경계에 있다. 즉, \(Q\)는 바깥쪽 정육면체이고 \(Q'\)은 안쪽 정육면체이다. \(Q\)와 \(Q'\)의 한 변 길이의 차이의 최솟값을 구하시오. 제약 조건: \(N \le 15,000\), \(-10^9 \le x_i, y_i, z_i \le 10^9\) 실행 조건: 테스트 케이스 50개에 대한 실행시간 .. 공감수 0 댓글수 0 2020. 2. 20.
유한분배격자의 기본정리 (Fundamental Theorem of Finite Distributive Lattices) Poset (partially ordered set) Theory에서 중요한 정리인 유한분배격자의 기본정리(Fundamental Theorem of Finite Distributive Lattices)에 대해 설명하고자 한다. 이 정리는 Birkhoff's Theorem으로도 불린다. 정의 1. 집합 \(P\)와 그 위에 정의된 order relation \(\le\)의 순서쌍 \((P, \le)\)를 Poset이라고 한다. \(P\)가 유한집합인 경우 \((P, \le)\)를 Finite Poset이라고 한다. 정의 2. Poset \(P\)의 임의의 두 원소가 유일하게 정해지는 Meet \(x\vee y\) 및 Join \(x\wedge y\)를 갖는 경우, \(P\)를 격자(Lattice)라고 한다.. 공감수 0 댓글수 0 2019. 10. 18.
SCPC 2019 본선 후기 오늘은 대망의(!) SCPC 본선이 있던 날. 지난 두 번의 대회에서 상을 못 받았고 지쳐가고 있었지만, 솔직히 방학 때만 벼락치기로 하면서 상 받기를 기대하는 나란 참...! 어쨌든 이번 예선 결과가 좋아서 나름 기대를 하고 대회장에 갔다. 가서 과자부터 집어다 쌓아놓으려고 했는데, 어쩐 일인지 올해는 초콜릿 바가 없어서 아쉬웠다. 아쉬운대로 일단 쿠키랑 음료를 가져다 놓았다. 늘 그렇듯이 1시 반에 대회가 시작되었다. 당연히 1번 문제부터 잡았다. 1번 문제는 이분 탐색으로 \(O(N \lg{N})\)으로 해결되는 게 당연한 문제인데 std::vector에다가 std::find를 쓰는 바람에 \(O(N^2)\)가 되어 계속 시간초과가 났었다. 90명이나 풀었는데 왜 난 안 되지...? 하다가 일단 2.. 공감수 2 댓글수 0 2019. 7. 30.
SCPC 2019 2차예선 4번 구현 소스 코드 SCPC 2019 2차예선 4번. 폭격의 소스 코드입니다. 휴리스틱 + Simulated Annealing을 써서 해결했습니다. 구현 아이디어 설명은 https://paido.tistory.com/16을 참고해주세요. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 .. 공감수 0 댓글수 0 2019. 7. 6.
SCPC 2019 2차예선 풀이, 후기 SCPC 2차예선이 끝났다. 확실히 1차예선보다는 체감 난이도가 높았다. 1번 같은 경우에는 아이디어는 맞게 잡았는데 실수를 좀 했다. 점화식을 잘못 쓰거나 변수를 선언하고 초기화를 안 한다든지...하지만 제출횟수가 10번이라 다행이다!!ㅋㅋㅋ 4번은 휴리스틱이라 많이 어렵게 느껴졌는데 어떻게든 되지 않을까? 하는 심정으로 막 제출하다가 계속 안 돼서 각성하고 로컬에서 데이터 열심히 만들어서 확인해보고 만점을 받았다. 뭔가 데이터를 랜덤하게도 만들어 보고 절반만 빽빽하게 채워진 것도 만들어 보고 하면서 감을 잡았던 것 같다. 솔직히 이게 되려나... 하면서 제출했는데 만점이 뜬 문제ㅎㅎ 5번은 세그먼트 트리를 \(O(\lg{N})\)으로 구현해야 되는데 너무 오랜만이라 잘못 구현해서 \(O(N)\)이 되.. 공감수 11 댓글수 15 2019. 7. 6.
SCPC 2019 1차예선 5번 구현 소스 코드 SCPC 2019 1차예선 5번. 세포 키우기의 소스 코드입니다. 5번 소스 코드 요청이 많아서 공개합니다. 선분 조각을 합치려면 우선 선분을 \(x\)좌표 순으로 정렬해 갖고 있어야 합니다. 그렇게 갖고 있다면, 합치려는 두 그래프에서 왼쪽 것부터 각각 빼낸 다음, 둘 중에 작은 걸 택하면 됩니다. 두 선분 조각 중 어느 하나가 다른 하나보다 완전히 밑에 있으면 그냥 하나를 버리면 되고요, 그렇지 않다면 선분을 조각내 줍니다. 이때 선분은 좌표를 미리 2배로 해 주었기 때문에 정수점이 아닌 곳에서 만나는 일은 없다고 생각했어요. 편하게 구현하려고 deque를 사용했어요. 쌩 자료구조보다 좀 느리긴 해도 여전히 amortized \(O(1)\)이라서요. 구현 아이디어 설명은 https://paido.ti.. 공감수 1 댓글수 0 2019. 7. 5.
SCPC 2019 1차예선 풀이, 후기 SCPC도 올해로 3년차다. 학기중에 Problem Solving을 못해서 감이 좀 떨어졌을까 걱정했지만 작년보다 결과가 좋았다. 1번-2번-5번-3번-4번 순서로 풀었다. 문제 1. 오르락 내리락 설명 함수 \(F(x)\)가 다음과 같이 정의된다고 하자. $$F(x) = \begin{cases} F(x+1) + 1, & \text{x가 3 이상의 홀수} \\ F(x/2) + 1, & \text{x가 짝수} \\ 0, & x = 1 \end{cases}$$ 정수 \(N, M\) (1 ≤ \(N\) ≤ \(M\) ≤ 1,000,000)을 받아서 \(F(N) + F(N+1) + ... + F(M)\)을 계산하는 것이 문제다. 제한시간: 10,000개 이하의 테스트 케이스에 대한 실행시간 총합이 1초 이내 (.. 공감수 0 댓글수 12 2019. 6. 22.
Randomized Quicksort Problem Solving (PS)를 할 때 정렬은 직접 구현하지 않고 std::sort를 이용하는 것이 상식이다. 왜냐면, 직접 구현하는 것이 까다롭기 때문이다. 퀵소트를 구현할 경우, 까딱하면 O(N^2)가 되어 시간초과를 내기 십상이다. 하지만 Randomization을 구현하고 적절한 tie-breaking을 구현하면 아래와 같이 평균 시간복잡도 O(N lg N)을 낼 수 있다. 코드 설명 기본적인 Quicksort 구현에 Pivot 선택 시 Randomization을 추가한 형태다. 랜덤한 숫자를 하나 골라 srand()를 호출해주면 기본 시드(seed)값에 대해 시간 초과가 나도록 설계된 데이터에서 시간 초과를 피할 수 있다. Randomization을 하더라도 구간 내의 숫자가 모두 같은 .. 공감수 0 댓글수 0 2019. 4. 19.
Windows 설치 방법 1. Windows ISO를 NTFS 혹은 FAT32 파티션에 복사한다. 이때, NTFS 파티션에 복사하는 경우 별도의 FAT32 파티션을 만들어 부트로더를 넣어주어야 한다. (설치 미디어의 \EFI 폴더를 복사) 부트로더가 있는 파티션을 P:, Windows ISO를 복사한 파티션을 Q:라 하자. 2. {ramdiskoptions} 엔트리 생성bcdedit /store P:\EFI\Microsoft\Boot\BCD /create {ramdiskoptions} /d "Ramdisk Options"bcdedit /store P:\EFI\Microsoft\Boot\BCD /set {ramdiskoptions} ramdisksdidevice partition=Q:bcdedit /store P:\EFI\Micr.. 공감수 1 댓글수 0 2019. 2. 26.
Equivalence of DFA, NFA, and ε-NFA Equivalence of DFA and NFAProof(=>): A DFA is always an NFA, by definition.(): A DFA is always an ε-NFA, by definition.( 공감수 0 댓글수 0 2019. 2. 22.
SCPC 2018 본선 2번 풀이. 외계메시지 문제 설명(요약)N개의 정수가 순서대로 주어진다. 이 수열에서 X번 이상 반복되는 패턴 중 가장 긴 패턴의 길이를 구하여라. 단, 패턴은 부분적으로 서로 겹칠 수 있다.제약 조건: N 공감수 0 댓글수 1 2019. 2. 13.
SCPC 2017 본선 4번 풀이. 방 바꾸기 문제 설명www.codeground.org 참조 풀이, Part 1 (부분문제 2)원래 그래프를 G라고 하자. G에서 임의의 간선은 최대 하나의 사이클에만 속하므로, 사이클을 이루는 정점들을 하나로 묶은 그래프 T를 생각하자. 사이클을 이루지 않는 정점은 그대로 홀로 둔다. T는 트리가 된다. 왜냐면, T의 정점들이 사이클을 이룬다면 애초에 하나로 묶였을 것이기 때문이다. * 원래 그래프의 정점과 구분하기 위해 T의 정점과 간선은 슈퍼정점과 슈퍼간선으로 표현할 것이다.* INF = 무한대 (Infinity)의 약자로 쓸 것이다. T의 슈퍼정점들 중, 빈 방의 처음 위치를 포함하는 슈퍼정점이 딱 하나 있을 것이다. 이 슈퍼정점을 트리 T의 루트 R(T)로 하자. 빈 방은 R(T)의 자식슈퍼정점 중 일부를 .. 공감수 0 댓글수 0 2019. 2. 13.
SCPC 2017 본선 3번 풀이. Colony 문제 설명www.codeground.org 참조 부분문제 1 풀이만약 어떤 연도 Y에 캡슐이 도달 가능하다면, 캡슐은 Galaxy1이 어떤 연도 i에 건설한 Colony1[i]에서 출발하여 Galaxy2이 어떤 연도 j에 건설한 Colony2[j]에 도달했을 것이다. Colony1[i]에서 출발한 캡슐이 방문 가능한 지점은 택시거리가 Y-i 이하인 모든 지점이다. 따라서 Colony1[i]와 Colony2[j]의 택시거리가 Y-i 이하인지 확인하면 된다. 전체 시간복잡도는 O(N3)으로 N 공감수 1 댓글수 0 2019. 2. 13.
SCPC 2017 본선 2번 풀이. Bridge 문제 설명(요약)평면 위에 볼록다각형 모양의 두 섬 A와 B가 있다. A와 B는 서로 교차하지 않는다. A와 B 사이에 다리를 놓으려고 하는데, 다리 건설 비용을 최소화하기 위해 다리의 길이를 최소화하려고 한다.다리의 A쪽 끝점 P와 B쪽 끝점 Q에 대해, P는 A의 내부나 경계에, Q는 B나 내부의 경계에 위치해야 한다.다리(선분 PQ)의 길이를 최소화하는 점 P와 Q에 대해, 그 길이를 구하여라.제약 조건: A, B의 꼭짓점 수 N, M은 각각 200,000 이하* 부분문제 1 (82점): N, M 공감수 1 댓글수 0 2019. 2. 13.
SCPC 2016 본선 4번 풀이. 반물질 문제 설명www.codeground.org 참조 제약 조건: 1 공감수 0 댓글수 0 2019. 2. 13.
SCPC 2016 본선 3번 풀이. 폭격 문제 설명2차원 격자칸 형태의 적국에 폭격을 하려고 한다.격자칸의 가로 크기는 N, 세로 크기는 M 이다.좌표는 가장 왼쪽 위 칸을 (1 , 1)로, 가장 오른쪽 아래 칸을 (M,N)으로 표현한다.각 격자칸에 최대 하나의 목표물이 있으며, 전체 목표물의 개수는 P 로 주어진다.각 폭격기는 3X3크기의 영역에 있는 목표물을 모두 파괴할 수 있으며, 그 영역에 두 개 이상의 목표물이 있어야 출격이 가능하다고 한다.적국의 목표물 위치가 주어졌을 때 모든 목표물을 파괴할 수 있는 최소의 폭격기 수를 계산하라.두 개 이상의 폭격기가 하나의 목표를 파괴하는 것도 가능하다.아래 그림에서 왼쪽의 경우는 어떤 경우에도 한 폭격기는 하나의 목표만 파괴할 수 있어서 폭격이 불가능하다.오른쪽의 경우는 두 대의 폭격기가 출동하.. 공감수 0 댓글수 0 2019. 2. 13.
SCPC 2016 2차예선 5번 풀이. 난민촌 문제 설명(요약)평면 위에 N개의 점 (xi, yi)가 있고, N개의 자연수 ai가 주어져 있다. 가상의 평균점 C(xc, yc)와 ai들의 순열 ap(1), ..., ap(N)을 잘 정해 다음 식을 최소화하면 그 최솟값은 얼마인가? 제약 조건: N 공감수 0 댓글수 0 2019. 2. 13.
SCPC 2017 1차예선 5번 풀이. Covernent 문제 설명(요약)2N개가 리프 노드를 포함하여 M(>2N)개의 정점을 갖는 트리 T=(V, E)가 있다. 각 엣지에는 양의 가중치가 부여되어 있다. 이 트리의 리프 노드는 1, 2, ..., 2N까지 번호가 붙어 있고, 노드 2N+1, ..., M은 엣지가 2개 이상 연결된 내부 노드이다. 리프 노드 i와 N+i 중 많아야 하나만 선택할 수 있다고 할 때, 이 조건을 만족하는 어떤 부분집합 X에 대해, 이들을 포함하는 최소 연결그래프(서브트리)를 생각할 수 있다. 이 서브트리의 모든 엣지의 가중치의 합을 S(X)라고 하자. 가능한 모든 X를 고려할 때 S(X)의 최댓값을 구하여라.제약 조건: 2 공감수 0 댓글수 0 2019. 2. 13.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.