공부중의 블로그

ex)소수 : [2,3]N = 4표현 가능한 수 : [1,2,3,4,6,8,9,12...]답 : 4 풀이 : 수열이 각 소수의 곱셈에 따라 반복적으로 구성된다. 즉, 1 2 3 4 6 8 ..이 포함되면2 4 6 8 12 16 ..3 6 9 12 18 24 ..이 각각 포함된다. 따라서 1을 처음에 놓고, 다음 후보군은2,3 중 하나다. 작은 2를 뺴고, 2의 다음 후보 4를 놓는다.계속 가장 작은 것 하나를 빼고 진행한다. 이렇게 N 개 세면 된다. 타임 컴플렉시티는 O(N * logK), K는 소수의 갯수이다. BST를 이용해서 최대값을 바로바로 조회하고 I/O를 해 주면 된다.

분수가 주어지는 경우, 소숫점 표현법으로 바꿔보자. 순환소수가 있는 경우 괄호를 출력한다.ex)1/3 = 0.(3)2/4 = 0.5(0)22/7 = 3.(142857) 솔루션: 분모를 소인수분해해서 2와 5로만 구성되 있으면 그냥 나눈걸 출력한다. 끝에 (0)을 붙인다.아니면 아래의 알고리즘을 쓴다. 정수로 나눈 값이 0이면 분자에 10을 곱한다. 정수로 나눈 값이 다음 자릿수다.0이 아니면 그걸 그냥 그대로 붙이고 넘어간다. 지금까지 나온 소숫점 아래 숫자가 다시 나왔으면 순환은 거기까지다. 근데 이 경우에 순환소수가 바로 시작하지 않는 경우와 순환소수 내의 숫자가 반복되는 경우 패턴 매칭이 상당히 어렵다. 다른 시도로는 순환소수 분수 형태로 주어진 분수를 고치는 방법이다.. 근데 경우의 수가 상당히 ..

처음에는 3또는 5만 소인수로 갖는 것들의 합 구하기로 생각해서, 3의 거듭제곱 중 가장 작으면서 큰거 i, 5의 거듭제곱 중 가장 작으면서 큰거 j 라고 하면 (i,j) 2중 for 루프의 모든 숫자들 중 N 보다 작은 것들을 전부 더해나갈 생각이었다. 갯수는 log^2N 이고 각각에 대해 합을 구하는건 단계별로 3씩 곱해나가는 셈이니까 1이 걸려서 총 시간 복잡도는 O(log^2N) 쯤 되겠다. --- 근데 이 문제는 "3 또는 5의 배수" 이기 때문에.. 10 이면 3 6 9 = 185 = 5tot : 23 매우 자명하게 3 total = N/3 * (N/3*(N/3+1)/2)5 total = same but 5그리고 이 둘의 합을 하면 중간에 15의 배수가 겹치므로15 total = same bu..