코드스테이츠 BE 28일차 - 자료구조 / 알고리즘 순열, 조합

GCD/LCM(최대공약수, 최소공배수), 순열/조합, 멱집합

​

순열 : 요소 n개 중에 m개를 순서 고려하여 뽑는 경우의 수. nPr = n! / (n-r)!

조합 : 요소 n개 중에 m개를 순서 고려하지 않고 뽑는 경우의 수 nCr = n! / (r! * (n-r)!)

! (팩토리얼)

​

[순열]

반복문 개수 == 요소를 뽑는 개수

반복문 for문 사용

// 순열의 모든 경우의 수 나열
// 순열 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
// 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
String[] lookup = new String[]{"A", "B", "C", "D", "E"};
ArrayList<String[]> result = new ArrayList<>();

for (int i = 0; i < lookup.length; i++) {          // lookup.length 순회
  for (int j = 0; j < lookup.length; j++) {
    for (int k = 0; k < lookup.length; k++) {
      if (i == j || j == k || k == i) continue;
        String[] input = new String[]{lookup[i], lookup[j], lookup[k]};
        result.add(input);
    }
  }
}

return result;
}
// 순열 5개 중 3개 뽑는 개수
for (int i = 0; i < lookup.length; i++) {
String pick1 = lookup[i];
for (int j = 0; j < lookup.length; j++) {
String pick2 = lookup[j];
for (letintk = 0; k < lookup.length; k++) {
String pick3 = lookup[k];

  if (i.equals(j) || j.equals(k) || k.equals(i)) continue;
  result.add(new String[]{pick1, pick2, pick3});

}
}
}
[조합]

​

// 모든 경우의 수

public static ArrayList<String[]> combinationLoop() {
// 조합 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
// 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
String[] lookup = new String[]{"A", "B", "C", "D", "E"};
ArrayList<String[]> result = new ArrayList<>();

for(int i = 0; i < lookup.length; i++) {
for(int j = i + 1; j < lookup.length; j++) {
for(int k = j + 1; k < lookup.length; k++) {
String[] input = new String[]{lookup[i], lookup[j], lookup[k]};
result.add(input);
}
}
}

return result;
}