René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"배운 내용 정리","articleBody":"- **힙**\r\n    - 루트 노드에는 항상 최댓값(최대 힙) 또는 최솟값(최소 힙)이 저장되는 완전 이진 트리로 push 및 poll 연산을 O(logN)으로 수행한다.\r\n- **우선 순위 큐**\r\n    - 우선순위가 높은 데이터가 먼저 나가는 자료구조로 주로 힙을 이용한다.\r\n    - 주로 그리디 문제를 풀 때 사용한 것 같다.\r\n- **이분 탐색**\r\n    - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 O(logN)으로 탐색할 수 있다.\r\n    - 데이터를 정렬해도 상관없고, 데이터 양이 100,000이 넘어가면서 탐색이 필요할 때 사용할 것 같다.\r\n- **파라메트릭 서치**\r\n    - 최적화 문제를 결정 문제로 바꾸어 푸는 것\r\n        - 최적화 문제란 문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제\r\n        - 결정 문제란 (예, 아니오) 이 2개의 답만이 나오는 문제로 주로 이분 탐색을 통해 문제를 해결한다.\r\n    - 파라메트릭 서치를 조사하는 주차에 ‘택배’ 문제가 나왔는데, 이때 택배 문제에서 최댓값을 구하라는 것을 보고 파라메트릭 서치로 풀어보려 했다. 이처럼 언제 파라메트릭 서치를 사용해야 되는지는 감이 안 온다. (문제를 많이 풀어봐야 알 것 같긴 하다.)\r\n- **컵라면**\r\n    - 컵라면 문제를 포함한 그리디 문제를 풀 때 주로 실시간 형식으로 문제를 풀었다. 결과를 다 알고 있기 때문에 뒤에서부터 연산을 진행하는 방식을 알게 되었다.\r\n    - 뒤에서 부터 푸는 자바 코드\r\n        ```java\r\n        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n        int n = Integer.parseInt(br.readLine());\r\n        \r\n        List\u003cList\u003cInteger\u003e\u003e nums = new ArrayList\u003c\u003e();\r\n        for (int i = 0; i \u003c= n; i++) {\r\n            nums.add(new ArrayList\u003c\u003e());\r\n        }\r\n        for (int i = 0; i \u003c n; i++) {\r\n            StringTokenizer st = new StringTokenizer(br.readLine());\r\n            int d = Integer.parseInt(st.nextToken());\r\n            int c = Integer.parseInt(st.nextToken());\r\n            nums.get(d).add(c);\r\n        }\r\n        int answer = 0;\r\n        PriorityQueue\u003cInteger\u003e pq = new PriorityQueue\u003c\u003e(Collections.reverseOrder());\r\n        for (int i = n; i \u003e 0; i--) {\r\n            for (int num : nums.get(i)) {\r\n                pq.add(num);\r\n            }\r\n            if (!pq.isEmpty()) {\r\n                answer += pq.poll();\r\n            }\r\n        }\r\n        System.out.println(answer);\r\n        ```\r\n        \r\n- **n+1 카드 게임**\r\n    - N+1 문제를 실시간으로 풀려 하니 너무 어려웠지만, 등가 상황 대치에 대한 설명과 접근 방식을 통해 다음 날 풀 수 있었고, 그리디 문제 유형을 하나 더 알게 되었다.\r\n    - 또, 이번에 배열 내에 있는 값을 제거할 때 remove 함수를 처음 사용해 봤다. remove는 O(N)이기 때문에 알고리즘을 풀 때 되도록 pop과 poll을 사용하려 했다. 이번 문제를 통해서 데이터양을 비교해 보고 양이 적다면 remove를 사용해도 되는 것을 배웠다.\r\n    - 자바에서 remove 함수는 int형 또는 Object를 매개변수로 받는다. int형은 해당 인덱스의 값을 제거하고, Object는 해당 객체를 삭제한다. N+1 카드 문제에서는 인덱스의 값을 제거하는 것이 아닌 숫자를 없애야 하므로 Integer.valueOf()를 통해 원시 타입을 객체 타입으로 바꿔서 값을 제거할 수 있는 것을 알게 되었다.\r\n    \r\n    ```java\r\n    public int solution(int coin, int[] cards) {\r\n      int n = cards.length;\r\n      List\u003cInteger\u003e handCards = new ArrayList\u003c\u003e();\r\n      List\u003cInteger\u003e drawCards = new ArrayList\u003c\u003e();\r\n      for (int i = 0; i \u003c n / 3; i++) {\r\n          handCards.add(cards[i]);\r\n      }\r\n    \r\n      int idx = n / 3;\r\n      int target = n + 1;\r\n      int answer = 1;\r\n      while (idx \u003c n) {\r\n          // draw card\r\n          for (int i = idx; i \u003c idx + 2; i++) {\r\n              drawCards.add(cards[i]);\r\n          }\r\n          idx += 2;\r\n    \r\n          int c1 = -1;\r\n          int c2 = -1;\r\n          int temp = Integer.MAX_VALUE;\r\n          // 손에 있는 카드로만 해결할 수 있는 경우\r\n          for (int i = 0; i \u003c handCards.size(); i++) {\r\n              for (int j = i + 1; j \u003c handCards.size(); j++) {\r\n                  int sum = handCards.get(i) + handCards.get(j);\r\n                  if (sum == target) {\r\n                      c1 = handCards.get(i);\r\n                      c2 = handCards.get(j);\r\n                  }\r\n              }\r\n          }\r\n          if (c1 != -1) {\r\n              handCards.remove(Integer.valueOf(c1));\r\n              handCards.remove(Integer.valueOf(c2));\r\n              answer++;\r\n              continue;\r\n          }\r\n    \r\n          // 카드 한장을 뽑아야 하는 경우\r\n          if (coin \u003e= 1 \u0026\u0026 drawCards.size() \u003e= 1) {\r\n              for (int i = 0; i \u003c handCards.size(); i++) {\r\n                  for (int j = 0; j \u003c drawCards.size(); j++) {\r\n                      int sum = handCards.get(i) + drawCards.get(j);\r\n                      if (sum == target) {\r\n                          c1 = handCards.get(i);\r\n                          c2 = drawCards.get(j);\r\n                      }\r\n                  }\r\n              }\r\n              if (c1 != -1) {\r\n                  handCards.remove(Integer.valueOf(c1));\r\n                  drawCards.remove(Integer.valueOf(c2));\r\n                  answer++;\r\n                  coin -= 1;\r\n                  continue;\r\n              }\r\n          }\r\n    \r\n          // 카드 두장을 뽑아야 하는 경우\r\n          if (coin \u003e= 2 \u0026\u0026 drawCards.size() \u003e= 2) {\r\n              for (int i = 0; i \u003c drawCards.size(); i++) {\r\n                  for (int j = i + 1; j \u003c drawCards.size(); j++) {\r\n                      int sum = drawCards.get(i) + drawCards.get(j);\r\n                      if (sum == target) {\r\n                          c1 = drawCards.get(i);\r\n                          c2 = drawCards.get(j);\r\n                      }\r\n                  }\r\n              }\r\n              if (c1 != -1) {\r\n                  drawCards.remove(Integer.valueOf(c1));\r\n                  drawCards.remove(Integer.valueOf(c2));\r\n                  answer++;\r\n                  coin -= 2;\r\n                  continue;\r\n              }\r\n          }\r\n    \r\n          break;\r\n      }\r\n      return answer;\r\n    }\r\n    ```\r\n    \r\n- **택배**\r\n    \r\n    어떻게 풀어야 하는지 접근 방식을 몰랐기 때문에 푸는데 애를 먹었다. 문제를 풀 때 배낭 문제처럼 풀어야 하나 고민하기도 했지만 구현을 못할 것 같아 포기했다. 검색을 통해 풀이를 보는데도 풀이 방식에 대해 오래 걸렸고, 간신히 이해하며 정리했다.\r\n    \r\n    풀어보니 회의실 배정 문제와 비슷한 것 같았고, 이러한 문제 유형을 여러 번 풀어봐야 해당 풀이 방식 또한 적응할 수 있을 것 같다.\r\n\r\n![A4 - 1](https://github.com/user-attachments/assets/9639efce-679a-4de0-9cca-03bb6bf50c76)\r\n","author":{"url":"https://github.com/KWY0218","@type":"Person","name":"KWY0218"},"datePublished":"2024-07-30T08:28:50.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/7/SquirtlesAlgorithmStudyS8/issues/7"}