완전 탐색과 그리디 알고리즘

🗒️ 플로우차트

 

1️⃣ 완전 탐색

1. 개념

• 가능한 모든 경우를 전부 다 해보는 방법

2. 예시

 

1) 비밀번호 찾기

• 비밀번호 4자리 숫자 / 0000 ~ 9999
• 9999 까지 다 입력해서 찾기 (느리지만 무조건 정답을 찾음)

2) 쇼핑몰 최저가 찾기

• 모든 쇼핑몰 가격 전부 비교 > 가장 싼 곳 선택

3. 장단점

 

1) 장점

• 생각하기 쉽다
• 구현이 단순함
• 정답을 절대 놓치지 않음

2) 단점

• 경우의 수가 많아지면 느림
• 숫자가 조금만 커져도 시간 폭발
• 문제가 작을 때만 쓰기 좋음

4. 반복문을 이용한 완전 탐색

 

1) 구현 방법

• for문 / while문
• 주어진 범위나 조건 파악 > 범위 내의 모든 경우를 반복문으로 확인

2) 대표적인 문제 예시: 두 수의 합이 target인 경우 찾기

• 문제 분석 및 풀이 아이디어

문제: 배열안에 두 수를 선택해서 두 수의 합이 target이 되는 조합을 찾기
- 목표: 주어진 배열에서 합이 target이 되는 두 수의 인덱스 반환
- 입력: 정수 배열과 목표값(target)
- 출력: 두 수의 인덱스를 담은 배열
- 조건:
 1. 같은 요소를 두 번 사용할 수 없음
 2. 답이 없는 경우 빈 배열 반환

접근 방법: 완전 탐색

풀이:
1. 배열 순회를 통해 첫 번째 수 선택 단계
  1.1. 배열의 첫 번째 요소부터 순차적으로 선택
  1.2. 선택한 수를 첫 번째 수로 지정

2. 두 번째 수 선택 및 검증 단계
  2.1. 첫 번째 수 다음 인덱스부터 배열 끝까지 순회
  2.2. 현재 선택된 두 수의 합이 target과 같은지 확인
  2.3. target과 같다면 두 수의 인덱스 반환
  2.4. target과 다르다면 다음 수 선택하여 2.2로 돌아가기

3. 결과 반환 단계
  3.1. 조합을 찾은 경우 인덱스 배열 반환
  3.2. 찾지 못한 경우 빈 배열 반환

시간복잡도:
1. 첫 번째 수 선택: O(N)
2. 두 번째 수 선택 및 검증: O(N)
3. 결과 반환: O(1)
→ 최종 시간복잡도: 이중 for문이므로 O(N²)

public class Solution {
   public static int[] findPairs(int[] numbers, int target) {
       // 1. 첫 번째 수 선택 단계
       for (int i = 0; i < numbers.length; i++) {
           // 1.1. 배열의 첫 번째 요소부터 순차적으로 선택
           // 1.2. 선택한 수를 첫 번째 수로 지정
           
           // 2. 두 번째 수 선택 및 검증 단계
           // 2.1. 첫 번째 수 다음 인덱스부터 배열 끝까지 순회
           for (int j = i + 1; j < numbers.length; j++) {
               // 2.2. 현재 선택된 두 수의 합이 target과 같은지 확인
               if (numbers[i] + numbers[j] == target) {
                   // 2.3. target과 같다면 두 수의 인덱스 반환
                   return new int[]{i, j};
               }
               // 2.4. target과 다르다면 다음 수 선택하여 2.2로 돌아가기
           }
       }
       // 3. 결과 반환 단계
       // 3.1. 조합을 찾은 경우 위에서 이미 반환
       // 3.2. 찾지 못한 경우 빈 배열 반환
       return new int[]{};
   }

   public static void main(String[] args) {
       // 테스트용 입력값 설정
       int[] numbers = {2, 11, 7, 15};
       int target = 9;  // 예상 결과: [0, 2] (2 + 7 = 9)

       // findPairs 메서드 실행
       int[] result = findPairs(numbers, target);

       // 결과 출력 및 검증
       if (result.length == 0) {
           System.out.println("합이 " + target + "이 되는 두 수를 찾을 수 없습니다.");
       } else {
           System.out.printf("찾은 인덱스: [%d, %d]\n", result[0], result[1]);
           System.out.printf("해당 값: %d + %d = %d\n", 
               numbers[result[0]], numbers[result[1]], target);
       }
   }
}

• 배열에서 두 개를 뽑아서 합이 target이 되는지 전부 확인

첫 번째 숫자 하나 고르고
→ 두 번째 숫자 전부 다 붙여보기

> 이중 for문 = O(N2제곱)

2️⃣ 그리디 알고리즘

1. 개념

• 지금 당장 제일 좋아 보이는 선택을 하는 방법

2. 예시

 

1) 거스름돈

