Doby's Lab

https://www.acmicpc.net/problem/14565 14565번: 역원(Inverse) 구하기 집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다. 정수 N, A가 주어졌을 때 Zn에서의 A의 www.acmicpc.net Solved By: EEA(Extended Euclidean Algorithm), MMI(Modular Multiplicative Inverse) (곱셈역에 대한 풀이만 하겠습니다.) 확장 유클리드 알고리즘과 모듈러 연산 곱셈 역원에 대해 배우기 좋은 문제였습니다. (a * c) = 1(mod n)이라는 식에서 a가..

확장 유클리드 알고리즘(Extended Eucildean Algorithm)이란 ax + by = c 같은 부정방정식이 주어졌을 때, (x, y)의 정수해를 알아내는 알고리즘입니다. 증명은 따로 하지 않으며 배운 곳까지만 작성하겠습니다. 증명 자료를 찾으려니 이해가 안 되는 부분들이 꽤나 많았습니다. [사전 지식] ax + by = c와 같이 미지수의 개수가 식의 개수보다 많아서 근이 일정하지 않은 방정식을 부정방정식(Underdetermined Equation)이라고 합니다. 그리고, ax + by = c에서 정수해를 구한다고 하였는데 부정방정식에서 정수해를 구하는 방정식을 디오판토스 방정식(Diophantine Equation)이라고 합니다. => 사실 이 용어는 그닥 중요하지 않습니다. ax + b..

https://www.acmicpc.net/problem/11256 Solved By: Greedy Algorithm 상자를 최대한 적게 쓸려면 사이즈가 큰 순서대로 상자를 쓰면 된다. => 그리디 알고리즘인 이유 상자의 사이즈 크기 순서대로 배열을 정렬하고, 사탕의 개수에서 상자의 크기를 하나씩 빼가면서 다 뺐을 경우, 몇 개까지 상자를 사용했는지 저장하여 출력했다. #include #include #include using namespace std; bool cmp(int a, int b){return a > b;} int main(){ int T; cin >> T; vector res; while(T--){ int n, m; cin >> n >> m; vector v; for(int i = 0; i..

https://www.acmicpc.net/problem/15720 15720번: 카우버거 첫째 줄에는 주문한 버거의 개수 B, 사이드 메뉴의 개수 C, 음료의 개수 D가 공백을 사이에 두고 순서대로 주어진다. (1 ≤ B, C, D ≤ 1,000) 둘째 줄에는 각 버거의 가격이 공백을 사이에 두고 주어진 www.acmicpc.net Solved By: Greedy Algorithm 세트가 만들어질 수 있는 최대의 개수를 minv라고 하겠습니다. 버거에서 minv개까지 내림차순으로 비용에 0.9를 곱합니다. 왜냐하면 세트로 만들었을 때, 어떠한 경우에도 다른 값에 할인을 했다가는 최솟값을 가질 수 없기 때문에 가장 큰 값에 0.9를 곱하여 다 더해주는 것이 맞습니다. => 그리디 알고리즘인 이유 버거와 ..

유클리드 호제법(Euclidean Algorithm)은 MOD 연산을 이용하여 두 수 간의 GCD(Greatest Common Divisior)를 빠르게 구하는 방법입니다. 코드로 구현하는 방법에도 반복과 재귀가 있습니다. 각 방법에 대하여 장단점이 있으며 두 방법 모두 MOD 연산을 사용하기 때문에 작은 수에서 큰 수로 MOD 연산을 하게 될 경우 알아서 swap이 되는 특징이 있으므로 따로 swap을 필요로 하지는 않습니다. #include using namespace std; int gcd1(int a, int b){ int temp; while(b){ temp = b; b = a % b; a = temp; } return a; } int gcd2(int a, int b){ // recursive ..

https://www.acmicpc.net/problem/14955 14955번: How Many to Be Happy? Let G be a connected simple undirected graph where each edge has an associated weight. Let’s consider the popular MST (Minimum Spanning Tree) problem. Today, we will see, for each edge e, how much modification on G is needed to make e part of an MST for www.acmicpc.net Solved By: MST, MFMC Undirected Graph에서 우선 MST를 구합니다. -> Kru..

https://www.acmicpc.net/problem/14248 14248번: 점프 점프 첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000) 다음 줄에는 출 www.acmicpc.net Solved By: BFS #include #include #include #define MAX 100001 using namespace std; vector arr(MAX, 0); int n, s; int bfs(int node){ int cnt = 0; cnt++; queue q; q.push(node); vector visited(n + 1, false); vis..

https://www.acmicpc.net/problem/21010 21010번: Slow Down Input begins with a line containing two integers: N M (2 ≤ N ≤ 1000; 1 ≤ M ≤ 20 000) representing the number of junctions and roads in Slow Town, respectively. The next M lines each contains three integers: uj vj tj (1 ≤ uj < vj ≤ N; 1 ≤ tj www.acmicpc.net Solved By: Dijkstra, MFMC 다익스트라를 돌려서 최단 경로를 구합니다. 그리고, 백준 1948번:임계 경로(https://draw-co..