서론
요즘 코딩테스트를 위해서 문제를 풀다보면, 수학적인 기초지식이 어쩔 수 없이 등장하게 된다.
대표적으로 조합과 순열에 관한것이 자주 등장하는데 해당 부분은 recursion 으로 쉽게 구현이 가능하다.
이런 지식이 필요하다 느낀 것은 뭐 배열에 등장하는 글자들 중 제일 많이 나오는 글자들의 조합을 구하라던가 의 내용의 문제일때, 해당 배경지식이 있다면 아 이거 그냥 조합으로 하고 문자열 Map 이용하면 끝나내!
라는 결론까지 도출이 가능하다. 사실 문제를 많이 풀어보란게, 이런걸 깨달으라고 그러는 거 같기도하다.
여튼 중요한 내용이라 반드시 정리를 하고 넘어가야 할 것 같아서 정리해보려고 한다.
조합
조합의 경우는 순서가 없는 것들의 집합이라고 할 수 있다. 뭐 만약의 과일의 집합이라고 하면, (바나나, 사과, 오렌지) 이런 조합은 순서가 없지 않은가? 이런것들이 조합이다.
우리가 조합을 구현하기 위해서는 어떻게 해야할까?
어떤 주어진 문자열에 대한 모든 조합을 구하는 recursion 을 만들어보자
우리가 해야 할것은 조합의 식에 맞춰서 nCr 을 구현하는 것이다.
즉 n 개의 원소들에서 r 개가 되는 조합(?) 의 최종 수를 구하는 것이다. 아 이게 글로 쓰려하니 뭐라해야 되는지 잘모르겠어서 아래 수식으로 설명하겠다.
그니까 3C2 일경우에는 "abc" 에서 두글자로 될 수 있는 조합을 모두 고르는 것이다.
EX) ab ac bc ca cb .. 등등이 될 수 있을 것이다.
그러면 우리가 어떻게 이걸 재귀로 풀어낼 수 있을까? 라는 생각을 먼져 해봐야 한다.
알고리즘에서 컴퓨터식 사고가 중요하기에 간단하게 기본 배경지식으로 생각했을때, 재귀가 가능한 이유는 Method 가 stack 자료구조로 관리되기 때문이다 라고 볼 수 있다.
만약 아래와 같은 코드가 있을때, 실행되는 순서는
public static int length(String str){
if(str.equals(""))
return 0;
return 1+length(str.substring(1));
}우리가 str 의 길이를 구하는 메소드 를 만든다면, 위와 같이 간단하게 재귀로서 만들 수 있을 것이다.
아래와 같은 콜스택을 유지하게 될 것이다.
1 + length(bc); --- 3
1 + length(c); --- 2
1 + length(""); --- 1
를 가지게 될것이다. 나가는 순서는 1,2,3 순서대로 나가게 된다.
즉 늦게 들어온 메소드가 먼져 나가게 되는 구조인데, 왜 이러한 구조를 가지게 되냐하면,
해당 3번 메소드는 2번 메소드의 결과가 필요하다. 2번 메소드는 1번 메소드의 결과가 필요하기에
연결에 연결을 이어 아래와 같은 결과를 지니게 되는 것이다.
여튼 우리의 조합도 이와 같다. 만약 abc 라는 문자열의 모든 조합을 우리가 찾아내야 한다면
2자리수 조합을 하는데 있어서는 한자리 수 조합이 필요하다.
즉 n 자리수 조합을 하는데 있어서는 n-1 자리수의 조합이 필요하게 된다.
그래서 우리가 이것을 recursion 으로서 설계가 가능하다는 것이다.
예를들어 우리가 String 을 전해주면 그 해당 문자들에 대한 주어진 수의 조합을 구하는 것이라고 해보자
예시는 String str = "abc" 일경우 abc 로 만들수 있는 하나의 문자들에 대한 조합을 구하는 것이라고 해보자.
그렇다면 우리는 3C1 이라는 것을 알 수 있다. 그런데 여기서 주어진 3은 어차피 str.length() 라고 볼수 있다.
그리고 우리는 각 글자를 한개씩 봐야하기에 char[] 배열로 변환하고 받을 것이다.
public class 조합 {
static ArrayList<String> stringCombination = new ArrayList<>();
public static void main(String[] args) {
nCr("abcd".toCharArray(), 1, "");
System.out.println(stringCombination.toString());
}
static void nCr(char[] str, int r, String result){
if(r == 0){
stringCombination.add(result);
return;
}else{
for(int i = 0; i < str.length; i++){
nCr(str, r-1, result+str[i]);
}
}
}
}위와 같이 짜줄 수 있을 것이다.
만약 저기서 2가지 조합을 구하고 싶다? 라고 하면
nCr("abcd".toCharArray(), 2, ""); 로 바꿔준뒤 실행하면 된다.
실행결과는 아래와 같다.
[aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd]
근데 처음에는 내가 수학적 머리가 좋지 않아서 그런지 이해가 가지않아서 난 콜스택을 이용해서 이해하려고 했다.
그니까 2로 들어갔을때, 1에 대한 결과값이 필요하므로 nCr("abcd".toCharArray(), 1, ""); 에 대한 결과과 먼져 이루어진다.
for(int i = 0; i < str.length; i++){
nCr(str, r-1, result+str[i]);
}상세하게 가면 처음에는 위에서 i = 0 에 대한 재귀호출이 이루어질 것이다.
nCr(str, 1, str[0]); 그래서 a 라는 값을 전달해주고, 아래 식을 진행한다.
nCr(str, 1, str[0])에서의 호출 구조를 보면 아래와 같다.
for(int i = 0; i < str.length; i++){
nCr(str, 0, "a"+str[i]);
}그래서 결국 보면 [aa, ab, ac, ad] 의 값을 전달해주고, r==0 일때 List 에 저장하는 방식으로 진행이 가능하다. 그래서 aa, ab, ac, ad 라는 값을 result에 저장할 수 있게 된다.
그래서 각 호출될때마다 오르는 count 라는 전역변수를 두고 측정해보면 아래와 같은 결과값을 보여준다.
count : 1 value :
count : 2 value : a
aa
ab
ac
ad
count : 7 value : b
ba
bb
bc
bd
count : 12 value : c
ca
cb
cc
cd
count : 17 value : d
da
db
dc
dd
[aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd]순열
순열의 경우는 아래와 같이 구현될 수 있다.
순열은 순서가 있어야 하기때문에 아래와 같이 구현할 수 있다.
public class 순열 {
static class Main {
public static void main(String[] args) {
List<String> arr = new ArrayList<>();
arr.add("a");
arr.add("b");
arr.add("c");
List<String> result = new ArrayList<>();
recursion(arr, result, arr.size(), 2);
}
private static void perm(List<String> arr, List<String> result, int n, int r) {
if (r == 0) {
System.out.println(result.toString());
return;
}
for (int i = 0; i < n; i++) {
result.add(arr.remove(i));
recursion(arr, result, n - 1, r - 1);
arr.add(i, result.remove(result.size() - 1));
}
}순열에 대한 설명은 따로 하지는 않겠다.
사실 알고리즘을 이해하려면 코드자체를 분석해서 이해하는게 좋다고 생각한다.
물론 머리 좋은 사람들은 보자마자 이해하는데, 난 잘 이해가 가지않아서 이 코드를 한 두세시간 동안 본거 같다. 멍청하면 노력으로 라도 극복해야 한다. 어렵다고 넘어가도 나중에 여기에 시간을 쓰게 되어있다.
여튼 잘 이해가 가지않는다면, 유튜브 강의든 여러가지 방법들을 통해 기본적인 구조를 이해한뒤, 이 코드를 그리면서라도 하나하나씩 뜯어보길 바란다.
아래 이 방식을 이용해서 푼 알고리즘 문제를 하나 적고가겠다!
프로그래머스 - 메뉴리뉴얼
package Programmers;
import java.util.*;
public class 메뉴리뉴얼 {
// 나중에 풀어보기
public static void main(String[] args) {
String[] orders = {"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"};
int[] course = {2,3,4};
Solution solution = new Solution();
String[] solution1 = solution.solution(orders, course);
System.out.println("solution1 = " + Arrays.toString(solution1));
}
static class Solution {
static HashMap<String, Integer> hm = new HashMap<>();
public String[] solution(String[] orders, int[] course) {
String[] answer = {};
int len[] = new int[course[course.length-1]+1];
ArrayList<String> al = new ArrayList<>();
//Sorting
for(int i = 0; i < orders.length; i++){
final char[] chars = orders[i].toCharArray();
Arrays.sort(chars);
for(int j = 0; j < course.length; j++){
if(course[j] <= orders[i].length()){
nCr(chars, orders[i].length(), course[j], 0, "");
}
}
}
for(String k : hm.keySet()){
if(2 <= hm.get(k)){
if(len[k.length()] < hm.get(k)){
len[k.length()] = hm.get(k);
}
}
}
for (String k: hm.keySet()){
if(2 <= hm.get(k) && len[k.length()] == hm.get(k)){
al.add(k);
}
}
Collections.sort(al);
final String[] strings = al.toArray(new String[0]);
return strings;
}
static void nCr(char[] str, int n, int r, int start, String result){
if(r == 0){
hm.put(result, hm.getOrDefault(result, 0)+1);
return;
}else{
for(int i = start; i < str.length; i++){
nCr(str, n, r-1, i+1, result+str[i]);
}
}
}
}
}
