JAVA_코딩테스트 준비_순열/조합

알고리즘에서 수학이란?

우리가 중,고등학교때 배운 수학공식, 법칙 등을 알고리즘에 적용하는 것이다. 

이런 문제를 이제 프로그램으로 푸는거다, 물론 위의 문제의 정답은 0 이 맞다

예를들어서 좌표 상의 두 점 사이의 거리를 구할때 피타고라스 정리를 사용한다던가, 두 수의 최대공약수를 빠르게 찾아내는 방법이라던가(유클리드 호재법)

사실, 코테같은거를 준비하다보면 뭐 어떤 조건에서 소수를 구해라, 약수를 구해라 라고 한다. 

그런데 이게 그냥 단순히 나눠서 안나눠떨어지게 코딩하면 시간초과 개판난다. 

"수학 법칙을 사용해서 연산 시간을 줄여야 한다." 이말이다.

 

순열과 조합

학창시절에 경우의수 뭐시기 하면서 뭘 뽑네 카드를 뽑네 몇장 뽑았네 순서를 상관하네 마네 한 기억이 있을것이다. 

나는 이게 맨날 헷갈려서 경우의 수 적으면 그냥 손으로 그리거나 머릿속으로 계산해서 풀었는데, 이게 이제 프로그래밍하는데 겨나온거다. 

다행히, 우리는 식만 짜고, 계산은 콤퓨터가 해준댄다.(식 세우는게 더 힘들다.)

일단 순열과 조합 말하기 전에 간단히 기억할 것은 두가지다.

• 순열 : n개 중에 m개 뽑아서 순서에 상관이 "있는" 경우의 수
  (A, B ,C 중에 2장 뽑는다 치면, B, C순서랑 C, B순서로 뽑은 경우가 "다르다고" 봄)
  
  
• 조합: n개 중에 m개 뽑아서 순서에 상관이 "없는" 경우의 수 
  (A, B ,C 중에 2장 뽑는다 치면, B, C순서랑 C, B순서로 뽑은 경우가 "같다고" 봄)

A, B, C ,D, E 5장의 카드를 예로 들겠다. 

 

순열

우리가 5장중에 3장 뽑는 경우의 수를 구할때는 

처음 뽑을 수 있는 5가지 -> 5

하나 뽑아서 남은 4가지 -> 4

또 하나 뽑아서 남은 3가지 -> 3 

-> 총 경우의 수 5 * 4 * 3 -> 60가지 

여기서 A, B, C ,D, E 중 A, B, C 를 뽑게 되었을 때 B, C, A / B, A, C 다 다르게 취급한다는 것이다.

순열 예시 (출처 : 코드스테이츠)

이걸 우리는 학창시절에 공식화 해서 배웟다.

• 5장에서 3장 선택하는 순열의 수 -> 5P3-> (5 x 4 x 3 x 2 x 1 ) /(2 x 1) = 60
  
  
• 일반식 nPr = n! / (n-r)!

코드 예시 

public static ArrayList<String[]> permutationLoop() {
  
  
    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 = 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;
}

뽑는 횟수만큼 for문을 돌려주는거로 해결 가능하다. 

여기서, i = j , k = j , k = i  인 경우 같은 카드가 두장 뽑히는 경우가 되므로, 똑같은 경우는 제외시켜준다. 

이거를 출력하면 

[
  [ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ], [ 'A', 'B', 'E' ],
  [ 'A', 'C', 'B' ], [ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ],
  [ 'A', 'D', 'B' ], [ 'A', 'D', 'C' ], [ 'A', 'D', 'E' ],
  [ 'A', 'E', 'B' ], [ 'A', 'E', 'C' ], [ 'A', 'E', 'D' ],
  [ 'B', 'A', 'C' ], [ 'B', 'A', 'D' ], [ 'B', 'A', 'E' ],
  [ 'B', 'C', 'A' ], [ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ],
  [ 'B', 'D', 'A' ], [ 'B', 'D', 'C' ], [ 'B', 'D', 'E' ],
  [ 'B', 'E', 'A' ], [ 'B', 'E', 'C' ], [ 'B', 'E', 'D' ],
  [ 'C', 'A', 'B' ], [ 'C', 'A', 'D' ], [ 'C', 'A', 'E' ],
  [ 'C', 'B', 'A' ], [ 'C', 'B', 'D' ], [ 'C', 'B', 'E' ],
  [ 'C', 'D', 'A' ], [ 'C', 'D', 'B' ], [ 'C', 'D', 'E' ],
  [ 'C', 'E', 'A' ], [ 'C', 'E', 'B' ], [ 'C', 'E', 'D' ],
  [ 'D', 'A', 'B' ], [ 'D', 'A', 'C' ], [ 'D', 'A', 'E' ],
  [ 'D', 'B', 'A' ], [ 'D', 'B', 'C' ], [ 'D', 'B', 'E' ],
  [ 'D', 'C', 'A' ], [ 'D', 'C', 'B' ], [ 'D', 'C', 'E' ],
  [ 'D', 'E', 'A' ], [ 'D', 'E', 'B' ], [ 'D', 'E', 'C' ],
  [ 'E', 'A', 'B' ], [ 'E', 'A', 'C' ], [ 'E', 'A', 'D' ],
  [ 'E', 'B', 'A' ], [ 'E', 'B', 'C' ], [ 'E', 'B', 'D' ],
  [ 'E', 'C', 'A' ], [ 'E', 'C', 'B' ], [ 'E', 'C', 'D' ],
  [ 'E', 'D', 'A' ], [ 'E', 'D', 'B' ], [ 'E', 'D', 'C' ]
]

