코테 대비 2 - 약수구하기, Collection 최대값 구하기, 순열,백트래킹

약수 구하기

약수를 구하는 기본적인 방법

public List<Integer> getDivisors(int number) {
        ArrayList<Integer> list = new ArrayList<>();
        
        // 1부터 해당 숫자까지 반복한다.
        for (int i = 1; i <= number; i++) {
            if (number % i == 0) { // 1부터 해당 숫자까지를 하나씩 나눠봐서 나눠지면 약수
                list.add(i);
            }
        }
        return list;
}

 

기본적인 방법 말고 최적화된 방법을 써야한다.

import java.util.*;

public class Solution {
    public List<Integer> getDivisors(int n) {
        List<Integer> divisors = new ArrayList<>();
        
        // Math.sqrt(n)를 따로 변수에 저장해서 쓰던가 하지않으면 매번 계산해야해서 느리다. i * i가 속도도 빠름
        for(int i = 1; i * i <= n; i++) {
            if(n % i == 0) {
                divisors.add(i);
                if(i != n / i) {
                    divisors.add(n / i);
                }
            }
        }
        
        divisors.sort(Comparator.naturalOrder());  // 정렬 필요시
        return divisors;
    }
}

제곱근 == Square Root == sqrt

 

√n 최적화의 원리 , 핵심 아이디어:

약수는 항상 쌍(pair)으로 존재한다!

 

예를 들어 n = 36의 약수들:

1 × 36 = 36
2 × 18 = 36
3 × 12 = 36
4 × 9 = 36
6 × 6 = 36  ← 여기서 √36 = 6

 

보면 √36 = 6을 기준으로 대칭!!

 

왜 √n까지만 검사하면 될까?

