배운 내용 정리

[KWY0218]

• 힙

  • 루트 노드에는 항상 최댓값(최대 힙) 또는 최솟값(최소 힙)이 저장되는 완전 이진 트리로 push 및 poll 연산을 O(logN)으로 수행한다.

• 우선 순위 큐

  • 우선순위가 높은 데이터가 먼저 나가는 자료구조로 주로 힙을 이용한다.
  • 주로 그리디 문제를 풀 때 사용한 것 같다.

• 이분 탐색

  • 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 O(logN)으로 탐색할 수 있다.
  • 데이터를 정렬해도 상관없고, 데이터 양이 100,000이 넘어가면서 탐색이 필요할 때 사용할 것 같다.

• 파라메트릭 서치

  • 최적화 문제를 결정 문제로 바꾸어 푸는 것
    • 최적화 문제란 문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제
    • 결정 문제란 (예, 아니오) 이 2개의 답만이 나오는 문제로 주로 이분 탐색을 통해 문제를 해결한다.
  • 파라메트릭 서치를 조사하는 주차에 ‘택배’ 문제가 나왔는데, 이때 택배 문제에서 최댓값을 구하라는 것을 보고 파라메트릭 서치로 풀어보려 했다. 이처럼 언제 파라메트릭 서치를 사용해야 되는지는 감이 안 온다. (문제를 많이 풀어봐야 알 것 같긴 하다.)

• 컵라면

  • 컵라면 문제를 포함한 그리디 문제를 풀 때 주로 실시간 형식으로 문제를 풀었다. 결과를 다 알고 있기 때문에 뒤에서부터 연산을 진행하는 방식을 알게 되었다.
  • 뒤에서 부터 푸는 자바 코드

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    
    List<List<Integer>> nums = new ArrayList<>();
    for (int i = 0; i <= n; i++) {
        nums.add(new ArrayList<>());
    }
    for (int i = 0; i < n; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int d = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        nums.get(d).add(c);
    }
    int answer = 0;
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    for (int i = n; i > 0; i--) {
        for (int num : nums.get(i)) {
            pq.add(num);
        }
        if (!pq.isEmpty()) {
            answer += pq.poll();
        }
    }
    System.out.println(answer);

• n+1 카드 게임

  • N+1 문제를 실시간으로 풀려 하니 너무 어려웠지만, 등가 상황 대치에 대한 설명과 접근 방식을 통해 다음 날 풀 수 있었고, 그리디 문제 유형을 하나 더 알게 되었다.
  • 또, 이번에 배열 내에 있는 값을 제거할 때 remove 함수를 처음 사용해 봤다. remove는 O(N)이기 때문에 알고리즘을 풀 때 되도록 pop과 poll을 사용하려 했다. 이번 문제를 통해서 데이터양을 비교해 보고 양이 적다면 remove를 사용해도 되는 것을 배웠다.
  • 자바에서 remove 함수는 int형 또는 Object를 매개변수로 받는다. int형은 해당 인덱스의 값을 제거하고, Object는 해당 객체를 삭제한다. N+1 카드 문제에서는 인덱스의 값을 제거하는 것이 아닌 숫자를 없애야 하므로 Integer.valueOf()를 통해 원시 타입을 객체 타입으로 바꿔서 값을 제거할 수 있는 것을 알게 되었다.

  public int solution(int coin, int[] cards) {
    int n = cards.length;
    List<Integer> handCards = new ArrayList<>();
    List<Integer> drawCards = new ArrayList<>();
    for (int i = 0; i < n / 3; i++) {
        handCards.add(cards[i]);
    }
  
    int idx = n / 3;
    int target = n + 1;
    int answer = 1;
    while (idx < n) {
        // draw card
        for (int i = idx; i < idx + 2; i++) {
            drawCards.add(cards[i]);
        }
        idx += 2;
  
        int c1 = -1;
        int c2 = -1;
        int temp = Integer.MAX_VALUE;
        // 손에 있는 카드로만 해결할 수 있는 경우
        for (int i = 0; i < handCards.size(); i++) {
            for (int j = i + 1; j < handCards.size(); j++) {
                int sum = handCards.get(i) + handCards.get(j);
                if (sum == target) {
                    c1 = handCards.get(i);
                    c2 = handCards.get(j);
                }
            }
        }
        if (c1 != -1) {
            handCards.remove(Integer.valueOf(c1));
            handCards.remove(Integer.valueOf(c2));
            answer++;
            continue;
        }
  
        // 카드 한장을 뽑아야 하는 경우
        if (coin >= 1 && drawCards.size() >= 1) {
            for (int i = 0; i < handCards.size(); i++) {
                for (int j = 0; j < drawCards.size(); j++) {
                    int sum = handCards.get(i) + drawCards.get(j);
                    if (sum == target) {
                        c1 = handCards.get(i);
                        c2 = drawCards.get(j);
                    }
                }
            }
            if (c1 != -1) {
                handCards.remove(Integer.valueOf(c1));
                drawCards.remove(Integer.valueOf(c2));
                answer++;
                coin -= 1;
                continue;
            }
        }
  
        // 카드 두장을 뽑아야 하는 경우
        if (coin >= 2 && drawCards.size() >= 2) {
            for (int i = 0; i < drawCards.size(); i++) {
                for (int j = i + 1; j < drawCards.size(); j++) {
                    int sum = drawCards.get(i) + drawCards.get(j);
                    if (sum == target) {
                        c1 = drawCards.get(i);
                        c2 = drawCards.get(j);
                    }
                }
            }
            if (c1 != -1) {
                drawCards.remove(Integer.valueOf(c1));
                drawCards.remove(Integer.valueOf(c2));
                answer++;
                coin -= 2;
                continue;
            }
        }
  
        break;
    }
    return answer;
  }

• 택배

  어떻게 풀어야 하는지 접근 방식을 몰랐기 때문에 푸는데 애를 먹었다. 문제를 풀 때 배낭 문제처럼 풀어야 하나 고민하기도 했지만 구현을 못할 것 같아 포기했다. 검색을 통해 풀이를 보는데도 풀이 방식에 대해 오래 걸렸고, 간신히 이해하며 정리했다.

  풀어보니 회의실 배정 문제와 비슷한 것 같았고, 이러한 문제 유형을 여러 번 풀어봐야 해당 풀이 방식 또한 적응할 수 있을 것 같다.