상황: 거스름돈 1260원을 최소한의 동전으로 거슬러주기
고려사항: 500원, 100원, 50원, 10원 동전 사용
그리디 방식: 가장 큰 단위의 동전부터 최대한 사용하기

처리 결과
- 500원: 2개 (1000원)
- 100원: 2개 (200원)
- 50원: 1개 (50원)
- 10원: 1개 (10원)
> 최종 결과: 총 6개의 동전 사용

• 제일 큰 동전부터 씀 / 총 동전 개수 최소 / 빠르고 간단

2) 회의실 배정

상황: 1개의 회의실을 다수의 팀이 시간대별로 사용하고자 할 때, 
      최대한 많은 회의를 진행하기
      
예시 상황:
- 회의 개수 = 8
- 회의 시간 목록 = 
	1번팀: 1시 ~ 4시
	2번팀: 3시 ~ 5시
	3번팀: 0시 ~ 6시
	4번팀: 5시 ~ 7시
	5번팀: 3시 ~ 8시
	6번팀: 5시 ~ 9시
	7번팀: 6시 ~ 10시
	8번팀: 8시 ~ 11시
	
그리디 방식: 
1. 회의 종료 시각이 빠른 순서로 정렬하기
2. 이전 회의 종료 시각 이후에 시작하는 회의 중 가장 일찍 끝나는 회의 선택하기

처리 결과: 
- 1번팀: 1시~4시 선택
- 4번팀: 5시~7시 선택
- 8번팀: 8시~11시 선택
> 최종 결과: 총 3개의 회의 진행 가능

• 빨리 끝나는 회의부터 선택 > 회의를 더 많이 넣을 수 있음

3. 장단점

 

1) 장점

 

• 빠르다 
• 구현이 간단하다
• 직관적이다

2) 단점

 

• 항상 정답은 아님
• 아무 문제에나 쓰면 망함 = 적용할 수 있는 유형 한정적 > 조건 중요

4. 필요 조건

 

1) 탐욕 선택 속성

• 지금 선택한 게 나중에 봐도 틀리지 않아야 함
• 예시) 회의실 문제 > 최대 회의 수 목표 달성

2) 최적 부분 구조

• 작은 문제의 정답들이 모이면 큰 문제의 정답이 된다
• 예시) 거스름돈 문제 > 최소 동전 개수 사용

3) 두 조건의 차이점

• 탐욕 선택 속성: 문제 해결 과정에서 현재 선택의 정당성 보장 중요
  > 각각의 선택에 초점
• 최적 부분 구조: 문제를 분할하여 최적해를 조합할 수 있는 구조인지 확인
  > 문제의 구조에 초점
• 두 개 모두 조건을 만족해야 그리디 사용 가능

3️⃣ 완전 탐색 VS 그리디

1. 특징 비교

구분	완전 탐색	그리디
방법	전부 다 해봄	지금 최선만 선택
속도	느림	빠름
정답 보장	항상 가능	조건부 가능
사용 시기	문제 작을 때	구조가 맞을 때

 

 

2. 문제 풀이로 비교(거스름돈 문제)

 

1) 공통상황

• 철수가 거스름 돈을 받아야 함 / 최소 동전 개수 구하기
• 입력: 사용할 수 있는 동전의 종류: 500원, 100원, 50원, 10원
           첫째 줄에 거슬러 주어야 할 금액 N이 주어집니다. (0 ≤ N ≤ 10,000)
• 출력: 거스름돈 N원을 만들기 위한 최소 동전 개수를 출력

2) 그리디 알고리즘 풀이

• 큰 동전부터 사용 / 항상 정답이 아닐 수 있음

접근방법: 
- 가장 큰 단위의 동전부터 최대한 거스름돈 주기(그리디)

1. 초기화 단계
   1.1. 동전을 큰 단위부터 작은 단위 순으로 정렬
   1.2. 거스름돈 금액을 저장할 변수 준비
   1.3. 사용된 동전 개수를 저장할 변수 초기화

2. 거스름돈 계산 단계
   2.1. 가장 큰 단위의 동전부터 순차적으로 진행
   2.2. 현재 동전으로 거스름돈을 최대한 많이 거슬러줌
   2.3. 남은 거스름돈에 대해 다음으로 큰 동전으로 반복

3. 결과 반환 단계
   3.1. 남은 금액이 0이면 사용된 총 동전 개수 반환
   3.2. 남은 금액이 0이 아니면, -1 반환
   
시간복잡도: O(K) - K은 동전의 종류 수

import java.util.*;

