쾌락없는 책임 (공부)
-
픽셀 위에 직선 그리는 알고리즘 - 2. Bresenham’s Algorithm, 브레젠헴 알고리즘쾌락없는 책임 (공부)/그래픽스 2021. 10. 23. 22:32
픽셀 위에 직선 그리는 알고리즘 - 1. Digital Differential Analyzer (DDA) 알고리즘 화면에 직선을 그리기 위해 고려할 것들 - 현대 모니터들은 전부 픽셀로 이루어져 있습니다. - 이 위에 직선을 그린다면 최대한 직선에 가깝게 표현되어야 합니다. 이 뜻은 픽셀들의 연속으로 husk321.tistory.com 서론 이전에 픽셀에 직선을 그리는 알고리즘으로 DDA 알고리즘을 알아봤었습니다. 글 마지막에 설명한 대로 DDA 알고리즘의 경우 float과 관련한 연산들이 있어 이를 개선해줄 필요가 있었습니다. 여기서 생각을 틀어서 어차피 사각형으로 된 좌표들 위에 픽셀을 찍는 것이니 직선의 경우 (x, y) 에 점을 찍었다면 다음 점은 (x+1, y+1) 이거나 (x+1, y), 2개..
-
픽셀 위에 직선 그리는 알고리즘 - 1. Digital Differential Analyzer (DDA) 알고리즘쾌락없는 책임 (공부)/그래픽스 2021. 10. 23. 16:28
화면에 직선을 그리기 위해 고려할 것들 - 현대 모니터들은 전부 픽셀로 이루어져 있습니다. - 이 위에 직선을 그린다면 최대한 직선에 가깝게 표현되어야 합니다. 이 뜻은 픽셀들의 연속으로 되어야 하며 끊기지 않아야 한다는 것입니다. - 픽셀의 중심이 좌표의 정수 부분이 됩니다. Digital Differential Analyzer - DDA 알고리즘 DDA 알고리즘은 양 끝점이 주어졌을 때 화면 위 직선을 그릴 수 있는 알고리즘입니다. 원리는 아래에 있으며 아주 간단합니다. 양 끝점을 이용해서 X, Y의 증분을 구합니다. 이후 X 가 1 증가할 때 Y가 어느정도로 증가하는지를 계산, 좌표를 구하고 해당 좌표의 픽셀을 채워줍니다. 위 정의의 경우 X가 +1 될때 Y가 어느정도로 증가하는지를 구하는 것으로 ..
-
최소 신장 트리(MST) 구하는 알고리즘 - 크루스칼 알고리즘, 프림 알고리즘쾌락없는 책임 (공부)/알고리즘 공부 2021. 10. 17. 22:41
앞선 요약 - 크루스칼 알고리즘은 Union Find 자료구조(=알고리즘)을 알고 있어야 합니다. 합집합 찾기 - Union Find, 유니온 파인드 알고리즘 합집합 찾기 - Union Find 노드들이 존재하고 있을 때 같은 집합에 있는가를 판별하는 알고리즘으로 Diskoint-set 자료구조를 사용하는 알고리즘입니다. 어느 곳에서는 Union Find를 자료구조로 보는 곳 husk321.tistory.com - 간선이 많은 경우 프림 알고리즘, 간선이 적은 경우 크루스칼 알고리즘을 사용하면 효율적입니다. - 본 포스팅은 백준의 1197번 MST 문제를 바탕으로 설명하고 있습니다. 크루스칼 알고리즘 (Kruskal's Algorithm) #include #include #include using nam..
-
2261 백준 - 가장 가까운 두 점, Closest Pair 알고리즘, 분할정복쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 10. 9. 18:10
2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net #include #include #include #include using namespace std; struct Point{ int x; int y; bool operator < (const Point &b) const{ if(x == b.x) return y < b.y; else return x < b.x; } }; int Distance(Point a, Point b){ return (a.x - b.x) * (a.x - b...
-
백준 1300 - K번째 수, C++, 이분탐색쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 9. 21. 13:12
1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net #include #include using namespace std; int n, k; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; int left = 1, right = k, res = -1; while(left
-
백준 1644 - 소수의 연속합, C++, 에라토스테네스의 채, 두 포인터쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 9. 20. 09:53
1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net #include #include using namespace std; int n; long long arr[4000001]; vector primeNumber; void FindPrime(){ arr[0] = -1; arr[1] = -1; for(long long i = 2; i
-
백준 14921 - 용액 합성하기 ,C++쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 9. 19. 12:03
14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당 www.acmicpc.net #include #include #include using namespace std; int n; int main(){ scanf("%d", &n); vector liquid(n); for(int i = 0; i < n; i++) scanf("%d", &liquid[i]); // pointer int left = 0; int right = n - 1; int result = 2100000000; // solution while(left ..
-
13975 백준 - 파일 합치기 3, C++, 우선순위 큐쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 9. 18. 14:43
13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net #include #include using namespace std; int t; int main(){ scanf("%d", &t); while (t--){ long long ans = 0, input; int k; priority_queue pq; scanf("%d", &k); for(int i = 0; i < k; i++){ scanf("%lld", &input); pq.push(-input); } int count = 0; while(!pq.empty()..