본문 바로가기

Algorithm/최적화7

[백준] 14252번 공약수열 사용 언어 - Python3 문제 - 14252번 공약수열 14252번: 공약수열 서로 다른 양의 정수로 이루어진 크기가 N인 집합 A가 주어진다. 영선이는 집합에 새로운 양의 정수를 추가하려고 한다. 이때, 집합에 있는 수를 정렬한 결과에서 인접한 두 수의 공약수가 1을 넘 www.acmicpc.net 정답 최대공약수 GCD(A,B) (정답 맞춘 여부 X) arr 한개씩 확인하면서 두 값 사이에 gcd 최대공약수가 있다면, 몇개의 값이 필요한지 검사한다. a+1부터 b까지 for문 반복하면서, gcd(a,j) 또는 gcd(b,j) 최대공약수가 존재한다면, tmp += 1, count += 1 최대공약수 존재하지 않고 for문이 끝났다면, count += 2 import sys input = sys.st.. 2023. 10. 23.
[백준] 2436번 공약수 사용 언어 - Python3 문제 - 2436번 공약수 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 정답 최대공약수 GCD(A,B), 최소공배수 LCM(A,B) (정답 맞춘 여부 X) 최대공약수 GCD(A,B) 1. GAP을 줄이기 공약수 = 일정한 간격으로 JUMP해서 A와 B 모두에 도달할 수 있는 수 GCD(12,8) = 0부터 8까지, 8부터 12까지 JUMP가 가능한 수 = GCD(8,12-8) GCD(A,B) = GCD(B-A,A) = GCD(A-(B-A), B-A) 두 수이 최대공약수 = 간격.. 2023. 10. 23.
[백준] 1407번 2로 몇 번 나누어질까 사용 언어 - Python3 문제 - 1407번 2로 몇 번 나누어질까 1407번: 2로 몇 번 나누어질까 자연수 N이 주어지면, 자연수를 유지하면서 N을 2로 몇 번까지 나눌 수 있는지를 생각해 볼 수 있다. 즉, N의 모든 약수 중 2의 거듭제곱 꼴이면서 가장 큰 약수를 생각하는 것이다. 예를 들어 15의 www.acmicpc.net 정답 최적화 - 정수론(수학) (정답 맞춘 여부 X) 모든 숫자는 1로 나누어 떨어짐 -> F(A)는 기본 최소 A이다. 2의 거듭제곱으로 나눠주면서, 최소 몇개가 2의 거듭제곱으로 나눠지는지 확인한 후 그 값만큼 더해준다. A부터 B 구간 = B-A+1 = B-(A-1) => A에 1을 빼주고 tmp_a와 tmp_b를 계산한 후, print(tmp_b - tmp_a) .. 2023. 9. 22.
[백준] 14232번 보석 도둑 사용 언어 - Python3 문제 - 14232번 보석 도둑 14232번: 보석 도둑 희대의 도둑 효빈이는 세계 최고의 보석가게 영선상에 잠입할 계획이다. 이 영선상은 최고의 보석가게답게 최고의 보안장치를 두고 있는데, 이 보안장치를 해제하지 않는다면 보석을 여러 개 www.acmicpc.net 정답 최적화 - 정수론(수학) (정답 맞춘 여부 O) n을 i로 나눴을 때 0이라면 = 약수라면, n = n/i로 업데이트 반복한다. answer 빈 리스트를 만들어줘서 약수들 저장! n이 1이 아니라면, 마지막 n의 값을 answer에 추가해준다. 예. n=15 => [3], n=15/3=5 => [3,5] n = int(input()) answer = [] for i in range(2, int(n**0.5).. 2023. 9. 22.
[백준] 11653번 소인수분해 사용 언어 - Python3 문제 - 11653번 소인수분해 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 정답 최적화 - 정수론(수학) (정답 맞춘 여부 O) n을 i로 나눴을 때 0이라면 = 약수라면, n = n/i로 업데이트 같은 i로 나눈 값이 0으로 나누어 떨어진다면 계속 i로 나눠줌 안 나누어 떨어질 때까지! 반복 n = int(input()) if n == 1: print('') else: for i in range(2, n+1): if n % i == 0: while n % i == 0: print(i) n = n / i 레퍼런스 정답 깃허브 https://github.com/yyeongeun/codingtest/.. 2023. 9. 21.
[백준] 1979번 소수 찾기 사용 언어 - Python3 문제 - 1979번 소수 찾기 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 정답 최적화 - 정수론(수학) (정답 맞춘 여부 O) int(num**0.5) + 1 약수 구할 때, 모든 값으로 나누지 말고, 루트한 값까지만 나눠주기 n = int(input()) nums = map(int, input().split()) answer = 0 for num in nums: cnt = 0 if num > 1: for i in range(2,int(num**0.5)+1): if num % i == 0: cnt += 1 # 소수 아닌 경우 if cnt == .. 2023. 9. 21.
[백준] 15736번 청기 백기 사용 언어 - Python3 문제 - 15736번 청기 백기 15736번: 청기 백기 예제 입력 1의 경우 1, 2, 3번 깃발이 존재하고, 3명의 선수가 참가한다. 첫 번째 선수는 1의 배수의 번호를 가진 깃발을 뒤집는다. 초기에 청색이였던 깃발은 첫 번째 선수에 의해 모두 백기로 된 www.acmicpc.net 정답 최적화 - 정수론(수학) (정답 맞춘 여부 X) 수학적 사고는 문제를 빠르게 획기적으로 풀 수 있도록 해준다! 1. 직접 그려서 특징을 찾아내기 2. 제곱근 구현 루트후 정수 변환 n = int(input()) answer = int(n**0.5) print(answer) 레퍼런스 정답 깃허브 https://github.com/yyeongeun/codingtest/blob/main/BAE.. 2023. 9. 21.

티스토리툴바