코딩테스트/백준 코틀린31 [백준] 30_1. CCW(Counter Clock Wise) 알고리즘 설명 | 수알못 선분 교차 2 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 설명 해당 문제는 CCW(Counter Clock Wise)라는 다소 생소한 알고리즘을 활용하여 풀 수 있는 문제입니다. 수학 벡터와 관련된 알고리즘이다 보니 포기가 마려웠지만 그래도 한 번 이해해보고자 하였습니다. 이번 글에서는 CCW 알고리즘에 대해 제가 이해한 과정을 최대한 풀어서 설명해 보겠습니다. CCW는 어떤 알고리즘인가? 평면 위에 3개의 점이 주어졌을 때 세 점의 방향을 알 수 있는 알고리즘입니다. 나올 수 있는 방향은 총 3가지입니다. 반 시계 방향 직선 시계 방향 ccw의 알고리즘에서는 반 .. 2024. 2. 2. [백준] 30. 가장 긴 증가하는 부분 수열 2 12015 해설 가장 긴 증가하는 부분 수열 2 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 갈수록 풀지 못하는 문제가 많아지고 있습니다. 해당 문제도 마찬가지로 풀지 못하였는데 풀이 방법이 전혀 생각지도 못한 방법이면서 너무나 간단하여 스스로 정리할 겸 글을 쓰게 되었습니다. 문제 풀이 이전에 풀었던 가장 긴 증가하는 부분 수열 1의 경우 dp를 통해 시간 복잡도 O(n^2)으로 문제를 해결할 수 있었습니다. 하지만 2의 경우 N의 범위가 1,000,000이기 때문에 다른 방법을 사용해 줘야 됩니다. 정답은 이진 탐색을 .. 2024. 1. 29. [백준] 29. 할로윈의 양아치 20303 해설 할로윈의 양아치 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 문제 나쁜 스브러스가 k-1명 이하의 아이들을 상대로 최대의 사탕개수를 빼앗으면 되는 문제입니다. 다만 아이들은 각각 친구를 가지며 어떤 아이의 사탕을 뺏을 경우 그 아이와 친구관계로 이루어진 모든 아이의 사탕까지 뺏어줘야 됩니다. 풀이 백준 Class 순서에 맞게 문제를 풀어왔기 때문에 해당 문제는 어렵지 않게 풀 수 있었습니다. K-1명 이하의 친구들을 상대로.. 2024. 1. 23. [백준] 28. 행렬 곱셈 순서 11049 해설 행렬 곱셈 순서 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 2차원 배열을 이용한 DP문제라는 것을 알아도 아이디어를 찾고 구현하는 데까지 꽤 까다로웠던 문제입니다. 풀이 최소한의 연산 횟수가 나올 수 있도록 행렬의 곱셈 순서를 결정해 주면 되는 문제입니다. 다만 행렬이기 때문에 행렬의 앞 뒤 순서는 지켜줘야 됩니다. ex) 행렬 A, B, C 가 주어졌을 때 - A x B x C 가능 - A x (B x C) 가능 - A x C x B 불가능 처음에는 뭔가 수학적 이론을 이용한 문제인가 .. 2024. 1. 22. 이전 1 2 3 4 ··· 8 다음 반응형
