본문 바로가기
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개에 대한 실행시간 .. 더보기
유한분배격자의 기본정리 (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)라고 한다.. 더보기
SCPC 2019 본선 후기 오늘은 대망의(!) SCPC 본선이 있던 날. 지난 두 번의 대회에서 상을 못 받았고 지쳐가고 있었지만, 솔직히 방학 때만 벼락치기로 하면서 상 받기를 기대하는 나란 참...! 어쨌든 이번 예선 결과가 좋아서 나름 기대를 하고 대회장에 갔다. 가서 과자부터 집어다 쌓아놓으려고 했는데, 어쩐 일인지 올해는 초콜릿 바가 없어서 아쉬웠다. 아쉬운대로 일단 쿠키랑 음료를 가져다 놓았다. 늘 그렇듯이 1시 반에 대회가 시작되었다. 당연히 1번 문제부터 잡았다. 1번 문제는 이분 탐색으로 \(O(N \lg{N})\)으로 해결되는 게 당연한 문제인데 std::vector에다가 std::find를 쓰는 바람에 \(O(N^2)\)가 되어 계속 시간초과가 났었다. 90명이나 풀었는데 왜 난 안 되지...? 하다가 일단 2.. 더보기
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 .. 더보기
SCPC 2019 2차예선 풀이, 후기 SCPC 2차예선이 끝났다. 확실히 1차예선보다는 체감 난이도가 높았다. 1번 같은 경우에는 아이디어는 맞게 잡았는데 실수를 좀 했다. 점화식을 잘못 쓰거나 변수를 선언하고 초기화를 안 한다든지...하지만 제출횟수가 10번이라 다행이다!!ㅋㅋㅋ 4번은 휴리스틱이라 많이 어렵게 느껴졌는데 어떻게든 되지 않을까? 하는 심정으로 막 제출하다가 계속 안 돼서 각성하고 로컬에서 데이터 열심히 만들어서 확인해보고 만점을 받았다. 뭔가 데이터를 랜덤하게도 만들어 보고 절반만 빽빽하게 채워진 것도 만들어 보고 하면서 감을 잡았던 것 같다. 솔직히 이게 되려나... 하면서 제출했는데 만점이 뜬 문제ㅎㅎ 5번은 세그먼트 트리를 \(O(\lg{N})\)으로 구현해야 되는데 너무 오랜만이라 잘못 구현해서 \(O(N)\)이 되.. 더보기
SCPC 2019 1차예선 5번 구현 소스 코드 SCPC 2019 1차예선 5번. 세포 키우기의 소스 코드입니다. 5번 소스 코드 요청이 많아서 공개합니다. 선분 조각을 합치려면 우선 선분을 \(x\)좌표 순으로 정렬해 갖고 있어야 합니다. 그렇게 갖고 있다면, 합치려는 두 그래프에서 왼쪽 것부터 각각 빼낸 다음, 둘 중에 작은 걸 택하면 됩니다. 두 선분 조각 중 어느 하나가 다른 하나보다 완전히 밑에 있으면 그냥 하나를 버리면 되고요, 그렇지 않다면 선분을 조각내 줍니다. 이때 선분은 좌표를 미리 2배로 해 주었기 때문에 정수점이 아닌 곳에서 만나는 일은 없다고 생각했어요. 편하게 구현하려고 deque를 사용했어요. 쌩 자료구조보다 좀 느리긴 해도 여전히 amortized \(O(1)\)이라서요. 구현 아이디어 설명은 https://paido.ti.. 더보기
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초 이내 (.. 더보기
Randomized Quicksort Problem Solving (PS)를 할 때 정렬은 직접 구현하지 않고 std::sort를 이용하는 것이 상식이다. 왜냐면, 직접 구현하는 것이 까다롭기 때문이다. 퀵소트를 구현할 경우, 까딱하면 O(N^2)가 되어 시간초과를 내기 십상이다. 하지만 Randomization을 구현하고 적절한 tie-breaking을 구현하면 아래와 같이 평균 시간복잡도 O(N lg N)을 낼 수 있다. 코드 설명 기본적인 Quicksort 구현에 Pivot 선택 시 Randomization을 추가한 형태다. 랜덤한 숫자를 하나 골라 srand()를 호출해주면 기본 시드(seed)값에 대해 시간 초과가 나도록 설계된 데이터에서 시간 초과를 피할 수 있다. Randomization을 하더라도 구간 내의 숫자가 모두 같은 .. 더보기

티스토리툴바