BOJ 17387 선분 교차2
https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net CCW를 이용하면 쉽게 풀수 있는 문제다. 하지만, 나는 의외의 곳에서 내 코드의 반례를 찾지 못했다. 아래는 내가 처음 작성한 코드이다. #include #include typedef long long ll; using namespace std; int ccw(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){ ll t = (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1); if(t>0) return 1; else if..
KAKAO 2022 파괴되지 않는 건물
https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr 2차원 구간합을 어떻게 처리할지 생각 필요했던 문제였다. 처음에 생각했던 방법은 세그먼트 트리 같이 구간합을 빠르게 구할 수 있는 자료구조 였다. 하지만, 해당 문제를 세그먼트 트리로 구현하기 위해서는 2차원..
BOJ 2143 두 배열의 합
https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 모든 경우의 수를 Naive 하게 구하려고 하면 다음과 같은 시간복잡도가 걸린다. O (n (n C 2) ^2) 문제를 잘 보면 입력 배열의 "부 배열"을 이용해야 함을 알 수 있다. 따라서 누적합을 미리 구해놓으면 구간 [i,j] 의 구간합을 O(1) 만에 구할 수 있다. 이 경우, 시간복잡도는 다음과 같다. O (..
2022 KAKAO Blind 양과 늑대
https://programmers.co.kr/learn/courses/30/lessons/92343?language=python3 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 처음 봤을 땐 그래프를 탐색(일반적인 DFS나 BFS)해가면서 모을 수 있는 최대 양을 갱신하려고 했었다. 하지만 위의 방법대로 구현하면 탐색 순서에 따라 모을 수 있는 양의 수가 달..