완전탐색과 그리디 알고리즘 (2)

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

 

학습 키워드

완전 탐색 ( Brute Force )

완전 탐색이 무엇인지 알아봅시다.

완전 탐색은 가능한 모든 경우의 수를 전부 확인하여 문제를 해결하는 방법입니다.

쉽게 말해 "가능한 모든 방법을 일일이 다 해보는 것 " 입니다.

 

완전 탐색 예시

인터넷 쇼핑몰 최저가 찾기

- 구매 품목: 라면 3개, 생수 2팩, 휴지 1팩
- 고려사항: 상품별 가격, 배송비, 무료배송 기준 금액, 묶음배송 할인 등을 
           종합적으로 고려하여 최저가 조합 찾기
- 완전 탐색 방식: 여러 쇼핑몰에서 구매 품목에 대한 합계 가격을 모두 비교하며 
                 최저가로 구해할 수 있는 쇼핑몰 선택

탐색 결과
- 쿠팡: 29,000원 (상품 26,000원 + 배송비 3,000원)
- 마켓컬리: 28,600원 (상품 26,100원 + 배송비 2,500원)
- SSG몰: 29,600원 (상품 29,600원 + 무료배송)
> 최종 선택 : 마켓컬리

 

비밀번호 찾기

- 상황: 4자리 숫자로 된 비밀번호 찾기 (0000~9999)
- 고려사항: 각 자리수마다 0~9까지의 숫자가 가능하므로 총 10000개의 경우의 수 확인
- 완전 탐색 방식: 0000부터 9999까지 순차적으로 모든 숫자 조합을 하나씩 시도

탐색결과
- 4868번 시도 끝에 비밀번호 4867임이 확인

 

완전 탐색의 장단점

장점

● 구현이 단순하고 이해하기 쉽습니다.

● 모든 경우를 확인하므로 반드시 정답을 찾을 수 있습니다.

● 문제를 처음 접근할 때 좋은 시작점이 됩니다.

 

단점 

● 모든 경우를 확인하므로 실행 시간이 오래 걸립니다.

● 경우의 수가 많아지면 현실적으로 해결이 어려울 수 있습니다.

 

완전 탐색으로 모든 문제를 해결할 수 있을까요?

❗
완전 탐색은 모든 문제 해결의 기본이 되는 좋은 시작점입니다. 
하지만 문제의 복잡도가 높아지거나 처리해야 할 데이터의 양이 늘어날수록 실행 시간이 기하급수적으로 증가하게 됩니다.
따라서 코딩 테스트에서는 상황에 맞는 최적화된 알고리즘(그리디, 백트래킹, 동적 계획법 등)을 선택하여 문제를 해결해야합니다. 
즉, 완전 탐색은 문제의 크기와 상황을 고려하여 전략적으로 사용해야 합니다.

 

반복문을 이용한 완전 탐색

반복문으로 완전 탐색을 구현하는 방법

반복문을 이용한 완전 탐색은 for문이나 while문을 사용하여 가능한 모든 경우를 순차적으로 탐색하는 방법입니다.
 
기본 구현 방법 
● 문제에서 주어진 범위나 조건을 파악합니다.
● 해당 범위 내의 모든 경우를 반복문으로 확인합니다.
● 각 경우마다 문제의 조건을 만족하는지 검사합니다.

 

대표적인 문제 예시 및 출이

두 수의 합이 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);
       }
   }
}

 

 

 

 

그리디 알고리즘 (  Greedy Algorithm )

 

그리디 알고리즘의 개념

그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 하는 방법입니다.
쉽게 말해 " 각 단계에서 최적이라고 생각되는 것을 선택하는 것" 입니다.

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

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

상황: 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개의 회의 진행 가능

그리디 알고리즘의 장단점
📌 장점
구현이 "비교적 단순"하고 "실행 속도가 빠릅"니다.
직관적이어서 이해하기 쉽습니다.
현재 상황에서 가장 좋은 것을 고르는 단순한 전략입니다.
📌 단점
항상 최적의 해를 보장하지는 않습니다.
각 단계에서의 최적의 선택이 전체적인 최적 해결책이 아닐 수 있습니다.
적용할 수 있는 문제의 유형이 한정적입니다.


그리드 알고리즘 두 가지 필수 조건

1. 탐욕 선택 속성
" 각 단계에서 선택한 방법이 이후의 결정과 상관없이 최종 답의 최적성을 유지 해야 합니다 "

[회의 시간표]
A팀: 1시~4시
B팀: 3시~5시
C팀: 5시~7시

