본문 바로가기

알고리즘

 (24)
13705-Ax+Bsin(x)=C
[Python]7420-맹독 방벽 www.acmicpc.net/problem/7420 7420번: 맹독 방벽 첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 젖ㅇ수) 다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 �� www.acmicpc.net manoflearning.tistory.com/216 백준 7420번: 맹독 방벽 문제 링크: https://www.acmicpc.net/problem/7420 문제 요약 2차원 상에서 점의 집합이 주어진다. 점의 집합을 모두 포함하고, 집합의 모든 점에서 거리가 L 이상인 도형의 둘레의 최솟값을 구하시오. 문제 manoflearning.tistory..
[Python]10254-고속도로 www.acmicpc.net/problem/10254 10254번: 고속도로 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 �� www.acmicpc.net 볼록껍질과 로테이팅 캘리퍼스를 이용해야하는 문제다. stonejjun.tistory.com/42이 블로그를 참고해서 작성했다. 아직 벡터를 배우지를 않아서 아직은 잘 모르지만, 나중에 기하 배우면 완벽하게 이해할 수 있을 것 같다. import sys input = sys.stdin.readline def ccw(p1, p2, p3): return p1[0]*(p2[1] - p3[1]) + p2[0]*(p..
[Python]4181-Convex Hull www.acmicpc.net/problem/4181 4181번: Convex Hull 때때로 주어진 점들 사이에서 볼록 껍질(Convex Hull)을 찾아내는 기술은 요긴하게 쓰인다. ACM 월드파이널에서 볼록 껍질을 응용해야 하는 문제가 출제되다 보니, 이걸 할 줄 아는 것은 참가자의 소 www.acmicpc.net 그냥 monotone chain알고리즘 돌려서 볼록껍질 구해서 차례대로 출력하면 된다. (정렬은 x오름차순, y오름차순으로) 주의할 것은 볼록껍질을 이루는 몇몇 점이 한선분 위에 있고, 그 선분이 볼록껍질을 이룰때, 사이의 점도 출력해줘야 한다는 것이다. import sys input = sys.stdin.readline n = int(input()) dots = [] dA = dots.a..
[C++]11930-Smallest Enclosing Sphere www.acmicpc.net/problem/11930 문제링크다. 11930번: Smallest Enclosing Sphere 첫째 줄에는 하나의 양의 정수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐 각 점의 좌표를 나타내는 3개의 정수 x, y, z가 주어진다. x, y, z는 -1,000,000보다 크거나 같고 1,000,000보다 www.acmicpc.net 밑에는 비슷한 문제들이다. www.acmicpc.net/problem/2626 2626번: 헬기착륙장 문제를 간단히 하기 위해서 섬의 크기는 무시하고, 섬의 위치를 2차원 정수 좌표로 표시한다. 첫 줄은 섬의 개수를 나타내는 정수 N(2≤N≤1,000)이다. 그 다음 N개의 줄은 각 줄마다 섬의 x 좌표값, ww..
[Python]2389-세상의 중심에서... www.acmicpc.net/problem/2389 2389번: 세상의 중심에서... 첫째 줄에 N(1≤N≤100)이 주어진다. 다음 N개의 줄에는 x, y 좌표가 주어진다. 각각의 좌표는 소수점 여섯째자리까지 주어지며, -600,000 ≤ x, y ≤ 600,000을 만족한다. www.acmicpc.net 비슷한 문제 ssuallassualla.tistory.com/156 처음에 봤을때는 오차를 $10^{-3}$으로 매우 후하게 줘서 쉬운문제일줄 알았다. 그래서 컨벡스헐 그린다음에, 가장 먼 두점 잡고 중점해서 원 그리는 방식으로 접근했다. 당연히 틀렸다. 그래서, wethinknewrise.tistory.com/5이 블로그를 참고해서 풀었다. 어디서는 simulated annealing이라고도 하고,..
[Python]16489-삼각형 해커 내가 처음으로 푼 다이아다.이거풀고 골드3 중간정도였는데 골드2중간까지 한번에갔다.랭킹도 26??에서1676으로 엄청 뛰었다. 실수오차 빼면 진짜 쉽다. 처음 4개는 쭉쭉 가다가 k에서 멈칫했는데, 지오지브라로 그려놓고서 보니까 잘 보였다.그다음에 엄청 설레서 냈다가 실수오차때문에 4번 틀렸다.파이썬 decimal모듈써도 실수오차 줄일려는 노력을 해야 맞는다. 진짜 쉬운 문제였다. 다른 다이아를 안풀어봐서 모르겠는데, 이게 제일 쉬울듯? 풀고난다음에 난이도 기여에가면, 문제 출제자가 실수오차 줄이는 팁과 해설을 올려놨으니, 꼭 보는것을 추천한다.
[Python]1194-달이 차오른다, 가자. https://www.acmicpc.net/problem/11941194번: 달이 차오른다, 가자.첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,www.acmicpc.net요즘 그래프관련 문제가 재밌어서 풀고 있다. 그래프 관련이기도 하고, 제목이 간지나서 풀게 됐다.내가 처음으로 풀어본 골드1 문제다. 처음엔 비트마스크를 할 생각을 못하고, visited[x][y]마다 set을 생성해서 가지고 있는 키를 정렬해서 키 in set이런 방식으로 구현하려는 어마무시한 생각을 했다..비트마스크를 처음 써봤는데, 재밌다. from collection..

티스토리툴바