본문 바로가기
728x90

알고리즘316

[C++] 백준 17427 약수의 합 2 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 문제 해결 시간으로 보았을 때 $O(n)$의 시간복잡도를 가져야한다. 그러기 위해서는 각각의 약수의 합을 구해서 더하는 방식으로 할 수 없다.(최소 $O(n\sqrt{n})$) 1부터 n까지 반복문 $i$을 돌릴 때 n을 $i$로 나누면 n까지 숫자중 $i$를 약수로 갖는 개수가 나온다. 따라서 $i$를 곱해주면 $i$를 약수로 갖는 것들.. 2023. 10. 31.
[C++] 백준 2637 장난감 조립 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 문제 해결 위상정렬 문제라는 것을 쉽게 알 수 있다. 가장 마지막에 완제품 n이 오므로 n부터 시작해서 앞에 제품들을 조사한다. CODE #include #include #include #include using namespace std; vector adj[101]; int in[101], cnt[101]; int main() { int n; cin >> n; int .. 2023. 10. 24.
[python] 백준 2659 십자카드 문제 https://www.acmicpc.net/problem/2659 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 문제 해결 주어진 입력값을 가지고 시계수를 구하는 함수를 만든다. 그 방법은 맨 앞의 숫자를 맨 뒤로 옮겨가며 가장 최솟값이 나오는 수를 구하면 된다. 1111은 가장 작은 시계수인 것은 명백하다. x를 입력값을 십자모형의 카드에 넣어 얻은 시계수라고 하면 1111부터 x까지 시계수의 개수를 구하면 되는 문제이다. CODE import sys input = sys.stdin.readline def clock_num(n): .. 2023. 10. 18.
[C++] 백준 3059 등장하지 않는 문자의 합 https://www.acmicpc.net/problem/3059 3059번: 등장하지 않는 문자의 합 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성되어 있고, 문자열 S가 주어진다. S는 알파벳 www.acmicpc.net 문제 해결 문자의 ASCII 숫자를 활용해서 해결하는 간단한 문제 CODE #include #include using namespace std; int main() { int t; cin >> t; for (int T = 0; T > s; int answer = 0; for (int i = 0; i <.. 2023. 10. 15.
728x90