for(int i = 1; i <= Math.sqrt(n); i++) {
    if(n % i == 0) {
        divisors.add(i);           // 작은 쪽 약수 (나눠졌으니까 나눈 수도 약수 )
        if(i != n / i) {           // 큰 쪽 약수도 추가 ( 나눠졌으니까 나눠진 몫도 약수 )
            divisors.add(n / i);
        }
    }
}
```

#### 1. i가 약수라면, n/i도 약수다
- 36 % 2 == 0 → 2는 약수
- 36 / 2 = 18 → 18도 약수!

#### 2. √n보다 큰 약수는 이미 찾았다
i = 1일 때: 1과 36을 동시에 찾음
i = 2일 때: 2와 18을 동시에 찾음
i = 3일 때: 3과 12를 동시에 찾음
i = 4일 때: 4와 9를 동시에 찾음
i = 6일 때: 6만 찾음 (6 = 36/6, 같으니까 한 번만)

더 이상 갈 필요 없음! 7부터는 36/7 = 5.x... 이미 찾은 약수들이에요.

### 시각적 설명:

n = 36의 경우

1  2  3  4  5  [6]  7  8  9  10 ... 36
↓              ↑              ↓
작은 약수들    √36           큰 약수들
(직접 찾음)                  (나눗셈으로 얻음)

√36 = 6을 넘어가면:
- i = 7일 때: 36/7 = 5.1... (약수 아님)
- i = 8일 때: 36/8 = 4.5 (약수 아님)
- i = 9일 때: 36/9 = 4 (4는 이미 i=4일 때 찾음!)

---

Collection 요소들중 최대 값 구하기

List, Set

Collections 유틸리티 사용한 방법

// List, Set
List<Integer> numbers = Arrays.asList(3, 1, 4, 1, 5, 9);
Integer max = Collections.max(numbers);  // 9

Set<Integer> set = new HashSet<>(numbers);
Integer maxSet = Collections.max(set);  // 9

// Comparator로 커스텀 비교
List<String> words = Arrays.asList("apple", "banana", "cat");
String longest = Collections.max(words, Comparator.comparing(String::length));

 

Stream API 사용한 방법

// 기본 타입
List<Integer> numbers = Arrays.asList(3, 1, 4, 1, 5, 9);
int maxValue = numbers.stream()
        .max(Comparator.naturalOrder())
        .orElse(0);
// 또는
int maxValue = numbers.stream()
        .mapToInt(Integer::intValue)
        .max()
        .orElse(0);  // 기본값

// 객체 비교
class Person {
    String name;
    int age;
    // constructor, getters...
}

List<Person> people = Arrays.asList(
        new Person("Alice", 25),
        new Person("Bob", 30)
);

// person중 가장 나이가 많은 person을 반환한다. 
Person person = people.stream() 
        .max(Comparator.comparing(Person::getAge))
        .orElse(null);

// 특정 필드만 추출
int maxAge = people.stream()
        .mapToInt(Person::getAge)
        .max()
        .orElse(0);

 

복잡한 비교

List<Product> products = Arrays.asList(
        new Product("A", 1000, 5),
        new Product("B", 1500, 3),
        new Product("C", 1200, 10)
);

// 가격 기준
Product mostExpensive = products.stream()
        .max(Comparator.comparing(Product::getPrice)) // int형 자료는 Integer로 변환되고 Integer는 Comparable를 구현해놨으니까 Comparator.naturalOrder()는 생략가능하다.
        .orElse(null);

// 여러 조건 조합
Product max = products.stream()
        .max(Comparator.comparing( p -> p.getPrice() * p.getStock()))
        .orElse(null);

// 다중 조건 (가격 우선, 같으면 재고)
Product max2 = products.stream()
        .max(Comparator.comparing(Product::getPrice)
                .thenComparing(Product::getStock))
        .orElse(null);

---

Map

Map<String, Integer> map = new HashMap<>();
map.put("a", 3);
map.put("b", 1);
map.put("c", 5);

// 방법 1: values()로 최댓값만
Integer maxValue = Collections.max(map.values());  // 5

// 방법 2: 최대값을 가진 Entry
Map.Entry<String, Integer> maxEntry = map.entrySet().stream()
        .max(Map.Entry.comparingByValue())
        .orElse(null);

Map.Entry<String, Integer> maxEntry = map.entrySet().stream()
        .max(Comparator.comparing(Map.Entry::getValue))
        .orElse(null);

System.out.println(maxEntry.getKey());  // "c"

// 방법 3: key 기준
String maxKey = Collections.max(map.keySet());

// 방법 4: Stream으로 value만
int maxVal = map.values().stream()
        .mapToInt(Integer::intValue)
        .max()
        .orElse(0);

 

---

순열 (Permutation)

n개 중에서 r개를 순서를 고려해서 뽑는 경우의 수

• 공식: nPr = n! / (n-r)!
• 예시: [1,2,3] 중 2개 뽑기 → 3P2 = 6가지

n개에서 r개를 뽑는거 까지는 조합과 같은데 ,순서가 다르면 다른경우로 보는것이 차이점이다.

두가지원소 1,2를 뽑아 [1,2]로 정렬하는 경우와

1,2를 똑같이 뽑고 [2,1]로 정렬하는 경우가 서로 다르다고 카운팅하는것이 순열이다.

 

시간복잡도는 n!이다 ( 선택리스트 갯수 n) 

public class prac {
    static int[] array = {1, 2, 3}; // 선택 대상 배열
    static int n = array.length; // 몇개중에서 뽑을 것인가
    static int r = 2; // 몇개 뽑을 것인가
    static int[] result = new int[r]; // 완성된 경우의 수를 저장할 배열
    static boolean[] visited = new boolean[n]; // 중복을 방지하기 위한 방문 배열

    public static void main(String[] args) {
        permutation(0);
    }

	// depth(= 현재 요소를 몇개 뽑았는가)
    public static void permutation(int depth) { // depth는 전역변수로 작성하면 재귀호출 앞뒤로 백트래킹을 해줘야해서 불편하므로 매개변수로 지정해주는게 좋다.

        // 원하는 갯수 만큼 다 뽑았다면 하고싶은거 진행한다. 원하는 갯수만큼 다 뽑고나서 depth를 증가시키고 재귀적으로 또 함수가 실행됬기에 depth == r 조건이 맞다.
        if (depth == r) {
            StringBuilder sb = new StringBuilder();
            sb.append("[ ");
            for (int number : result) {
                sb.append(number).append(",");
            }
            sb.deleteCharAt(sb.length() - 1);
            sb.append(" ]");
            System.out.println(sb);
            return; // 다 뽑았기에 더 진행하지않고,이 함수를 호출한곳으로 돌아가서 다른 경우의 수를 탐색한다. ( = 이전 호출 스택으로 돌아간다. )
        }

        for (int i = 0; i < n; i++) { // 선택 대상 배열 전체를 재귀적으로 살펴서 모든 경우의 수를 구한다.
            if (!visited[i]) {
                visited[i] = true; // 방문하지 않았던 요소라면 방문하고 방문처리 한다.
                result[depth] = array[i]; // 해당 요소를 뽑았기 때문에 결과 배열에 저장해준다.
                permutation(depth + 1); // 요소를 뽑았기 때문에 이제 다음 요소를 뽑기위해 스스로를 호출하는데 한개 뽑았기 때문에 depth를 증가시켜서 넘긴다.
                visited[i] = false; // 백트래킹 ( = 현재 요소를 뽑는 시도는 이미 위의 재귀 호출로 진행이 끝났고, 이제 다른 경우의 수를 만들기위해 선택했던걸 되돌린다. )
            }
        }
    }
    
}
        /*
        
         depth는 재귀의 깊이를 의미한다.
         하나를 선택할때마다 depth가 증가하는것은 그 다음 재귀로 들어가게 됨을 의미한다.
         그래서 depth와 r이 같으면 다 뽑은것이다. 

         depth 1  -> [ 1, 2, 3, 4, 5 ] 를 반복문을 돌면서 하나를 선택하거나 선택하지않거나
         depth 2  -> [ 1, 2, 3, 4, 5 ] 를 반복문을 돌면서 하나를 선택하거나 선택하지않거나
         
         */

 

백트래킹이란?

 

"변경한 상태를 명시적으로 원래대로 되돌리는 것"

(상태변경 → 탐색 → 상태복원) 이게 백트래킹!

 

일반순열에는 Visited 방문배열에 대한 백트래킹이 들어가 있다.

if (!visited[i]) {
    // 1️⃣ 상태 변경
    visited[i] = true;
    result[depth] = array[i];

    // 2️⃣ 다음 단계 탐색
    permutation(depth + 1);

    // 3️⃣ 상태 복원 ⭐ 백트래킹!
    visited[i] = false;
}

 

일반 순열에는 visited가 필요한 이유

왜 필요한가?

-> "같은 원소를 중복 선택하지 못하게 하려고"

 

왜 중복 선택 위험이 있나?

-> 순열은 순서가 중요하기 때문에 모든 순서를 고려하려면 매번 선택 대상 배열의 처음 인덱스부터 다시 살펴봐야 함

for (int i = 0; i < n; i++) {
    if(!visited[i]){
        visited[i] = true;
        result[depth] = array[i];
        permutation(depth+1);
        visited[i] = false;
    }
}

[1, 2, 3]에서 2개 뽑기, i가 반복문의 인덱스

첫 번째: 1 선택 (i=0)
  두 번째: i=0,1,2 전체를 봄
    i=0 → 1을 또 선택? ❌ visited로 막아야 함!
    i=1 → 2 선택 ✅
    
첫 번째: 2 선택 (i=1)
  두 번째: i=0,1,2 전체를 봄
    i=0 → 1 선택 ✅ [2,1] 만들려면 뒤돌아봐야 함!
    i=1 → 2를 또 선택? ❌ visited로 막아야 함!

 

순열은 순서가 중요하기때문에 모든 순서를 고려하기 위해서는
매번 재귀마다 선택 대상 배열의 첫번째 인덱스부터 다시 살펴보게끔 코드가 짜진다.
그래서 반복문이 돌다보면 이미 뽑힌 요소가 다시 뽑힐 위험이 있는데 그걸 Visitied 방문배열로 막는것이다.

 

일반순열, 중복순열, 일반조합, 중복조합 중 일반순열에만 Visited 방문배열이 필요하다.

중복순열은 중복이 가능하니까 중복방지용인 Vistied 배열이 필요없고

조합들은 반복문 시작인덱스인 StartIndex를 이용하여 중복이 애초에 발생하지않게끔 진행하기 때문이다.

 

visited를 백트래킹 하는 이유

왜 복원해야 하나?
-> "다른 경우의 수에서 그 요소를 다시 사용할 수 있게 하려고"

-> "복원하지 않으면 첫 번째로 선택한 요소를 기준으로한 경우의 수만 구할 수 있고,
나머지 요소들을 첫 번째로 선택하는 경우는 살펴볼 수 없기 때문 "

 

Visited를 이용해서 순서가 다른 모든 경우에 대해서 살펴보면서 중복된 요소를 뽑는걸 막을 수 있었다.

 

하지만 Visited를 백트래킹 하지않으면

첫번째 재귀스택에서 뽑힌 첫번째 요소를 기준으로 한 모든 경우의 수만 살펴볼 수 있다.

 

그 이유는

 

첫번째 재귀스택에서 뽑힌 첫번째 요소를 기준으로 모든 경우의 수를 살펴보면서 들린 요소들은

Visited에서 True로 되어있을거니까

첫번째 재귀스택에서 반복문 인덱스 i를 증가시켜서 다음 요소를 첫번째로 뽑은 모든 경우를 살펴보려고할때 

이미 모든 요소가 다 Visited에서 True로 방문처리 되어있어서

IF문을 통과하지 못해 코드가 실행되지 않아 경우의수를 살펴볼 수 없게된다.

 

예시) 선택 대상 배열이 {1,2,3} 이 있고 2개를 뽑는 순열인데 Visited의 백트래킹을 하지않는다면

permutation(0)
├─ i=0: 1 선택 → visited = [T, F, F]
│  │
│  └─ permutation(1)
│     ├─ i=1: 2 선택 → visited = [T, T, F]
│     │  └─ [1, 2] ✅
│     │
│     └─ i=2: 3 선택 → visited = [T, T, T] ← 모두 true!
│        └─ [1, 3] ✅
│
├─ i=1: 2 선택?
│  └─ ❌ visited[1] = true라서 통과 못 함!
│
└─ i=2: 3 선택?
   └─ ❌ visited[2] = true라서 통과 못 함!

결과: [1,2], [1,3]만 나옴

 

permutation(0)으로 첫번째 재귀가 시작되고 나서 permutation(1)이 동작하면서

첫번째 요소를 기준으로 한 모든 경우의 수를 뽑아냈다.

그리고 permutation(1)의 함수가 종료되면서 첫번째 재귀로 돌아온후

이제 다음 인덱스를 기준으로 살펴보려고할때

방문배열이 이미 다 True로 되어있기에 다음 경우의수를 살펴 볼 수 없게된다.

 

예시) 선택 대상 배열이 {1,2,3} 이 있고 2개를 뽑는 순열인데 Visited의 백트래킹을 한다면

permutation(0)
├─ i=0: 1 선택 → visited = [T, F, F]
│  │
│  └─ permutation(1)
│     ├─ i=1: 2 선택 → visited = [T, T, F]
│     │  └─ [1, 2] ✅
│     │  └─ visited[1] = false ⭐ → visited = [T, F, F]
│     │
│     └─ i=2: 3 선택 → visited = [T, F, T]
│        └─ [1, 3] ✅
│        └─ visited[2] = false ⭐ → visited = [T, F, F]
│  
│  └─ visited[0] = false ⭐ → visited = [F, F, F]
│
├─ i=1: 2 선택 → visited = [F, T, F]
│  │
│  └─ permutation(1)
│     ├─ i=0: 1 선택 ✅ → [2, 1] ✅
│     └─ i=2: 3 선택 ✅ → [2, 3] ✅
│
└─ i=2: 3 선택 → visited = [F, F, T]
   │
   └─ permutation(1)
      ├─ i=0: 1 선택 ✅ → [3, 1] ✅
      └─ i=1: 2 선택 ✅ → [3, 2] ✅

결과: [1,2], [1,3], [2,1], [2,3], [3,1], [3,2] 모두 나옴

 

 

result[depth]에 대해서는 백트래킹을 안해도 되나?

해당 요소를 뽑았다라는 코드로 

result[depth] = array[i];

 

이런식의 코드가 있는데

result의 역할은 경우의 수를 저장하는 역할이다.

반복문이 진행되면서 result[depth]의 값은 덮어씌워진다. 

그래서 따로 백트래킹 코드가 필요없는것이다.

자연스럽게 기존 상태가 지워지고 새로운 상태로 덮어씌워지기 때문에 백트래킹이 필요없다고 생각하면 된다.

 

순열이든 조합이든 모든 경우의수를 살펴보는 기본적인 원리는 반복문과 재귀 그리고 결과를 담는 배열이다.

 

예를들어 선택 대상 배열이 {1,2,3}이고 2개를 뽑아야한다고 했을때

첫번째에 어떤게 들어가야하나 하고 선택 대상배열에 대한 반복문이 돌면서 선택 결과를 배열에 담고

두번째에 어떤게 들어가야하나 하고 선택 대상배열에 대한 반복문이 돌면서 선택 결과를 배열에 담는다.

 

그게 재귀적으로 실행되는것이고 순열인지 조합인지 중복이 가능한지에 따라

반복문의 첫번째 인덱스가 무엇이 될지와 Visited 방문배열이 필요한지가 나눠지는것이다.

 

중복순열

public class prac {
    static int[] array = {1, 2, 3};
    static int n = array.length;
    static int r = 2;
    static int[] result = new int[r];

    public static void main(String[] args) {
        permutationWithDuplicates(0);
    }
    
    public static void permutationWithDuplicates(int depth) {
        if (depth == r) {
            System.out.println(Arrays.toString(result));
            return;
        }

        for (int i = 0; i < n; i++) {
            // 중복을 허용하니까 중복을 위한 방문배열과 방문 체크하는 로직도 없다.
            result[depth] = array[i];
            permutationWithDuplicates(depth + 1);
        }
    }

}

 

중복 순열에는 백트래킹이 필요없다.

 

그 이유는 다음과 같다.

 

1. 중복을 허용함으로 상태를 관리하던 Visted 배열이 필요없다. 그래서 되돌릴게 없다. 

 

2. result[depth]에 값을 넣은걸 되돌려야하지만 어차피 다음 루프에서 해당 값이 덮어써지니까 따로 코드를 작성할 필요가 없다.

그래서 상태를 되돌리는 백트래킹 관련 코드를 넣지않아도 된다.

 

중복순열 실행 흐름 

선택 대상 배열 : {1,2,3}
뽑는 갯수 : 2
i -> 반복문 인덱스
result -> 결과를 담는 배열
중복순열 동작 흐름

📞 permutationWithDuplicates(0) 호출
result = [?, ?]

  i=0
  result[0] = 1
  result = [1, ?]
  
    📞 permutationWithDuplicates(1) 호출
    
      i=0
      result[1] = 1
      result = [1, 1]
      
        📞 permutationWithDuplicates(2) 호출
        depth==r이니까 출력: [1, 1] ✅
        return
      
      // 복원 없음! result = [1, 1] 그대로
      
      i=1 ← 다음 루프 진행
      result[1] = 2  ← 자동으로 덮어씀!
      result = [1, 2]
      
        📞 permutationWithDuplicates(2) 호출
        출력: [1, 2] ✅
        return
      
      // 복원 없음! result = [1, 2] 그대로
      
      i=2 ← 다음 루프 진행
      result[1] = 3  ← 자동으로 덮어씀!
      result = [1, 3]
      
        📞 permutationWithDuplicates(2) 호출
        출력: [1, 3] ✅
        return
    
    return (depth=0으로 복귀)
  
  // 복원 없음! result = [1, 3] 그대로
  
  i=1 ← 다음 루프 진행
  result[0] = 2  ← 자동으로 덮어씀!
  result = [2, 3]  ← 1이 2로 바뀜!
  
    📞 permutationWithDuplicates(1) 호출
    
      i=0
      result[1] = 1  ← 자동으로 덮어씀!
      result = [2, 1]  ← 3이 1로 바뀜!
      
        📞 permutationWithDuplicates(2) 호출
        출력: [2, 1] ✅
        return
      
      i=1
      result[1] = 2
      result = [2, 2]
      
        📞 permutationWithDuplicates(2) 호출
        출력: [2, 2] ✅
        return
      
      ... (계속)

 

정리