쾌락없는 책임 (공부)
-
백준 1717 집합의 표현 - C++, Union find쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 6. 29. 10:16
1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net #include using namespace std; int parent[1000001]; int FindParent(int x){ if(x == parent[x]) return x; return parent[x] = FindParent(parent[x]); } void Merge(int x, int y){ x = FindParent(x); y = FindParent(y); if(x == y) return; else pa..
-
CCW - Counter Clockwise, 벡터의 외적쾌락없는 책임 (공부)/알고리즘 공부 2021. 6. 28. 20:36
좌표만으로 넓이를 구해야 하는 경우가 있다 간혹 알고리즘 문제를 풀 때 주어진 좌표만으로 넓이를 구해야 하는 경우가 있습니다. 일단적인 직사각형이라고 하면 쉽게 구할 수 있으나 간혹 5각형 이상의 다각형들이 나오기 때문에 이를 위한 알고리즘이 필요하게 됩니다. 이 때 사용하게 되는 알고리즘이 CCW (Counter Clockwise)로 백터의 외적을 이용해서 넓이를 구하는 공식입니다. 외적에 대한 내용은 수학과 관련한 이야기니 코드적으로 알아볼 것만 보겠습니다. CCW CCW = { (x1 * y2) + (x2 * y3) + (x3 * y1) } - { (y1 * x2) + (y2 * x3) + (y3 * x1) } 위 공식이 두 벡터를 통해서 방향성을 구한 것입니다. CCW의 값에 따라 방향이 정해지게..
-
에라토스테네스의 채 - 소수 구하기쾌락없는 책임 (공부)/알고리즘 공부 2021. 6. 27. 13:31
에라토스테네스의 채 특정 범위의 소수를 판정하는데 유용한 알고리즘으로 만일 '1개의 수'가 소수인지를 판정하고 싶다면 다른 알고리즘을 사용하는게 더 좋습니다. 기본적인 원리는 수학 시간에 많이 봤습니다. 일단 2를 제외한 배수들을 전부 지우고 그 다음은 3의 배수들, 4는 이미 지워졌으니 5의 배수를... 이런 식으로 수를 지워나가면 됩니다. 아래 위키백과의 사진을 탐고한다면 바로 이해할 수 있을 것입니다. 알고리즘으로서 에라토스테네스의 채 백준 실버 문제부터 자주 등장하게 되며 소수를 판정하는 문제들에 자주 사용하게 됩니다. 특히 범위 내 소수를 구할 수 있다는 알고리즘에서 매력적이며 정말 간단하게 구현이 가능한 알고리즘입니다. 에라토스테네스의 채 알고리즘의 시간복잡도는 O(nlog(logn))으로 꽤..
-
백준 2660 회장뽑기 - C++, 플로이드-와샬쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 6. 26. 21:57
2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net #include #include #include using namespace std; int n, score, num, minnium; int vote[51][51]; int result[51]; int main(){ scanf("%d", &n); for(int i = 0; i
-
백준 3649 로봇 프로젝트 - C++, 두 포인터, 예외 찾기쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 6. 26. 16:25
3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net #include #include using namespace std; // 1cm = 10000000 um // 구멍의 너비, 레고 조각수, 레고 조각의 길이 int x, n, l; int lego[1000001]; int main(){ ios::sync_with_stdio(false); cin.tie(); cout.tie(); while(cin >> x >> n){ // input for(int i = 0; i < n; i++) cin..
-
유클리드 호제법 - 최대 공약수 구하기쾌락없는 책임 (공부)/알고리즘 공부 2021. 6. 25. 11:17
소스코드 #include using namespace std; int gcd(int n, int m){ int temp; while(m){ temp = n%m; n = m; m = temp; } return n; } 최대 공약수를 구하는 O(log(n+m)) 알고리즘 기본 생각으로 알고리즘을 짜게 되면 nm의 시간 복잡도가 주어지게 됩니다. 1부터 계속해서 수를 검증해야 하기 때문에 테스트 케이스가 너무 많은 경우 시간이 너무 오래 걸려 문제를 풀 수 없게 됩니다. 조금 더 풀어쓰기 위 예시를 봤을 때 나머지가 0이 되는 연산에서의 분모가 최대 공약수가 됩니다. 코딩을 하는게 목적이니 증명에 대해서는 다음에 이야기하겠습니다. 최소 공배수를 구하는 경우 유클리드 호제법으로 최대 공약수를 구한 다음 (val..
-
백준 14442 벽 부수고 이동하기 2 - C++, BFS쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 6. 24. 21:09
14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net #include #include #include using namespace std; int n, m, k; int goX[4] = { 0, 0, 1, -1 }; int goY[4] = { 1, -1, 0, 0 }; int map[1001][1001]; int cost[1001][1001][11]; int BFS(){ queue q; q.push(make_pair(make_pair(0, 0), 0)); cost[0][0][0] ..
-
백준 2473 세 용액 - C++, 두 포인터쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 6. 24. 19:45
2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net #include #include using namespace std; int n; long long res = 3000000001; int first, second, third; long long arr[5001]; void search(){ for(int i = 0; i < n; i++){ int l = i + 1; int r = n - 1; while(l < r){ long long sum = arr[i] + arr[l] + arr[r]..