public class Solution {
    public static int coinChange(int[] coins, int target) {
        // 1. 초기화 단계
        // 1.1. 동전을 큰 단위부터 작은 단위 순으로 정렬
        Arrays.sort(coins);

        // 1.2. 거스름돈 금액을 저장할 변수 초기화
        int remainingAmount = target;
        // 1.3. 사용된 동전 개수를 저장할 변수 초기화
        int coinCount = 0;

        // 2. 큰 동전부터 사용하는 단계
        // 2.1. 가장 큰 단위의 동전부터 순차적으로 진행
        for (int i=coins.length-1; i>=0; i--){
            // 2.2. 현재 동전으로 거스름돈을 최대한 많이 거슬러줌
            coinCount += remainingAmount / coins[i];  // 현재 동전으로 거슬러 줄 수 있는 개수
            remainingAmount %= coins[i];              // 남은 금액 계산
            // 2.3. 남은 거스름돈에 대해 다음으로 큰 동전으로 반복
        }

        // 3. 결과 반환 단계
        // 3.1. 사용된 동전 개수 반환
        return coinCount;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] coins = {500, 100, 50, 10};

        // 거스름돈 금액 입력 받기
        int target = scanner.nextInt();

        // 결과 출력
        System.out.println(coinChange(coins, target));
    }
}

3) 완전 탐색 풀이

• 모든 경우를 다 해봐서 제일 적은 동전 개수 찾기

1. 초기화 단계
   1.1. 각 동전 별로 사용 가능한 최대 개수 계산
        - 목표 금액 / 동전 금액 = 최대 사용 가능 개수
        예) 500원짜리는 최대 몇개, 100원짜리는 최대 몇개...
   1.2. 최소 동전 개수를 저장할 변수를 최댓값으로 초기화

2. 모든 조합 시도 단계 (4중 for문 사용)
   2.1. 500원: 0개부터 최대 개수까지 반복
   2.2. 100원: 0개부터 최대 개수까지 반복
   2.3.  50원: 0개부터 최대 개수까지 반복
   2.4.  10원: 0개부터 최대 개수까지 반복
        각 조합에 대해:
        - 현재 조합으로 만들어지는 총 금액 계산
        - 목표 금액과 일치하는지 확인
        - 일치하면 사용된 동전 개수(현재 4중 for문의 각 인덱스 합)와 
          현재 최소값 비교하여 갱신

3. 결과 반환 단계
   3.1. 찾은 최소 동전 개수 반환
   3.2. 해를 찾지 못한 경우 -1 반환
   
시간복잡도: O(n₁ × n₂ × n₃ × n₄)
- 각 n은 각 동전으로 만들 수 있는 최대 개수입니다.
예를 들어 2000원을 만들 때:
500원: 최대 4개 (n₁ = N//500)
100원: 최대 20개 (n₂ = N//100)
50원: 최대 40개 (n₃ = N//50)
10원: 최대 200개 (n₄ = N//10)
최종 시간 복잡도: O(N^4)

public static int coinChange(int[] coins, int target) {
    // 1. 초기화 단계
    // 1.1. 각 동전 별로 사용 가능한 최대 개수 계산
    //      - 목표 금액 / 동전 금액 = 최대 사용 가능 개수
    int[] maxCounts = new int[coins.length];
    for (int i = 0; i < coins.length; i++) {
        maxCounts[i] = target / coins[i];
    }

    // 1.2. 최소 동전 개수를 저장할 변수를 최댓값으로 초기화
    int minCoins = Integer.MAX_VALUE;

    // 2. 모든 조합 시도 단계 (4중 for문 사용)
    // 2.1. 500원: 0개부터 최대 개수까지 반복
    for (int i = 0; i <= maxCounts[0]; i++) {
        // 2.2. 100원: 0개부터 최대 개수까지 반복
        for (int j = 0; j <= maxCounts[1]; j++) {
            // 2.3. 50원: 0개부터 최대 개수까지 반복
            for (int k = 0; k <= maxCounts[2]; k++) {
                // 2.4. 10원: 0개부터 최대 개수까지 반복
                for (int l = 0; l <= maxCounts[3]; l++) {
                    // 각 조합에 대해:
                    // - 현재 조합으로 만들어지는 총 금액 계산
                    int currentSum = (coins[0] * i) + (coins[1] * j) +
                            (coins[2] * k) + (coins[3] * l);

                    // - 목표 금액과 일치하는지 확인
                    if (currentSum == target) {
                        // - 일치하면 사용된 동전 개수(현재 4중 for문의 각 인덱스 합)와 
                        //   현재 최소값 비교하여 갱신
                        minCoins = Math.min(minCoins, i + j + k + l);
                    }
                }
            }
        }
    }

    // 3. 결과 반환 단계
    // 3.1. 찾은 최소 동전 개수 반환
    // 3.2. 해를 찾지 못한 경우 -1 반환
    return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
}

 

4) 풀이 비교

구분	그리디	완전 탐색
생각 방법	지금 제일 좋은 선택	다 해봄
경우의 수	거의 없음	엄청 많음
속도	빠름	느림
정답 보장	조건 맞을 때만	항상 보장
코딩 테스트	자주 사용	위험