[선택 과정]
1. 첫 선택: "가장 빨리 끝나는" A팀 선택
   - A팀이 4시에 끝나기 때문에 이후 시간대에 더 많은 회의를 배정할 수 있음
   - 이 선택이 "최대 회의 수"라는 최종 목표 달성에 최선!
   
2. 최적 부분 구조
" 전체 문제의 최적해가 문제를 나눈 각 부분 문제의 최적해를 결합해서 얻을 수 있어야 합니다 "

[상황] 거스름돈 1260원 (동전: 500원, 100원, 50원, 10원)

[해결 과정]
1.가장 큰 단위(500원)로 최대한 거스름돈을 해결 → 500원 2개 사용
2.남은 금액(260원)을 같은 방식으로 해결
	- 100원 2개 → 200원
	- 50원 1개 → 50원
	- 10원 1개 → 10원

각 단계의 "최대한 큰 동전 사용하기"의 결과가 모여서 전체 문제의 "최소 동전 개수"라는 최적해를 만듦

 

그리드 알고리즘 증명 방법

그리디 알고리즘으로 해결할 수 있는지 증명해야 합니다.

수학적 증명
" 가장 확실한 증명이지만, 난이도가 높다 "
[귀류법을 통한 회의실 배정 문제 증명 예시]
* 귀류법: 어떤 명제가 참임을 증명하기 위해, 그 명제가 거짓이라고 가정한 후 모순을 이끌어내는 증명 방법입니다.

1단계) 가정
   - "가장 일찍 끝나는 회의(A)를 선택하지 않는 최적해가 있다"고 가정

2단계) 최적해 분석
   - 최적해의 첫 회의를 B라고 하자
   - B의 종료 시간은 A의 종료 시간보다 늦거나 같음

3단계) 교체 가능성 증명
   - B를 A로 교체해도:
     * 회의 시간이 겹치지 않음 (A가 더 일찍 끝나므로)
     * 나머지 회의 일정에 영향 없음
     * 그런데 A를 선택하면 오히려 더 많은 시간을 확보할 수 있음

4단계) 결론
   - B를 A로 교체 후 상황 분석
     * 최소한 같은 개수의 회의를 진행할 수 있음
     * 더 많은 시간이 확보되어 더 많은 회의가 가능할 수도 있음
   - 최종 증명
     * "A를 선택하지 않는 것이 최적"이라는 가정이 모순
     * "가장 일찍 끝나는 회의(A)를 선택하는 것이 최적해"임이 증명됨
     

작은 예시로 검증
" 다양한 크기의 입력값으로 직접 테스트 "
[동전 거스름돈 문제 검증]
테스트 케이스 1: 작은 금액
- 상황: 160원
- 과정:
  1) 100원 1개 (남은 금액: 60원)
  2) 50원 1개 (남은 금액: 10원)
  3) 10원 1개
- 결과: 3개의 동전 사용으로 최적해

테스트 케이스 2: 각 동전의 배수
- 상황: 500원
- 결과: 500원 1개로 최적해

테스트 케이스 3: 모든 동전 필요
- 상황: 660원
- 과정:
  1) 500원 1개 (남은 금액: 160원)
  2) 100원 1개 (남은 금액: 60원)
  3) 50원 1개 (남은 금액: 10원)
  4) 10원 1개
- 결과: 4개의 동전이으로 최적홰

반례 찾기
" 그리디 알고리즘이 실패하는 경우 찾기 "
[잘못된 동전 구성의 반례]
상황: 동전 {500원, 400원, 100원}으로 800원 거슬러주기

그리디 방식:
1) 500원 선택 (남은 금액: 300원)
2) 100원 3개 사용
→ 총 4개 동전 사용

최적해:
1) 400원 2개 사용
→ 총 2개 동전으로 해결 가능

결론: 이런 반례가 있다면 그리디 접근이 부적절

기존 문제와의 비교
" 이미 증명된 문제들과 비교 분석 "
예시) 회의실 배정 vs 활동 선택 문제
1. 공통점
   - 시간이 겹치지 않게 선택
   - 종료 시간 기준 정렬 사용

2. 차이점
   - 회의실: 한 개의 회의실에서 최대 회의 수
   - 활동 선택: 여러 활동 중 겹치지 않는 최대 활동 수

3. 결론
   - 구조가 같으므로, 같은 그리디 접근 가능

 

※ 팁

● 수학적 증명이 아닌 경우 가능한 여러 방법으로 교차 검증할 것

● 반례를 찾으려는 노력이 중요

● 다양한 유형의 그리디 알고리즘 문제를 풀기

 

문제 분석 및 풀이 아이디어

