LeeJellan
[TIL] Java Algorithm 3
코드스테이츠 백엔드 부트캠프 D+41
드디어!! 알고리즘 섹션이 끝났다.
길고 길었다… 9월 20일 부터 9일간 코딩테스트를 준비하는 방법과
여러 알고리즘의 형태들을 공부했다.
너무 어려운 내용이 한꺼번에 많이 머리에 입력되서 과부하가 온 상태였다.
사실 알고리즘 문제 푸는 것에 대한 성취감도 있고
재미를 느끼는 편이긴한데, 단기간에 여러가지 내용을 배우다보니
커다란 벽에 막힌 느낌이었다. 하나하나 해결하면서
겨우 마지막 알고리즘 풀이 시간까지 왔다.
웹 서비스 지식을 배운후 추후에 알고리즘 공부를 다시해보자!!
오늘은 수열과 조합에 대한
알고리즘 공부를 했다.
비교적으로 탐욕 알고리즘이나, DP같은 알고리즘보다는
조금 이해하기가 더 편했던 것 같다.
for문과 재귀함수를 이용해 중복수열, 조합 등
기초적인 문제들을 프로그래밍을 해보았고 정리해보려한다.
순열(Permutation)
순열, 요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수
예를 들어 5장의 카드 A, B, C, D, E 중 순서를 생각하며 3장의 카드를 뽑아서
나열해보면 5 x 4 x 3 x 2 x 1 / 2 x 1 = 60 이렇게 경우의 수가 60개가 뽑히게 된다.
즉, 5 x 4 x 3 의 값이다.
nPr 이라고 표시도 한다. 여기서 n=5 , r=3 이된다. 즉, ₅P₃
전체요소의 값에서 나열해야하는 수만큼 팩토리얼로 곱해주면된다
5장 중 3장 나열 = 5 x 4 x 3
7장중 2장 나열 = 7 x 6
6장중 5장 나열 = 6 x 5 x 4 x 3 x 2
간단하게 다시 정리하면
수열이란 A,B,C 와 A,C,B를 다른 경우로 판단하며
순서를 중요하게 생각하여 나열하는 방법이다.
만약 [A,B,C,D,E] 배열 5장중
3장을 나열할때 [A,B,C] / [C,B,A] 와 같이 중복된 단어의
배열이 존재하는 경우까지 포함한다는 뜻이다.
이것과 반대되는 개념은 아래에 조합에서 다뤄보고
코드로 예제를 확인해보자
수열 문제
public static void main(String[] args) {
N06_Permutation exmple = new N06_Permutation();
System.out.println(exmple.newChickenRecipe(new int[]{10010,10,110,111100,101010},3));
}
public ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
// 1. 예외상황
// choiceNum숫자가 배열값보다 클경우 null로 반환
// 주어진 재료가 모두 사용하지 못할 경우 null로 반환
if (choiceNum > stuffArr.length) return null;
// 2. 모든 경우의 수를 찾는 문제.
// stuffArr에서 choiceNum 개수 만큼의 경우의 수를 찾는문제 즉, stuffArr P choiceNum의 수만큼 찾기
// int 배열을 String 배열로 변경한다.
String[] strArray = Arrays.stream(stuffArr).mapToObj(String::valueOf).toArray(String[]::new);
System.out.println(Arrays.deepToString(strArray));
ArrayList<Integer> overlapCheck = new ArrayList<>();
// 0이 3개 이상은 레시피는 배열에서 제외한다.
for (String s : strArray) {
String[] str = s.split("");
int zeroCount = (int) Arrays.stream(str).filter(i -> i.equals("0")).count();
if (zeroCount < 3) overlapCheck.add(Integer.parseInt(s));
}
// 객체를 정렬합니다.
Collections.sort(overlapCheck);
// 리스트로 담은 재료들을 배열로 변환
int[] ingredient = overlapCheck.stream().mapToInt(i->i).toArray();
int[] check = new int[ingredient.length];
// abnormal) 사용할 수 있는 재료가 choice보다 작다면 null 반환
if(choiceNum>ingredient.length) return null;
// abnormal) 주어진 재료 모두 사용할 수 없다면 null 반환
if(ingredient.length==0) return null;
// 2. 순열의 길이가 달라지기 때문에 재귀함수로 문제를 푼다
return repeat(choiceNum, new ArrayList<>(), new Integer[]{}, ingredient, check);
}
public ArrayList<Integer[]> repeat(int choiceNum, ArrayList<Integer[]> arrayList, Integer[] arr, int[] ingredient, int[] check){
// choiceNum만큼 진행후 탈출조건
if(choiceNum==0){
arrayList.add(arr);
System.out.println(Arrays.toString(arr));
return arrayList;
}
// 재료를 순회하여 재귀하여 합쳐 경우의 수를 구하기
for(int i=0; i<ingredient.length; i++){
if(check[i]==0){
check[i] = 1; // {1,0,0} ->
Integer[] copyArr = Arrays.copyOf(arr,arr.length+1);
copyArr[arr.length] = ingredient[i];
arrayList = repeat(choiceNum-1, arrayList, copyArr ,ingredient, check);
check[i] = 0;
}
}
return arrayList;
}
위 문제는 1,0이 포함된 숫자형태의 요소들의 수열을 나열하는 문제다.
문제의 제약사항중 0이 3개이상 포함된 요소들은 제거해서
나열해야한다. 위의 예제로 {10010,10,110,111100,101010} 값이란 배열이 들어왔을때
10010, 101010을 제거한 후 {10,110,111100} 이란 숫자의 수열을 구하는 것이다.
여기서 우리가 알 수 있는 것은 3가지 경우의 수열을 구하는 것이고
재귀함수를 통해 수열을 풀이해볼 수 있다.
for문으로도 가능한데 위의 처럼 수열의 요소들이 달라지게될 경우
다른 값을 출력해야하기 때문에 재귀함수로 문제를 풀면 간단하게 풀 수 있다.
여기서 경우의 수를 먼저 구해보자면
₃P₃ 즉 (3 x 2 x 1)의 경우의 수를 구하면 되는 문제다.
[10, 110, 111100]
[10, 111100, 110]
[110, 10, 111100]
[110, 111100, 10]
[111100, 10, 110]
[111100, 110, 10]
수기로 나열해보아도
이렇게 6개로 유추해 볼 수 있다.
여기서 중요한점은 무엇인가? 중복된 값도 배열에 담기는 모습이다.
중복된 값이라는 의미는 10,110,11100이란 숫자들이 동일하게 담긴 배열들이 있는 것을 뜻한다.
여기서 이런 중복된 값들을 얘기해보면 전부다 중복된 값의 배열이다.
이런 중복된값을 제거하고 정렬하는 방법이 조합이다.
여기서 한가지 봐야할 점은 [10, 10, 10] 이러한 방법으로는
체크가 되지 않는 모습이다. 왜냐하면 int[] check라는 배열을 통해
이미 방문한 숫자를 체크해주고 있기 때문이다.
여기서 만약 체크해주는 조건문이 없을 경우에는
[10, 10, 10]
[10, 10, 110]
[10, 10, 111100]
[10, 110, 10]
[10, 110, 110]
[10, 110, 111100]
[10, 111100, 10]
[10, 111100, 110]
[10, 111100, 111100]
[110, 10, 10]
[110, 10, 110]
[110, 10, 111100]
[110, 110, 10]
[110, 110, 110]
[110, 110, 111100]
[110, 111100, 10]
[110, 111100, 110]
[110, 111100, 111100]
[111100, 10, 10]
[111100, 10, 110]
[111100, 10, 111100]
[111100, 110, 10]
[111100, 110, 110]
[111100, 110, 111100]
[111100, 111100, 10]
[111100, 111100, 110]
[111100, 111100, 111100]
3 x 3 x 3의 경우의 수인 27가지의 경우가 나오게된다.
위와 같은 경우는 한배열안에 같은 값의 중복을 허용하는 차이점이 있다.
조합(Combination)
조합은 위에서 계속 설명했듯이
순서를 생각하지 않고 선택할 때의 모든 경우의 수이다.
위의 예제와 같이 카드 5장 [A,B,C,D,E]가 있을 경우 3장을
순서를 생각하지 않고 나열한다고 가정하면
5 x 4 x 3 x 2 x 1 / (3 x 2 x 1) x (2 x 1) = 10
10가지의 경우의 수가 나오게 된다.
₅C₃ 이라고도 표시한다. 중복값을 제거한다고 생각하면 간단하다.
즉, [A,B,C]와 [C,B,A]를 동일한 경우로 취급하여
경우의 수로 체크하지 않는다는 뜻이다. 위에 수열에서는 이런 경우도
체크했는데 말이다.
그렇다는건 우리가 구하고자하는 값이
동일한 객체가 필요없는 경우의 수를 구할 때 조합이라는 나열법을
사용하여 알고리즘을 풀이하면 좋다는 것이다
오늘 풀어본 코드로 간단한 예제를 봐보자
public static void main(String[] args) {
N07_Combination example = new N07_Combination();
System.out.println(example.boringBlackjack(new int[]{2, 3, 4, 8, 13}));
}
public int boringBlackjack(int[] cards) {
ArrayList<Integer> arrayList = new ArrayList<>();
// 카드개수는 정해져 있지 않음
// 중복되는 값은 List에서 제외
// 여러장의 카드의 3장만 골랐을때의 경우의 수의 합을구해 배열로 변환.
for(int first=0; first<cards.length; first++){
for(int secound=first+1; secound<cards.length; secound++){
for(int third=secound+1; third<cards.length; third++){
int sum = cards[first] + cards[secound] + cards[third];
arrayList.add(sum);
}
}
}
// 배열 요소중 소수의 개수를 찾기
int primeCount = 0;
System.out.println(arrayList);
for(int i=0; i<arrayList.size(); i++){
int check = 0;
if(arrayList.get(i)==1) continue;
if(arrayList.get(i)==2) primeCount++;
if(arrayList.get(i)%2==0) continue;
for(int j=3; j<=Math.sqrt(arrayList.get(i)); j+=1){
if(arrayList.get(i)%j==0) {
check = 1;
System.out.println(arrayList.get(i));
break;
}
}
if(check==1) continue;
primeCount++;
}
return primeCount;
}
위의 문제는 배열에 나열된 카드 중에
순서를 생각하지 않고 3장을 골라 합을 구한뒤
구한 값에서 소수를 포함하는 수량을 반환하는 문제다. 위에서는 재귀로 풀지않고
For문으로 문제를 풀었다. 이유는 3장이라는 명확한 반복 수량이 정해졌기 때문이다.
여기서 중요한점은 순서를 생각하지 않고 3장을 고른다는 말이다.
이말은 즉, 중복된 값은 제거하고 3장을 고른다는 말이다.
예를들어 [1,2,3,4,5]의 카드가 있을 경우 [1,2,3]과 [3,2,1]은 순서를 생각하고
뽑은 것이기 때문에 위의 케이스중 하나만 존재해야한다는 것이다.
고로[1,2,3]을 포함한 경우의 수는 단 하나만 존재한다는 것이다.
위의 테스트 케이스에서 주어진 [2,3,4,8,13]이라는 5장중 3장을 고르는 것이니
조합의 식에 의해 ₅C₃ 즉, 10가지의 경우만 도출해내면된다는 이야기이다.
경우의 수를 수기로 계산해보자면
[2,3,4]
[2,3,8]
[2,3,13]
[2,4,8]
[2,4,13]
[2,8,13]
[3,4,8]
[3,4,13]
[3,8,13]
[4,8,13]
이렇게 10가지로 나누어 볼 수 있다.
즉, 중복되는 요소값이 없는셈이다! 이말은 순서를 생각하지 않고 골랐다!
라고 직역을 할 수 있다.
이렇게 수열과 조합에 대한 문제들을 오늘 풀어봤고
최대공약수와 같은 문제들도 훑어봤다.
문제의 난이도는 재귀가 들어가는 순간
머리가 어지러워진다~~ IDE 없이 프로그램을 어떻게 짜나 싶을 정도로
IDE를 사용하지 않으면 오류가 엄청 발생한다.
문법오류부터 오탈자까지…
나중에 코딩테스트할때는 IDE를 사용하지 않는 곳이 많다고하니
차근차근 문법도 정확히 쓰는법과 IDE에 의존하지 않고
코드를 작성하도록 연습 많이해야겠다.
오늘까지 알고리즘 공부 섹션을 끝냈고
이제 부터는 정말 본격적인 웹에 대해 공부하는 시간이 다가왔다.
기대되고 설렌다. Spring을 배우고 서버에 데이터도 담아보고
서비스가 어떻게 운용되는지 얼른 공부해보고싶다.
알고리즘 공부는 우선 잠깐 내려놓고
(물론 하루에 한문제 이상은 풀 예정!)
다음을 위해 집중해보려한다.
오늘 공부는 여기까지 끝!!
오늘의 커피량: ☕️ ☕️
오늘의 점심: 라면, 총무김밥