본문 바로가기

Algorithm/Implementation

 (746)
(C++) - 백준(BOJ) 10830번 : 행렬 제곱 답 문제링크 : https://www.acmicpc.net/problem/10830 행렬 제곱을 구현해보는 문제였습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include using namespace std;long long a[6][6],ans[6][6],c[6][6],n,b;void cal(long long a[6][6], long long b[6][6]){ for (int i = 1; i 0) { if (b % 2 == 1)//지수가 홀수면 { cal(ans, a); } cal(a, a); b /= 2; } for (int i = 1; i
(C++) - 백준(BOJ) 1629번 : 곱셈 답 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이방법 a^b%c를 구하는 문제다. a를 b번 곱하게 되면 O(b)의 시간이 거리게 되지만 a ^ b/2 * a ^ b/2 로 곱하게 된다면 시간은 O(2 * logN)의 시간이 걸린다. 따라서 이 문제는 분할 정복 문제라고 볼 수 있다. Code #include using namespace std; long long a, b, c; long long cal(long long a, long long b, long long c) { if (b == 0) { re..
(C++) - 백준(BOJ) 1991번 : 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 트리순회를 구현해보는 문제였습니다. 풀이방법 전위순회(preorder) : 루트 -> 왼쪽 자식 -> 오른쪽 자식 중위순회(inorder) : 왼쪽 자식 -> 루트 -> 오른쪽 자식 후위순회(postorder) : 왼쪽 자식 -> 오른쪽 자식 -> 루트 Code #include using namespace std; int n, a[26][2]; void preOrder(int x){ if(x..
(C++) - 백준(BOJ) 2711번 : 오타맨 고창영 https://www.acmicpc.net/problem/2711 2711번: 오타맨 고창영 첫째 줄에 테스트 케이스의 개수 T(1 T; for (int i = 0; i > index >> w; for (int i = 0; i < w.size(); i++) { if (i != index - 1) cout
(C++) - 백준(BOJ) 10170번 : NFC West vs North #include using namespace std; int main() { cout
(C++) - 백준(BOJ) 9325번 : 얼마? 답 문제링크 : https://www.acmicpc.net/problem/9325 단순 입출력 문제였습니다. 1234567891011121314151617#include using namespace std;int main() { int T,s,n,q,p,sum = 0; cin >> T; for (int k = 0; k > s >> n; for (int i = 0; i > q >> p; sum += p*q; } cout
(C++) - 백준(BOJ)코딩 11399번 : ATM 답 www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 간단한 그리디 문제였습니다. 풀이방법 1. 오름차순 정렬 : 전체 대기시간이 한 대기시간으로부터 누적되어 더해지기 때문에 가장 시간이 적게 걸리는 사람이 먼저 은행업무를 봐야 합니다. 이를 위해 오름차순 정렬을 먼저합니다. 2. 전체 걸리는 시간을 계산해줍니다. Code #include #include using namespace std; int n; int arr[1000]; int main(){ cin >> n; for(int i = 0..
(C++) - 백준(BOJ) 1977번 : 완전제곱수 https://www.acmicpc.net/problem/1977 1977번: 완전제곱수 M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완 www.acmicpc.net 그대로 구현하는 문제였습니다. 📕 Code #include using namespace std; int main() { int small = 10001, M,N, sum = 0, cnt=0; cin >> M >> N; for (int j = 1; j = M&&j*j = M&&j*j j*j) { small = j*j; } } if (cnt == 0) { cout

티스토리툴바