코딩 테스트 준비 문제 [약수 문제] _ Python3

1. 문제와 문제 조건 파악하기

계산 관련 문제는 배열, 사칙 연산, 데이터 타입에 대한 이해를 기본으로 합니다. 먼저, 두 정수 타입의 변수를 넣었을 때 약수를 반환하는 문제를 풀어봅시다.

 

문제:

두 정수를 매개변수로 입력하고, 각각의 정수에 포함된 약수를 나열 작은 수부터 차례대로 정리하라. 정리된 약수는 배열 형태로 반환하는 함수를 만들어라.  

 

조건:

- 두 정수는 1000 이하의 수이다. 

- 반환된 배열은 리스트 타입으로 만들 것.

- 음수는 약수로 취급하지 않는다.

2. 약수 알고리즘 _ 유용한 함수 정리

약수는 정수로 나누어 떨어지는 어떤 수를 말합니다. 이 어떤 수는 정수에 따라 2개 이상의 약수를 갖기도 합니다. 다시 말해서, 모든 수는 1과 자기 자신을 기본 약수로 합니다. 물론 1은 약수가 1뿐 입니다. 그렇다면, 가장 쉽게 약수를 구하는 알고리즘은 어떻게 될까요?

 

바로 어떤 수 n을 1 씩 줄여가며 나눈 결과를 확인하는 방법입니다. 이 방법은 가장 단순하기도 하고 다른 방법은 시간을 줄여줄 수는 있으나, 새로 배워야 할 정보가 많아 언급하지는 않겠습니다.

 

* 위 방법에서 굳이 시간을 단축시켜 보자면 1과 자기 자신을 제외하면 됩니다. 그러면 시간 복잡도는 O(n-2)이죠. 

 

약수 알고리즘을 알았으니 이번에는 배열과 관련된 유용 함수를 알아봅시다. 배열에서 원소를 차례대로 추가하는 코드는 다음과 같습니다.

 

코드 1 _  배열 이름.append(n)

; 배열 이름에 해당하는 배열의 끝 부분에 새로운 변수 n을 삽입합니다.

결과적으로 배열 총사이즈가 증가합니다.

 

코드 2 _  del 배열 이름[n]

; 배열 이름에 해당하는 배열의 n번째 인덱스를 삭제합니다. 결과적으로 배열 총사이즈가 감소합니다.

 

* 이 문제에서는 코드 1이 사용하기에 적합해 보이네요.

 

이 문제에서 사용하지는 않았지만, 추후 자료구조에서 중요한 pop 코드를 다음과 같이 기록하겠습니다.

코드 3 _  배열 이름. pop(n)

; 배열 이름에 해당하는 배열의 n번째 인덱스를 삭제합니다. 결과적으로 배열 총사이즈가 감소합니다. 만약 인덱스 n이 없다면, 가장 큰 인덱스 값에 해당하는 원소를 삭제합니다.

3. 문제 풀어보기

문제를 해결하기 위해 제시한 예시 코드는 다음과 같습니다.

 

예시 코드:

def convert(T1,T2):
    Ans1, Ans2 = [], []
    if T1 <= 1000 and T2 <= 1000:
        for i in range(T1):
            if T1%(i+1) ==0:
                Ans1.append(i+1)
        for i in range(T2):
            if T2%(i+1) ==0:
                Ans2.append(i+1)
    return Ans1,Ans2

 

코드 결과:

약수 구하기 코드 결과