이렇게, 3장 뽑아서 만들 수 있는 경우의 수 완성이다. 

 

조합

앞서 말한것 처럼, 조합에서는 순서에 상관없이 다 같은거로 본다. 

A, B, C / B, C, A / B, A, C 다 같은 놈으로 본다는 것이다. 

그러면 3 장의 카드를 뽑는 경우의 수가 모두 중복 되는 경우가 있다는 것이다. 

조합 예시 (출처 : 코드스테이츠)

고로, 3장에서 3장을 뽑는 경우의 수 

처음 뽑을 수 있는 3가지 -> 3

하나 뽑아서 남은 2가지 -> 2

또 하나 뽑아서 남은 1가지 -> 1

-> 3* 2 * 1 -> 총 6가지 

고로, 앞에서 구한"순열"에서 중복되는 부분을 빼주면 

 (5 x 4 x 3 x 2 x 1 ) / ( 2 x 1) * ( 3 x 2 x 1 ) =10가지

(5 x 4 x 3 x 2 x 1 ) / ( 2 x 1)부분은 앞에서 구한 순열 

( 3 x 2 x 1 ) 부분은 중복된 부분이다.

이를 식으로 나타내면 

• 5장에서 3장을 무작위로 뽑는 경우 ->  5C3 = 5! (3! * 2!) = 10
  
  
• 일반식 nCr = n! / (r! *(n - r)!)      

코드 예시 

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;
}

위의 순열과 마찬가지로 뽑는 횟수 만큼 for문을 겹겹이 만들어 놧다.

다른점은 for문의 시작 부분은 이전 for문 안의 값 +1 로 중복값을 방지한다는 것이다. 
( i = 0 / j = i + 1 / k = j  + 1 )

한번 만든 3장의 카드 조합은 다시 만들지 않기 때문에, 하나의 요소로 만들 수 있는 모든 경우의수를 다 구한 후, 그 요소만 포함하지 않고 반복문을 실행하는 것이다. 

이걸 출력하면

/*
[
  [ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ], [ 'A', 'B', 'E' ],
  [ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ], [ 'A', 'D', 'E' ],
  [ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ], [ 'B', 'D', 'E' ],
	[ 'C', 'D', 'E' ]
]
*/

이렇게, 조합 출력이 나온다. 

추가적인 사실 : 여러겹의 for문 .... 시간복잡도에서 O(n^2)를 갖는 녀석이다! 라고 파악하면 참 좋은 학생이다

위의 for문으로 순열, 조합을 만들어 낼 수 있는데, 사실 지금까지는 희망편이다.

희망편인데, 파멸편은 왜 넣었냐고? 그게 현실이라서다

위에서 "3장"을 뽑는다고 명시해서 for문이 3개라고 계속 말했다. 

3장 뽑아서 for문이 3개....

4장은 4개....

카드 40장 중에 도둑잡기 한다고 4명이서 10장씩 나눠갖게 한다고 하면 for문이 10개가 되는 것이다. 

그런데, 또 한명 더 추가되서 인당 8장으로 뽑아야 하는 장수가 바뀌게 된다면 어찌할텐가?

위의 for문을 늘리는 방식으로는 한계가 있다. 변칙적인 수에 맞춰 작동 하기 힘들고, 조건에 따라 많은 수를 다뤄야 한다고 하면 아주 작살난다. 

그런데, 이 함수, for문, 변수..... 모두 복사해서 또 반복하는놈이 있지 않은가?

바로 재귀함수다.

재귀함수를 사용해서 순열과 조합을 풀 수 있는데, 이게 생각보가 엄청 골때린다.

이거 코드를 일일히 예를 들어서 설명하고 싶어도 내가 자세히 파악하는게 힘들었다..
(오늘 코드 문제도 잘 못풀었다.)

이건 연습으로...커버해야한다...

핵심은..

이런 수학적 요소가 있는 알고리즘을 풀때는 그에 맞는 적절한 수학법칙을 코드로 구현하고, 우리가 그에 맞는 자바 문법을 활용 해야 한다는 것이다. 

앞서 순서를 생각하냐 마냐로 순열과 조합이 갈리는 것 처럼, 만약 숫자라면 공약수를 구하거나, 소수를 구해야 하는 것 처럼 

적절한 식을 적절히 작성해야 한다. 

코딩테스트 관련 챕터는 여기서 끝이라고 한다.

아니 세상에, 이거로 코테 대응이 된다고? 

그럴리가 없다 

코드스테이츠에서 계속 말하는 것은 일단 "우리는 던져줄테니 너가 알아서 잘 공부해야됨 ㅎㅎ" 이기 때문에 스스로 공부해야 한다. 

일단 코딩테스트를 준비하기 위해 대표 유형을 공부하고, 연습해야겠다.