KOI 기출2 [KOI 기출] XCorr (2018 전국 고2) 처음 이 문제를 봤을 때는 굉장히 식도 많고 복잡한 대수학이나 자료구조를 써야 할 것만 같아서 겁을 많이 먹었었는데, 생각해보니 이론적으로 어려운 부분은 없다. (간단한 수학+이진탐색) 구현이 좀 짜증날 수는 있는데, 침착하게 식을 세워보면 된다. 문제 보기 백준 15976번 접근 방법 1. 노가다 일단 정의에 충실하게 \( XCorr(t) \)를 구하는 함수를 만들어 모든 \(t\)에 대해 일일이 구한 값을 더한다면, XCorr 한 번 구하는 데 시간이 \(O(n)\)이므로 총 \( O((b-a)n) \)이라는 시간복잡도가 나온다. 정의에 충실하게 짠 \(XCorr\) 함수는 대충대충 써보면 다음과 같다. (테스트는 안 해봤는데 맞겠지...?) int xcorr(int t) { int sum = 0; .. 2020. 3. 1. [KOI 기출] 두 박스 (2018 전국 중1) 이 문제는 알고리즘 문제는 아니지만, 그냥 풀면 복잡한 문제를 얼마나 쉽게 단순화할 수 있는지를 잘 보여주는 문제다. 문제 보기 정올 3232번, 백준 15973번 접근 방법 1. 노가다 노가다로 찾아도 Line은 "비교적" 쉽게 찾을 수 있다. 아마 조건문을 한 15개쯤 쓰면 Line과 Point는 판별할 수 있다. Line을 찾으려면 공유하는 x 또는 y좌표가 있는지 찾은 후에, 내접하는지, 외접하는지, 아니면 만나지 않는지만 따져주면 된다. x 좌표 하나만을 공유하는 경우는 다음과 같은 것들이 있다. (물론 왼쪽 변의 위치 관계도 고려하고, 저것들은 선대칭한 케이스들도 고려해야 하지만, 대표적으로는 저렇게 나타낼 수 있다.) 이중 마지막 2개가 Line이다. Point는 비슷하게 x좌표 하나와 y좌.. 2019. 7. 19. 이전 1 다음
