[2022-1-7] 프로그래머스 연습 문제 - 소수 만들기(조합, DFS 응용)

매일 공부 시작전에 프로그래머스 문제를 하나씩 풀고 있다. 오늘은 내적을 푸는 날이었는데 문제가 너무 쉬워서 다음문제도 풀어보았다. 문제 이름은 소수 만들기 였다.

 

정수배열에서 세가지 수를 뽑아 그 합이 소수인 개수를 구하는 문제였다. 이를 위해 일단 정수 배열에서 세개의 중복없는 수를 뽑아야 했고(조합) 그 수들의 집합의 합을 구해야 했다.

 

고등학교 때 이후로 순열 조합과 담쌓은지 오래돼서 기억을 되돌는데 오래 시간이 걸렸다.

 

그 후 조합을 구하는 알고리즘을 검색해 봤는데 DFS를 응용해서 구할 수 있다고 한다.

근데 이문제를 풀 때 DFS를 어떻게 응용해야 풀 수 있다는 건지 이해가 잘 안됐다. 그래서 재귀를 이것 저것 다뤄보다가 결국 소 뒷걸음치다가 맞아서 아래와 같은 코드를 풀 수 있었다.

class Solution {
    private static final int DRAW_NUMBER = 3;
    private int answer;
    
    public int solution(int[] nums) {
        answer = 0;
        countPrimesNumber(nums,0,0,0);
        return answer;
    }

    private void countPrimesNumber(int[] nums,int begin, int depth, int sum){
        if(depth == DRAW_NUMBER){
            if(isPrime(sum)) answer++;
            return;
        }

        for(int index = begin;index < nums.length;index++){
            countPrimesNumber(nums, index+1, depth+1,sum+nums[index]);
        }
    }

    private boolean isPrime(int number){
        for(int index = 2;index = Math.sqrt(number);index++){
            if(number % index == 0) return false;
        }
        return true;
    }
}

답은 정답이었지만 뭔가 찍어서 맞춘 느낌이 강했기 때문에 찝찝해서 조합과 DFS 가 무슨연관이 있는지 계속 생각해봤다. 

 

일단 DFS는 그래프의 탐색 알고리즘이다. 그러려면 정점과 간선이 필요하다. 여기서 정점이 될 수 있는 것은 배열의 정수들 뿐이다. nums 가 {1,2,3,4} 라고 배열 안의 정수들이 정점이라고 먼저 생각해봤다.

 

배열로 표현된 정점

그러면 간선은 어떻게 될까. 이 문제에서 그런 언급은 없었다. 그래서 일단 그을 수 있는 간선을 모두 그어 보았다.

간선 추가

DFS는 깊이 우선 탐색을 말하는데, 내가 찾은 가장 이해하기 쉬운 정의는 다음과 같다.

DFS : 그래프의 탐색 방법 중 하나로, 현재 정점과 인접한 간선들 중 아직 방문하지 않은 정점으로 향하는 간선을 무조건 따라간다. 더이상 방문할 곳이 없는 정점에 도달하면, 마지막으로 따라왔던 간선을 따라 뒤로 돌아간다.

하지만 조합을 구하기 위해서는 이와 다른 조건을 가져야 한다. 일단 방문하지 않은 정점을 따라가는 것이 아니다. 배열에서 현재 자신보다 인덱스가 큰 정점에 방문한다. 또한 이전 정점으로 돌아가는 조건도 추가된다. 기존에는 더이상 방문할 수 있는 정점이 없을 때만 이전 정점으로 돌아가지만, 집합의 크기가 3일 때, 즉 Depth가 3이되었을 때 탐색을 종료하고 이전 정점으로 돌아간다.

 

이렇게 구현방법을 찾아보고 고민하다보니 백트래킹(Backtracking)이라는 개념이 있다는 것을 알게 됐다.

 

백트래킹은 현재 노드를 통한 탐색이 목표로 하는 노드를 찾는데 유망하지 않으면 부모노드로 돌아가 다른 노드를 검색한다는 의미이다. 이 문제에선 유망하다 유망하지 않다의 개념보단 조건에 맞고아니고에 문제기는 하지만 기존의 인접한 방문하지않은 모든 정점을 방문한다라는 정의에서 새로운 방문 조건을 추가하는 점에서 유사하다고 느꼈다.

 

 

느낀점

TIL을 시작하고 계속 간단한 논리적인 사고 정도를 요구하는 문제만 풀다가 정말 알고리즘이 필요한 문제를  처음 풀어본 것 같다. 어떻게 코딩테스트에 대비해서 알고리즘을 고민할지 고민이었는데 이렇게 문제들을 하나씩 풀어나가면서 만나는 알고리즘마다 각개격파식으로 공부해 나가는 것도 좋을 것 같다. 새로운 알고리즘 문제들도 보고싶고, 또 다른 DFS 문제도 만나서 얼른 오늘 공부한 내용으로 풀어보고 싶다!