[ TIL - PGS ] 99클럽 코테 스터디 29일차 TIL + 오늘의 학습 가이드

💡 오늘의 학습 키워드

• 이분탐색

 

✅ 오늘 공부한 내용

• 오늘의 리트코드 문제! 300번 Longest Increasing Subsequence

 

👀 오늘의 회고

🤣 오늘의 문제점

• 초반에 무슨 소리인지 못알아 듣고..
• 어떤 방식을 써야할지 모르겠어서 gpt 찬스를 사용했다.
• 2가지 방법이 존재하는데 Binary Search(이분탐색)과 DP를 사용하는 방법이었다.

 

🔥 어떤 시도를 했는가?

• 일단 문제의 뜻이 최장 증가 수열이라는 이름을 가진 문제였다.
• 문제는 그냥 integer 형태의 배열인 nums가 주어지고, 가장 긴 strictly한 증가 수열의 길이를 return 하라란 의미였다.
  • 여기서 strictly가 애매해서 gpt한테 의역을 부탁했었는데 직역으로 하길래 해석했을 때 가장 가까운 뜻은 "절대적으로" 또는 "정확히"라는 뜻으로 해석할 수 있을 것 같다.
• 그래서 문제를 분석해 본다면 연속되게 규칙적으로 증가하는 수들을 구하는 것이다.
• 예제 1번을 살펴 보면 배열이 [10, 9, 2, 5, 3, 7, 101, 18]이 있다면 제일 긴 걸 구해야 하기 때문에
  • 여러 경우의 수가 나오는데
    • 10, 101
    • 9, 101
    • 2, 5, 7, 101
    • 5, 7, 101
    • 3, 7, 101
    • 7, 101
    • 101
    • 18
  • 이기 때문에 제일 긴 배열의 길이가 4가 된다.
• 이걸 구하는 알고리즘을 짜는 것이다..!
• 아래는 solution을 참고한 답안이다.

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> arr = new ArrayList<>();

        for(int n : nums){
            // 배열이 비어있다면 추가하기
            // arr 배열 마지막 값이 nums 값 보다 작다면 추가하기
            if(arr.isEmpty() || arr.get(arr.size() - 1) < n){
                arr.add(n);
            } else {
                int ind = binarySearch(arr, n);
                arr.set(ind, n);
            }
        }

        return arr.size();
    }

    private int binarySearch(List<Integer> arr, int target){
        int left = 0;
        int right = arr.size() - 1;

        while(left <= right){
            int mid = (left + right) / 2;
            if(arr.get(mid) == target)  {
                return mid;
            } else if (arr.get(mid) > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

 

👏 무엇을 새로 알았는가?

• binary search와 dp의 콜라보..

 

👩‍💻 내일은 무엇을 학습할 것인가?

• 항해 99 문제 풀기
• 원티드 인턴쉽 OT 들으러 가기