알고리즘 (1-1 ~ 1-4)

1억은 == 1초

1억만 있었으면 좋겠다...

완전탐색 (Brute Force)

문제: 배열안에 두 수를 선택해서 두 수의 합이 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);
       }
   }
}

문제: 한 개의 회의실에서 진행할 수 있는 최대 회의 수 구하기

• 목표: 하나의 회의실에서 최대한 많은 회의 진행하기
• 입력: 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);
   }
}