[알고리즘] 약수 구하기

약수구하기

약 5개월전까지만 해도 알고리즘에 대해서 꾸준히 공부를 진행해왔었다.
하지만 다른회사로 이직을 하게되면서, 업무에 적응과 회사분위기에 적응이 필요하기때문에 어느정도 공부는해왔지만, 글을 작성해오지는 않았습니다..

그래서 이것은 알아둘 필요가 있겠다 싶어 작성합니다.

---

약수구하기
아주 간단하게 생각하면 아래와 같은 로직이 구성된다.

int n = 100;

for(int i = 1; i <= n; i++){
	if(n % i == 0){
    	System.out.println(i + "는 약수 입니다.");
    }
}

단순하게 1부터 n까지 반복하면서 index가 나누어지면 약수로 취급한다.
하지만 알고리즘을 조금 알고있다면 시간복잡도에 관해 생각이 들것이다.

기본적으로 for문은 시간복잡도가 O(n)이기 때문에 조금 비효율적일수 있다.

---

그렇다면 어떻게 해?

제곱근을 통해서 시간을 단축시키고 효율성을 증대시켜보자..

int n = 100; // 입력 값
int sqrt = (int) Math.sqrt(n); // 100의 제곱근은 10
ArrayList<Integer> arr = new ArrayList<>(); // 약수 받을 ArrayList

for(int i = 1; i <= sqrt; i++){
    if(n % i == 0){ // 약수 중 작은 수 저장
        arr.add(i);
        if(n / i != i){ // 약수 중 큰 수 저장
            arr.add(n / i);
        }
    }
}

간단하게 위를 살펴보면

• 100의 제곱근을 구한다 . = 10
• 여기서 우리가 알수 있는것은, 10을 i 로 나누어서 떨어진다면, i와 몫은 모두 10의 약수로 판단할수가있다.
• 그렇기에, 위와 같이 두번의 플래그를 통해 가져온다.

---

실행결과는 보여주기 어렵지만, 프로그래머스 알고리즘 레벨1 문제를 풀다가
알아두면 매우 좋을것같다는 생각이 들어 간단하게 작성해봅니다.

혹시 잘못된정보가 있다면, 수정하겠습니다. 😊