🔥 들어가며
코딩테스트 준비를 위해 회사 동료와 약속을 했습니다. 얼마나 오래갈지는 모르겠지만, 프로그래머스 문제를 풀면서 단계별로 최소 주 X회 이상 코딩 문제를 풀기로...
단순히 문제를 풀면서 단순히 코딩 문제를 푸는 것만이 아닌 블로그에 사용한 알고리즘, 시간복잡도 등 문제 해결 과정 및 코딩테스트에서 많이 나오는 개념들을 정리해보고자 합니다.
💬 Divisor Problems
- 순서쌍의 개수: https://school.programmers.co.kr/learn/courses/30/lessons/120836
- 약수의 개수와 덧셈: https://school.programmers.co.kr/learn/courses/30/lessons/77884
문제 1. 순서 쌍의 개수
💡 문제 내용
순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ n ≤ 1,000,000
입출력 예시 및 설명
| n | result |
|---|---|
| 20 | 6 |
| 100 | 9 |
입출력 예 1)
n이 20 이므로 곱이 20인 순서쌍은 (1, 20), (2, 10), (4, 5), (5, 4), (10, 2), (20, 1) 이므로 6을 return합니다.
입출력 예 2)
n이 100 이므로 곱이 100인 순서쌍은 (1, 100), (2, 50), (4, 25), (5, 20), (10, 10), (20, 5), (25, 4), (50, 2), (100, 1) 이므로 9를 return합니다.
💡 문제 해석
이 문제는 입출력 예 1) 에서 보듯이 순서쌍이 튜플을 앞자리만 따서 변경하면 (1, 2, 4, 5, 10, 20)가 되고, 이는 가능한 약수의 개수를 묻는 것으로 해석할 수 있습니다.
🔍 약수란?
수론에서약수(約數, 영어: divisor) 또는인수(因數, 영어: factor, 전 용어: 승자(乘子))는 어떤 수를 나누어떨어지게 하는 수를 말한다.위키 백과 - 약수
💡 문제 해결 코드
시간복잡도 O(N)의 경우에는 코드는 매우 단순합니다. 정말 단순히 모든 원소를 검사해, 원래 숫자와 원소를 나누었을 때, 나누어 떨어지는지 보면 됩니다.
아래는 Python 코드입니다.
# 약수를 구하는 함수
def get_divisor(n: int) -> list:
return len([i for i in range(1, n+1) if n % i == 0])
# 약수의 개수를 반환
def solution(n):
return get_divisor(n)문제 2. 약수의 개수와 덧셈
💡 문제 내용
두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤
left≤right≤ 1,000
입출력 예시 및 설명
| left | right | result |
|---|---|---|
| 13 | 17 | 43 |
| 24 | 27 | 52 |
입출력 예 1)
- 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.
| 수 | 약수 | 약수의 개수 |
|---|---|---|
| 13 | 1, 13 | 2 |
| 14 | 1, 2, 7, 14 | 4 |
| 15 | 1, 3, 5, 15 | 4 |
| 16 | 1, 2, 4, 8, 16 | 5 |
| 17 | 1, 17 | 2 |
- 따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 합니다.
💡 문제 해결 코드
앞선 문제1과 문제2는 같은 내용의 문제지만, 해결해야될 문제의 수가 최대 999개까지 차이나기 때문에, 최대한 시간을 단축하기 위해 약수의 개수를 구하는 함수의 시간복잡도를 O(log N)으로 줄여보았습니다.
시간복잡도 O(log N)이란?
입력 데이터의 크기가 커질수록 처리 시간이 로그(log) 만큼 짧아지는 알고리즘
아래는 Python 결과 코드 입니다.
def get_divisor_count(n):
digits = [len(set([i, n//i])) for i in range(1, int(n**0.5)+1) if n %i == 0]
return sum(digits)
def transform(n: int):
if get_divisor_count(n) % 2 == 1: n *= -1
return n
def solution(left, right):
arr = [transform(i) for i in range(left, right+1)]
return sum(arr)원소 탐색을 최대 log2 N 값 만큼 탐색하도록 range 함수에서 max 범위를 int(n**0.5)+1 으로 지정했습니다. 그 이유는 log2 N 값을 넘는 숫자는 이미 앞서 나온 숫자의 몫으로, 이미 카운팅 되었기 때문입니다.
🔥 마치며
오늘은 코딩테스트 입문 과정을 풀며 워밍업 시간을 가졌습니다. 이번달 내로 0단계 문제를 모두 완성하는 것이 목표입니다!!
