내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
숫자 블록
ps:problems:programmers:12923
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 숫자 블록 ====== ===== 풀이 ===== * 문제를 잘 이해한 뒤 다시 정리해보면. begin부터 end까지의 각 수에 대해서, 자기 자신을 제외하고 가장 큰 약수를 찾으라는 문제이다. * 정확히는 10,000,000 이하의 가장 큰 약수.. * 어떤 수 n의 가장 큰 약수를 구하려면, 2부터 sqrt(n)까지로 전부 나눠보면 된다. i가 n의 가장 작은 약수라면, 가장 큰 약수는 n/i 이다. sqrt(n)까지 중에 약수가 없다면, n은 소수이다. * 즉, n%i == 0 이고, n/i > 10,000,000 인 최소의 i를 찾으면 된다. * 2부터 시작해서 저 조건을 만족하는 i가 나올때까지 탐색하는 것보다, n/10,000,000부터 시작해서 탐색하는 것이 약간 더 효율적이긴 하지만, 루프의 전체 반복횟수에 비하면 미미한 차이라서 별 의미 없다 * 이 작업을 m개의 수에 대해서 수행해야 하므로 시간복잡도는 O(m*sqrt(n)) (m<=10,000, n<=1,000,000,000) * 사실, 10,000,000 이하라는 조건만 없다면, 훨씬 더 효율적으로 풀 수 있기는 하다. 2부터 sqrt(n)까지의 모든 수로 나누는 대신 그 범위 안의 모든 소수로 나눠보면 되기 떄문이다 * 에라토스테네스의 체를 이용해서 x이하의 소수를 모두 찾는데 걸리는 시간은 O(xloglogx)이다 * x이하의 소수의 개수는 O(logx) 이다. * 이 두가지를 적용해보면, 시간 복잡도는 O(sqrt(n)*loglog(sqrt(n)) + m*log(sqrt(n)) = O(sqrt(n)*loglogn + m*logn) 으로 훨씬 단축된다. * 그러나.. 10,000,000 이하라는 조건 때문에 이 방법은 불가능.. x가 조건이 없이 그냥 가장 큰 약수라면 n/x가 소수일테지만, x가 10,000,000 이하의 가장 큰 약수라면 n/x는 소수가 아닐 수도 있다. ===== 코드 ===== <dkpr py> """Solution code for "Programmers 12923. 숫자 블록". - Problem link: https://programmers.co.kr/learn/courses/30/lessons/12923 - Solution link: http://www.teferi.net/ps/problems/programmers/12923 """ import math def solution(begin, end): answer = [] for i in range(begin, end + 1): if i == 1: answer.append(0) continue for j in range(2, math.isqrt(i) + 1): if i % j == 0 and i // j <= 10_000_000: answer.append(i // j) break else: answer.append(1) return answer </dkpr> {{tag>프로그래머스 ps:problems:programmers:Level_4}}
ps/problems/programmers/12923.txt
· 마지막으로 수정됨: 2021/01/21 15:31 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로