For Programmer

이 문제는 간단히 10^12 까지 소인수 분해를 할 수 있냐를 묻는 문제이다. 그러나 O(N)으로는 못돈다. 따라서 최적화된 소인수 분해 코드를 짜야하는데 O(logN) 으로 구할 수 있는 소인수 분해 식이 있다. 예를들어 어떤 n의 소인수 분해는 a*b*c*d*e*f*g*h*i => n 다음과 같이 표현이 가능하다. 여기서 중요한 점은 a~i 까지의 수중에 sqrt(N)보다 큰 수는 많아봐야 1개(i) 이거나 없다.(제곱수 일때) 따라서 이러한 점을 이용해서 식을 짜면 된다. K = int(input()) # 소인수 분해 최적화(logN) def prime(k): x = k arr = [] for i in range(2, k): if i * i > k: break while x % i == 0: arr..

이 문제 코드 다 짜놓고 계속 틀리길래 엄한데 찾고 있었다.. 테케에서 입력횟수 제한을 안두면 알아서 try except로 EOFerror를 잡아줘야 한다. (참나... 이것때문에 엄한데서 오류를 찾고 2시간을 소비했다.... 죽어도 까먹지 말자.) 이 문제는 우선 K를 소인수 분해 해준다. 그렇다면 다음과 같이 소수 형태로 변한다.(2^3 * 3^5 * 7^2)... 그렇다면 이 소수들의 지수와 n!에서의 해당 소수의 지수 개수를 비교 해준다. 그 후 두개중 작은 개수를 최대공약수에 계속해서 곱해주면 된다. 예를들어) k의 소인수 분해 결과가 2^3 * 3^5 * 7^2 라고 하자. 하지만 n이 10이라서 10! 내에서는 2의 지수의 개수가 18개 3의 지수의 개수가 4개 7의 지수의개수가 1개이다. ..

이 문제 설명은 여기서 너무 잘되어 있어서 링크 남기겠다. 아무리 생각해도 못찾겠는데 약간 수학식으로 풀어야하는 문제였다. https://algosu.tistory.com/9 [C++] 백준 2436 - 공약수 https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공 algosu.tistory.com # 유클리드 호제법 사용 def uclid(a, b): while a % b != 0: a, b = b, a % b if b == 1: return True else: return False def solution(N, M): num..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWNcJ2sapZMDFAV8 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이 문제 너무 어렵게 생각해서 3시간을 넘게 생각했는데 풀리질 않았다. 힌트를 보니 정말 쉽게 접근할 수 있었다. 간단히 총 복도 길이 리스트 만들고 지나간 길을 +1씩 해주면 된다.. 그 후 가장 많이 지나간 복도(최대값) 출력하면 된다. (심지어 중간에 이 풀이 방식도 생각을 했으나 +1씩 한것이 과연 문제에 해결할 수 있을까? 라고 생각을 하고 지나쳤는데 그게 답이었다.. ) 조금 생각해야 할..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이 문제 이상하게 index 함수와 슬라이싱을 사용하면 10가지 출력이 모두 맞는데도 불구하고 런타임에러가 발생한다. 아마 숫자가 21억을 넘어가서 그런거 같다. (정확한 이유는 모르겠음..) 그래서 일반 for문으로 구성하니 정답이 출력되었다. 그리고 또한 반대로 탐색하며 마지막 인덱스를 최대값으로 설정하여 앞으로 탐색하면서 자신과 값의 차를 계속해서 더해준다. 그리고 만약 자신보다 높은 숫자가 ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWVl47b6DGMDFAXm SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이 문제 알면쉽고 모르면 생각을 꽤 하는 문제이다. 간단히 풀이방식은 '(' 을 만나면 현재 개수와 전체 개수를+1 씩 추가해주고 만약 레이저를 만나면 현재 저장된 개수를 그대로 전체개수에 한번더 추가해준다. 그리고 ')' 를 만날때 레이저가 아니라면 현재 개수를 -1 씩 해주는 식으로 문제를 풀었다. import sys sys.stdin = open('input.txt', 'r', encoding..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWYygN36Qn8DFAVm SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 간단한 구현문제이다. import sys sys.stdin = open('input.txt', 'r') T = int(input()) for order in range(1, T + 1): N, Q = map(int, input().split()) array = [0 for x in range(N + 1)] for i in range(1, Q + 1): # Q의 횟수만큼 L, R = map(int, ..

위 문제 문과생에겐 너무 어려운 문제이다.... 해설을 보니 nCm 은 n!/m!*(n-m)! 과 같다고 한다. 여기서 생각할 수 있는 점은 어떤수의 0의 개수는 10^k * n 이라고 할 수 있다. 예를 들어 0이 5개이면 10^5 * n 이라고 할 수 있다. 여기서 10은 다시 (2*5)^5 로 나눌 수 있는데 이는 즉, 2와5의 짝이 5개 있다는 말이다. 따라서 n!/m!*(n-m)! 식에서 n! 의 2와 5의 승수를 구하고 m!,(n-m)!의 승수를 구해서 빼주면 된다. 여기서 빼는 이유는 승수의 나눗셈 계산은 빼기이기 때문이다. 그리고 짝을 찾아서 짝의 개수만큼 출력해주면 된다. # 5의 승수 구하기 def five_power_n(N): count_5_1 = 0 X = 5 while X