본문 바로가기

분류 전체보기

 (42)
Union-Find 시뮬레이터 Python과 pygame을 이용해 Union-Find자료구조의 시뮬레이터를 만들어 봤다. 경로압축할지 선택 할 수 있다. 노드의 연결상태를 그려주는 코드가 짜기 매우 힘들었다.ㅜㅜ 결국 DFS를 사용해 해결했다. 다만, 너무 노드 연결을 많이하면 연결상태 알려주는 그림이 이상해지니, 조금만 해보자. 이번에도 코드가 구데기니 사용만 하자. import pygame def find(n): if p[n] == n: return n return find(p[n]) def beautifulFind(n): return p[n] def optimizedFind(n): if p[n] == n: return n p[n] = optimizedFind(p[n]) return p[n] def union(n1,n2): glo..
최소크기 외접원-경사하강법 시뮬레이터 최소크기 외접원을 구하는 알고리즘 중에는 경사하강법이 있다. 이미 설명이 잘 되어있는 글이 많으므로, 시뮬레이터를 통해 이해에 도움을 주려고 한다. 아래에 설명이 잘 되어있는 글을 링크 걸어놨다. wethinknewrise.tistory.com/5 [백준 2389] 세상의 중심에서... https://www.acmicpc.net/problem/2389 2389번: 세상의 중심에서... 첫째 줄에 N(1≤N≤100)이 주어진다. 다음 N개의 줄에는 x, y 좌표가 주어진다. 각각의 좌표는 소수점 여섯째자리까지 주어지며, -600,000 ≤ x.. wethinknewrise.tistory.com www.secmem.org/blog/2019/04/08/Smallest-Enclosing-Circle/ 최소 외접..
Monotone Chain 시뮬레이터 볼록껍질 만드는 알고리즘이다. en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain 파이썬 코드 보고서 이해하는게 제일 쉬웠다. Graham Scan에 비해서 안유명한 것같은데, 개인적으로는 Graham Scan보다 매우 좋아함. 각도 정렬이 아닌, 좌표가지고 정렬을 하기 때문이다. 아래는 이해를 돕기 위해 pygame을 이용해 볼록껍질이 어떻게 만들어지는지 표현한 것이다. 코드는 진짜 구데기니까 이해하지말고 사용만 하자. FPS가 낮을 수록 천천히 볼 수 있다.(단, 정수여야함) 중간에 나가는게 안된다. 나갈려면 alt+tab누르고 거기서 끄면 된다. 아니면 볼록껍질 완성되고 10초뒤에 꺼진다. import ..
[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모듈써도 실수오차 줄일려는 노력을 해야 맞는다. 진짜 쉬운 문제였다. 다른 다이아를 안풀어봐서 모르겠는데, 이게 제일 쉬울듯? 풀고난다음에 난이도 기여에가면, 문제 출제자가 실수오차 줄이는 팁과 해설을 올려놨으니, 꼭 보는것을 추천한다.

티스토리툴바