2022 01 31

2022-01-31

알고리즘 문제풀이 - Two Pointers, Sliding Window

• O(n^2) -> O(n)으로 줄여보자!!!

• Two Pointers가 필요한 이유?
  • Qs. 두 개의 배열을 오름차순으로 정렬해라
    • Sol1. 두 개의 배열을 합치고, Sorting으로 해결 -> O(nlogn)
    • Sol2. 두 개의 포인터를 통해, 순회하면서 비교로 해결 -> O(n)
  • n의 크기가 커질수록 O(nlogn)과 O(n)의 차이는 엄청 커진다!

• Sliding Window
  • O(n)으로 연속된 합을 구할 수 있음
    • index 기점으로 for문 돌아서 O(n^2)로 검사하지 말고!
  • 이전의 값을 저장해두는 공간을 꼭 마련해둘 것!

• 배열의 안에서 하나의 원소부터 몇 개까지 어떻게 하라
  • 이런 문제 조건 만나면 투 포인터, 슬라이딩 윈도우 고려해볼 것!

• 투 포인터 활용 시 주의사항
  • Array Out Of Bound 주의할 것
  • 확실한 순서를 세우고 들어갈 것
    • index를 더하고 array에 접근하는지, array에 접근하고 index를 더하는지!
  • 임시 저장소를 잘 활용할 것

• 투 포인터 문제 풀이 접근 방법
  1. lt, rt를 잡는다
  2. rt를 for문 순회하면서 하나씩 늘린다
  3. lt를 늘려줘야할 조건에 다다르면, while 문으로 lt를 따라잡는다
  4. 임시변수, 답 등을 철저히 기록해둔다!

JCF List의 구현체

• 참고: https://steady-coding.tistory.com/356
• ArrayList
  • 배열을 인스턴스 변수로 들고 있음
  • 따라서 접근에 O(1)

  • 원소를 add할 때 배열 용량을 넘어버리면 grow 함수를 호출하게 됨 (자동으로 배열의 사이즈 증가)

    • 기존의 용량의 1/2을 추가하여 용량을 키우는 걸 알 수 있음

          private void grow(int minCapacity) {
              // overflow-conscious code
              int oldCapacity = elementData.length;
              int newCapacity = oldCapacity + (oldCapacity >> 1);
              if (newCapacity - minCapacity < 0)
                  newCapacity = minCapacity;
              if (newCapacity - MAX_ARRAY_SIZE > 0)
                  newCapacity = hugeCapacity(minCapacity);
              // minCapacity is usually close to size, so this is a win:
              elementData = Arrays.copyOf(elementData, newCapacity);
          }
      

    • add(object)는 O(1), add(index, object)는 O(n)으로 동작함
      • Thread Unsafe. 여러 쓰레드가 접근하면 뇌절. Collections.synchronizedList(new ArrayList(...)) 사용 요망
      • 정리
    • 추가: add(object) - O(1), add(index, object) - O(n)
    • 삭제: remove() - O(1), remove(index) - O(n)
    • 탐색: contains(object) - O(n)
    • 반환: get() - O(1)

• LinkedList
  • 양방향 포인터 구조 링크드 리스트
  • 정리
    • 추가: add(object), add(index, object) - O(n) (작업은 O(1)인데, 노드 탐색까지가 O(n))
    • 삭제: remove(), remove(index) - O(n) (작업은 O(1)인데, 노드 탐색까지가 O(n))
    • 탐색: contains(object) - O(n)
    • 반환: get() - O(n)