Algorithm with Math

◎ 순열(permutation)

• 요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수.

• m개가 정해져 있는 경우, m중 반복문을 이용하여 쉽게 구현할 수 있다.

    for (int i = 0; i < lookup.length; i++) {
      for (int j = 0; j < lookup.length; j++) {
        for (int k = 0; k < lookup.length; k++) {
          if (i == j || j == k || k == i) continue;
          // i, j, k에 대해 적당히 함
      }
    }

• m이 정해져 있지 않은 경우, 재귀를 이용해서 구현할 수 있다.

  // numList에 있는 숫자를 r개 나열하는 경우 구하기
    List<Integer> nPrlist(List<Integer> numList, int r){
        if (r == 1) return numList; // r == 1일떄, 그대로 내보냄
  
        List<Integer> ansList = new ArrayList<>(); // 새로운 리스트 선언&초기화
        for(int i=0; i< numList.size(); i++){
            // head tail 설정
            Integer head = newList.get(i); // 하나 선택
            // 나머지 케이스 만들기
            List<Integer> newList = copyList(numList); 
            newList.remove(i);
            List<Integer> tail = nPrlist(newList,r-1); // 뒤에꺼는 귀납을 통해 리스트로 가져옴
  
            // for문으로 하나씩 더해서 리스트에 넣음
            for (Integer tailElement : tail){
                ansList.add((int) (head*Math.pow(10,r-1) + tailElement));
            }
        }
        // 만든 리스트 리턴
        return ansList;
    }
  
    List<Integer> copyList(List<Integer> list){
        List<Integer> newList = new ArrayList<>();
        for(Integer num : list){
           newList.add(num);
        }
        return newList;
    }

◎ 조합(Combination)

• 순서에 상관없이 요소 n개 중에 m개를 뽑는 경우의 수.

• m개가 정해져 있는 경우, m중 반복문을 이용하여 쉽게 구현할 수 있다.

  int Len = cards.length;
  // j = i+1; k = j+1; 순서를 제한(앞에서 뽑은것의 다음 것을 뽑음)
  // i < Len - 2; j < Len - 1; 뒤에서 뽑을 것들을 적어도 이후 뽑을 갯수만큼 남겨놓음
  for(int i = 0; i < Len - 2; i++) {
      for(int j = i + 1 ; j < Len - 1; j++) {
          for(int k = j + 1; k < Len; k++) {
              // i, j, k 에 대해 적당히 사용
          }
      }
  }

• m개가 정해져 있지 않은 경우, 재귀를 통해 구현 가능

  // String 중에서 r개를 뽑는 모든 경우를 List<String>으로 줌
  public List<String> combinationCase(String str, int r){
        List<String> ans = new ArrayList<>(); // ans 초기화 & 선언
        
        // r == 1일때, 탈출조건
        if(r == 1){
           char[] chars = str.toCharArray();
           for (char letter : chars){
               ans.add(String.valueOf(letter));
           }
           return ans;
        }
  		
        char[] charArray = str.toCharArray(); // str을 CharArray로 만듦
  
        for(int i=0; i<=charArray.length-r; i++){
            char head = charArray[i]; // 앞에 뽑을 것 하나 선언
            // tail을 구할 때 사용할 chararray(String)을 만듦
            char[] remainder = Arrays.copyOfRange(charArray,i+1,charArray.length);
  
            // 뒤에 계산된 부분을 재귀를 통해 구함 
            List<String> tail = combinationCase(charToString(remainder), r-1);
            // tail 앞에 head를 붙임
            for(String element : tail){
                ans.add(head + element);
            }
        }
       return ans;
    }
    // charArray를 String으로 바꾸는 method
    private String charToString(char[] charArray){
        StringBuilder sb = new StringBuilder();
        for(char character : charArray){
            sb.append(character+"");
        }
        return sb.toString();
    }

◎ GCD (최대공약수)

• 최대공약수

  • 두 수의 공통된 약수중 최대인 약수
  • 최대공약수의 약수들은 두수의 모든 공약수와 필요충분조건이다.

• 유클리드 호재법 : 두 수의 최대공약수를 쉽게 구할 수 있게 해주는 공식

  • 큰 두수를 다룰 떄 참고하자
  • 참고 자료