문제: 한 개의 회의실에서 진행할 수 있는 최대 회의 수 구하기
- 목표: 하나의 회의실에서 최대한 많은 회의 진행하기
- 입력: N개의 회의 시간(시작 시간, 종료 시간)
- 출력: 최대 회의 개수
- 조건: 
 1. 한 회의가 끝나는 것과 동시에 다음 회의 시작 가능
 2. 회의는 중간에 중단될 수 없음
 3. 시작 시간과 종료 시간이 같을 수도 있음

접근 방법: 
- 핵심 아이디어: "종료 시간이 빠른 회의부터 선택하기"
- 알고리즘 선정: 그리디 알고리즘
	* 현재 시점에서 가장 빨리 끝나는 회의를 선택하는 것이 최적해
	* 종료 시간이 빠를수록 이후 선택할 수 있는 회의가 많아짐
	* 정렬 후 단순 순회로 해결 가능
	
세부 구현:
1. 정렬 단계
   1.1. 종료 시간을 기준으로 오름차순 정렬

2. 회의 선택 및 카운트 단계
   2.1. 첫 번째 회의 선택 (가장 일찍 끝나는 회의) 및 카운트 1 증가
   2.2. 첫 번째 회의의 종료 시간 저장
   2.3. 이전 선택한 회의의 종료 시간보다 시작 시간이 같거나 늦은 회의 중에서
        가장 일찍 끝나는 회의 선택하고 카운트 증가
   2.4. 더 이상 선택할 회의가 없을 때까지 2.3 반복
3. 결과 반환 단계
   3.1. 회의 카운트 반환

시간복잡도:
1. 정렬 단계: O(NlogN)
2. 회의 선택 단계: O(N)
3. 결과 반환 단계: O(1)
→ 최종 시간복잡도: O(NlogN)


" 코드스니펫 구현 코드 "
class Solution {
   public static int maxMeetings(int[][] meetings) {
       // 1. 정렬 단계
       // 1.1. 종료 시간을 기준으로 오름차순 정렬
       Arrays.sort(meetings, (a, b) -> {
           return a[1] - b[1];
       });
       
       // 2. 회의 선택 및 카운트 단계
       // 2.1. 첫 번째 회의 선택 및 카운트 1 증가
       int count = 1;  
       // 2.2. 첫 번째 회의의 종료 시간 저장
       int lastEndTime = meetings[0][1];
       
       // 2.3. 이전 선택한 회의의 종료 시간보다 시작 시간이 같거나 늦은 회의 중에서
       //      가장 일찍 끝나는 회의 선택하고 카운트 증가
       // 2.4. 더 이상 선택할 회의가 없을 때까지 2.3 반복
       for (int i = 1; i < meetings.length; i++) {
           if (meetings[i][0] >= lastEndTime) {
               count++;
               lastEndTime = meetings[i][1];
           }
       }
       
       // 3. 결과 반환 단계
       // 3.1. 회의 카운트 반환
       return count;
   }

   public static void main(String[] args) {
       // 테스트용 회의 배열 생성
       int[][] meetings = {
           {1, 4},  // 1번팀
           {3, 5},  // 2번팀
           {0, 6},  // 3번팀
           {5, 7},  // 4번팀
           {3, 8},  // 5번팀
           {5, 9},  // 6번팀
           {6, 10}, // 7번팀
           {8, 11}  // 8번팀
       };
       
       // 최대 회의 개수 구하기
       int maxCount = maxMeetings(meetings);
       System.out.println("최대 진행 가능한 회의 수: " + maxCount);
   }
}

 

완전 탐색 VS 그리디 알고리즘 비교

 

두 알고리즘의 특징 비교

 

각 알고리즘 사용은 언제가 적절한가?

 

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {

        int[] numbers = {2, 11, 7, 15};
        int target = 9;

        int[] result = findPairs(numbers, target);
        System.out.println(Arrays.toString(result));
    }

    private static int[] findPairs(int[] numbers, int target) {
        // 1. 배열을 순회해서 천번째 수 선택
        for (int i = 0; i < numbers.length; i++) {
            // 1.1 배열의 첫 번째 요소부터 순차적으로 선택
            int num1 = numbers[i]; // 첫번째 수 선택

            // 2. 두 번째 수 선택 및 검증 단계
            // 2.1 첫번째 수 다음 인덱스부터 배열 끝까지 순회해서 선택
            for (int j = i + 1; j < numbers.length; j++) {
                // 2.2 현재 선택된 두 수의 합이 target과 같은지 확인
                int num2 = numbers[j];
                if (num1 + num2 == target) {
                    // 2.3 target과 같다면 두 수의 인덱스를 반환
                    return new int[]{i, j};
                }
            }
        }
            // 3. 결과 반환 단계
            // 3.1 조합을 찾지 못한 경우 빈 배열을 반환
            return new int[]{};
        }
    }