47일차

Suhyeon Lee·2024년 12월 5일

목록 보기

47/80

CodeKata

SQL

150. Revising Aggregations - The Count Function

작성한 쿼리

SELECT
  COUNT(*)
FROM
  city
WHERE
  population > 100000
;

151. Revising Aggregations - The Sum Function

작성한 쿼리

SELECT
  SUM(population)
FROM
  city
WHERE
  district = 'California'
;

152. Revising Aggregations - Averages

작성한 쿼리

SELECT
  AVG(population)
FROM
  city
WHERE
  district = 'California'
;

Python

60. 기사단원의 무기

작성한 코드

def solution(number, limit, power):
    answer = 0
    weight = []
    for i in range(1, number+1):
        weapon = 0
        for j in range(1, int(i**(1/2))+1):
            if i%j == 0:
                weapon += 1
                if j**2 != i:
                    weapon += 1
            if weapon > limit:
                weapon = power
                break
        weight.append(weapon)
    answer = sum(weight)
    return answer

→ 문제 핵심은 약수 구하는 거라 여기를 참고하면 좋음

참고할 만한 풀이

def cf(n): # 공약수 출력
    a = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            a.append(n//i)
            a.append(i)
    return len(set(a))
def solution(number, limit, power):
    return sum([cf(i) if cf(i)<=limit else power for i in range(1,number+1)])

set 함수로 중복되는 값을 제거해서 제곱수를 해결

에라토스테네스의 체(1~N의 수가 소수인 지 판별하는 알고리즘) 응용으로 1부터 N까지의 수 i에 대한 약수들의 합을 구할 수 있다
- '1부터 어떠한 수의 배수들은 모두 소수가 아니다'라는 개념으로 접근하는데, 이를 이용해 해당 수의 약수들의 합을 구함

참고

divisors = [0] * (number + 1) for i in range(1, number + 1): for j in range(i, number + 1, i): divisors[j] += 1
위와 같이 '에라토스테네스의 체' 와 유사한 방식으로 배열을 만들어 해결하면 O(nlogn) 으로 굉장히 빠르게 해결할 수 있습니다.