DFS 활용 문제 - 동전 교환

오늘은 DFS 탐색 알고리즘을 사용한 동전 교환 문제를 풀어보려 합니다😊

 

DFS 동전교환

 

개요

문제 내용

이 문제의 포인트는 DFS 탐색 알고리즘을 활용, 배열을 내림차순으로 하여 시간을 단축하였는가, 탐색하지 않아도 될 상황을 제한하였는가 총 3가지 인 것 같아요. 바로 코드를 보면서 확인해 볼게요😀

 

Main📙

public class ExchangeCoins {
    static int n, m, result = Integer.MAX_VALUE;
   
    public static void main(String[] args) {
     ExchangeCoins T = new ExchangeCoins();
     Scanner sc = new Scanner(System.in);
     n = sc.nextInt();
     Integer[] arr = new Integer[n];
     for(int i = 0; i < n; ++i) {
         arr[i] = sc.nextInt();
     }
     Arrays.sort(arr, Collections.reverseOrder());
     m = sc.nextInt();
     T.DFS(0,0,arr);
     System.out.println(result);
    }
}

문제 요구 사항에 맞게 각 변수들에 값을 담았습니다. int n은 동전 종류의 개수이고, m은 거슬러야 할 금액입니다. 예시를 살펴보면 1원, 2원, 5원의 동전들이 주어지는데, 이 동전들을 한 배열에 담아서 사용하기 위해 arr를 선언하여 반복문을 통해 담아주었습니다. 평소에는 int[]를 사용하였지만, 서두에서 언급했듯이 내림차순으로 정렬하기 위해 Integer로 선언하였습니다.

 

📌 기본형을 객체로 다루기 위해서 사용하는 클래스를 래퍼 클래스(wrapper class)라고 합니다. int의 래퍼 클래스는 Integer입니다😀

 

내림차순으로 정렬하는 이유는, DFS 탐색 알고리즘은 트리 구조상 왼쪽부터 탐색하게 됩니다. 만약에 오름차순으로 1,2,5를 그대로 받았다면 예제 답인 15원이 될때까지 1원을 15번 사용한 결과부터 도출하게 됩니다. 하지만 우리가 풀어야 할 답은 최소로 동전을 사용해야 하기 때문에 큰 금액부터 돌면서 조건문을 통해 더 이상 트리를 탐색하지 않게 해야 시간복잡도가 많이 줄어듭니다. 이 부분은 DFS 함수 부분에서 더 자세히 설명할게요.

 

DFS📘

public void DFS(int L, int sum, Integer[] arr) {
    if(sum > m) return; // line 2
    if(L >= result) return; // line 3
    if(sum == m) {
        result = Math.min(result, L); // line 5
    } else {
        for(int i = 0; i < n; ++i) { // line 7
            DFS(L+1, sum+arr[i], arr);
        }
    }
}

DFS 탐색 방법

line 2를 보면 총 합계 sum이 주어진 거스름 금액 m보다 크면 return 하게 되어있습니다. 왜 설정해야 할까요? 만약 2원을 7번 사용하여 14원이 되었을 때, 1원을 한번 사용하면 합계가 15로 같아져서 문제가 안되지만 2원이나 5원을 사용하면 15원을 넘어가게 됩니다. 그렇게 계속해서 15원을 찾기 위해 누적하게 되고 무한루프에 빠지게 되기 때문에 설정하였습니다.

 

line 3을 보면 L 값이 result 값 이상이면 return하게 되어 있습니다. 여기서 L은 트리 구조상으로는 몇 번 노드를 사용하였는가 즉, 몇 개의 동전을 사용했는가를 뜻합니다. 만약 문제의 답인 5를 3번 사용한 결과에서 L은 3을 뜻하는대, 굳이 1원짜리 동전을 15번 즉 L이 15까지 갈 필요가 없습니다(최소 동전을 사용하기 때문) 

 

무한루프와 시간복잡도를 줄이기 위한 코드는 line2, 3을 통해 구현했습니다. 이제는 DFS 탐색을 해야 하는데 DFS는 if~else문을 사용합니다.

 

여기서 if 조건문으로는 문제에서 주어지는 거스름돈이 노드들의 합계와 같아야 합니다. 그때마다 결과값 result에 L값을 대입시켜주는데 DFS는 모든 노드를 탐색하기 때문에 문제 조건(최소 동전 개수)을 맞추기 위해 작은 값을 구해주는 Math.min() 함수를 사용했습니다. 

 

else문에서는 반복문을 통해 n만큼 반복하면서 노드를 뻗쳐나갑니다. 여기서는 3개의 동전이 주어졌고, 각 노드들마다 1원, 2원, 5원을 각각 더해주면서 트리 구조가 완성되겠습니다. 여기서 재귀로 DFS 함수를 호출하는대 L값은 동전을 하나 더 쓰기 때문에 +1을 해주고, 합계 sum에는 사용한 동전을 더해주면 됩니다.

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간 하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---

 

마치며

지금까지 동전 교환 문제를 풀어보았어요. 다음 문제는 순열에 대해서 알아보겠습니다😄