728x90 백준브실골/Geometry12 백준 1435, 네 점 개요 문제 링크 골드 2, Geometry 네 점의 3차원 공간 내 존재 가능성 여부 출력하기 접근 애매한 순수 기하학 문제, 정답율이 7.6%인 요상한 문제이다. 핵심은 3차원 공간 내에 존재 가능성을 찾는 것인데, 이 부분이 쉽게 생각해내기 어렵다. 우선 삼각형의 구성 조건을 생각한 사람이 많을 것이다. AB+BC >= AC를 생각하고 24개 조합 (4개 점 중 3개, 3개 순서)에 대해 이 조건을 모두 돌려볼까? 하면 마지막 케이스가 안된다. 아래 그림을 보자. 모든 조합에서 삼각형이 구성가능하고, D는 AC위에 존재하는데, BD가 5가 될 수 없다. D는 항상 AC위에 저 지점에 존재해야 하므로 ABCD는 모두 고정점이다. 그래서 BD의 길이도 고정길이가 나오는데 그 길이가 5가 아닌 것. 예시가.. 2023. 2. 21. 백준 14604, Over Fitting (Small) 개요 문제 링크 골드 1, Geometry 한 구역에 몰아진 특정점의 개수를 최대로 하는 선분 구하기 접근 Over fitting이란 어떤 데이터가 classifier에만 최적화된 경우를 말하는데, 데이터가 조금만 달라져도 출력이 달라지기 때문에 AI의 성능이 떨어진다. 즉 overfitting = 모델의 정확도 하락. 문제의 의미는 overfitting이 나도 상관 없으니 최대한 많이 분류하는 선분을 그어보라는 것 같다. 실제로 이 문제는 2차원 데이터의 1차원 분류기만 이용했지만, 변수의 개수에 따라 N-1차원의 weight 행렬을 이용하는 것이 ML (machine learning)의 원리인 것으로 기억한다. 플1의 Large 문제도 있던데 시간되면 풀어봐야겠다. 둘의 접근은 매우 다른데, 이 문제.. 2023. 2. 18. 백준 13847, Geometry?! Why Not?? 개요 문제 링크 골드 4, Geometry 끝점과 원점을 이은 직선과 경로의 사이 넓이 접근 하루의 시작을 순수 기하학 문제로 해보자. 뭔가 쉬운 방법이 있지 않을까 고민했는데 그런거 없었다. 하나하나 교점 구해서 삼각형 넓이 더해주는 것이 최선. 그래도 경우를 나눠보자. 우선 Y값이 같은 점의 집합에 대해 사다리꼴의 넓이의 합을 구해줄 것인데, Y값이 [L,R]에서 같을 때, Y[L], Y[R]이 모두 직선의 아래에 있거나 위에 있으면 단순히 사다리꼴의 넓이를 구한다. 그렇지 않다면 중간에 직선과 교점이 존재하는데, 그 교점을 구하고 왼쪽삼각형과 오른쪽 삼각형의 넓이를 구한다. 이때 교점의 좌표는 (Y/기울기, Y) Y값의 할당은 어떻게 하느냐? R이면 X추가하고 Y값 부여, U이면 Y값만 추가해준다... 2023. 2. 18. 백준 2778, 측량사 지윤 개요 문제 링크 골드 3, Geometry 세 직선으로 구성되는 삼각형의 넓이 접근 직선의 방정식과 삼각형, 고1에서 다루는 내용이었나? 기억이 안난다. 그만큼 알고리즘 없이 기하학적 지식만으로 풀어내는 문제이다. 교점 3개를 구하고 ccw를 구해주면 끝난다. 크기가 무한이 되는 경우가 있으니 평행을 체크하면 되고, 평행은 방향벡터의 방향성을 보면 되므로, (b1,a1) // (b2,a2) => b1/b2 = a1/a2 => b1×a2 = b2×a1을 사용하면 된다. 고등과정으로 풀 수도 있지만 벡터에 익숙해지자. 점이 같은 경우는 고려 안해도 되나? 안해도 된다. 어차피 ccw를 구해주면 0이 된다. Pseudo code cross() { x = (b1*c2-c1*b2) / (a1*b2-b1*a2) y.. 2023. 2. 15. 백준 5180, 피자! 개요 문제 링크 골드 3, Geometry 포함하는 특정점의 개수가 같고 크기가 같도록 원을 나누는 최대 개수 접근 요상한 애드혹 문제, 틀왜맞이 절로 나왔다. 이분탐색이나, 스위핑, 별의 별 방법을 다 생각해봤지만 N수가 적어서 그냥 for문을 돌면서 다 체크해주면 통과한다. 다 체크란 어떻게 하냐? n부터 2까지 조각을 쪼갤 건데, 시작을 0부터 2π/n까지 하고, 개수가 모두 같으면 조각수를 출력해주면 된다. 즉 4중 for문 돌려주면 된다. Pseudo code for (piece = n~2) angle_diff = 2pi/piece for (start = 0~angle_diff) for (i = 0~piece) piece_start = start + i * angle_diff piece_end .. 2023. 2. 15. 백준 2013, 선그리기 개요 문제 링크 골드 3, Geometry 평행하고 겹치는 부분이 있는 선을 통합한 뒤의 서로 다른 선의 개수 접근 모두의 맞왜틀 문제. 평균 시도가 11회인 아주 번거로운 문제이다. 만약 다 확인해봤다면 floating point error를 확인하자. double을 오차 없이 다루기 위해 long long을 사용하자. 입력을 받아올 때 아래와 같이 해주면 된다. long long = (long long)(double*100+0.5) 0.5를 더해주는 것은 왜냐? 예를 들어 9.99와 같은 수에 100을 곱하면 998.99999와 같이 변해버릴 수 있다. 이럴 때는 바로 변환하면 998이 되므로 0.5를 더해 내려주면 999를 잘 받아올 수 있다. 문제로 돌아와서, N=10000인데도 O(N^2)이 먹.. 2023. 2. 14. 백준 2773, 바깥 삼각형의 중심 개요 문제 링크 골드 3, Geometry 삼각형의 각 선분으로 만든 정사각형의 꼭짓점을 연결한 중점과 삼각형의 꼭짓점의 연장선의 교점 접근 기하학 문제 중 새로운 원리나 알고리즘을 이용하는 것이 아닌 그냥 단순한 문제, 그래서 cpp의 class를 활용해 코드를 짜고 c언어에서 다시 짜봤다. 내 생각은 우선 벡터AB에 대해 점A에서 직교하고 AB와 크기가 같은 벡터는 두개가 있다. 위로 가거나, 아래로 가거나. 어떤 벡터 (x,y)에 대해 수직이고 크기가 같은 벡터는 (y, -x), (-y, x)가 있다. 내적과 벡터의 크기를 알고만 있다면 당연하게 구할 수 있다. 그럼 둘 중 어떤 벡터를 고르냐? 하면 끝점의 AB에 대한 ccw가 C점과 다른 점을 고른다. 왜냐하면 C의 반대편에 존재해야 하기 때문이.. 2023. 2. 14. 백준 16115, 팬이에요 개요 문제 링크 골드 3, 기하학 자취가 원이 되도록 회전하는 최소 각도 구하기 접근 접근 자체는 매우 쉬움, 우선 원점으로부터의 거리가 가장 먼 점들만 고려해야 함. 이유는 더 짧은 점은 아무리 고려해도 가장 큰 원을 만들지 못하기 때문. Class를 처음 써보면서 operator도 써보고 CCW도 써보고 해봤는데 생각보다 부질없는 일이었음. 각도만 고려하면 돼서 매우 단순함. 핵심은 두 점의 사잇각을 생각해야 함. x축으로부터의 각에 대해 정렬한 다음 두 점의 사잇각의 최댓값이 정답. 처음에는 2π와 비교하면서 최솟값을 업데이트하려 했는데 틀렸음. 하지만 여기까지 하면 정답이 안나옴. 아래 케이스를 보자. // (0,1) (1,0) output = 90 answer = 270 문제는 angle[0] .. 2023. 2. 8. 백준 1430, 공격 개요 문제 링크 골드 4, 기하학, BFS 가치를 절반씩 줄이며 2차원 이동할 때 특정점까지 최대 가치를 보존하며 이동하는 경우 접근 이동을 계속할 때 유효점에 도달하면 최대값을 갱신해주면 됨. 우선 이 점이 유효한지를 저장해야. 이동을 계속한다? = 방문점 체크 필요함. N=50이니까 DFS나 BFS 어떤것을 써도 상관 없는데, C++의 미친 장점, STL이 있으니까 큐를 써줄 것. 그냥 모든 점이 갈 수 있고 아직 간 적 없다면 무조건 추가해주면 됨. 갈 수 있다 = 거리가 R이하이다. Pseudo code while (x = Q에 대해) 방문[x] = 1 for (y = 모든 점) if (y 이미 방문함) continue if (x->y 거리가 R초과) continue Q.push(y) Source.. 2023. 2. 8. 백준 22942, 데이터 체커 개요 문제 링크 골드 4, 기하학, 스위핑 모든 구간의 교차 여부 판정 접근 스위핑 문제, 1263번과 매우 유사하므로 정렬 후 업데이트하면서 확인하면 끝남. 정렬은 어떻게 할 것이냐? 시작이 같으면 끝이 빠른 순 혹은 끝이 같으면 시작이 빠른 순 중에 고르면 된다. 어차피 둘 중 잘 찍으면 맞음. 이후에 교차여부는 어떻게 판정하냐? 하면 구간의 양 끝점이 둘 다 안에 있거나 밖에 있으면 된다. Pseudo code compare() { if (시작이 같으면) 끝이 빠른 순 else 시작이 빠른 순 } sort_by_compare() for (x = 원) // 시작과 끝이 모두 내부에 존재하면 c1=c2=1 // 모두 외부에 존재하면 c1=c2=0 c1 = start < x.start < end c2 =.. 2023. 2. 8. 다음 728x90
