TIL 221221 알고리즘 : 다중 포인터 패턴

🎆 오늘 한 것

• deep dive 27~29장 읽기
• 알고리즘 강의 다중 포인터까지
• 리액트 강의(경로 매개 변수 추출하기)
• 백준 1문제 풀이

🙄 오늘 하려고 했는데 못한 것

• 수업 정리 및 복습(Sass 기초)

✨ Multiple Pointers

인덱스나 위치에 해당하는 포인터/값을 만든 다음, 특정 조건에 따라 중간 지점부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 패턴

🎇 예제 1

📌 Q. 정렬된 배열에서 합이 0인 첫번째 쌍 구하기

👇 예시

console.log(sumZero([-4, -3, -2, -1, 0, 1, 2, 5])); // [ -2, 2 ]
console.log(sumZero([-3, -2, -1, 0, 1, 2, 3])); // [ -3, 3 ]
console.log(sumZero([-2, 0, 1, 3])); // undefined
console.log(sumZero([1, 2, 3])); // undefined

📌 A1. 순진한 풀이 방법(?)

function sumZero(arr){
    for(let i = 0; i < arr.length; i++){
        for(let j = i+1; j < arr.length; j++){
            if(arr[i] + arr[j] === 0){
                return [arr[i], arr[j]];
            }
        }
    }
}


sumZero([-4,-3,-2,-1,0,1,2,5])

단순하게 이중for문을 돌리면 끝

시간 복잡도 O(n^2)

📌 A2. 리팩토링한 풀이

const sumZero = (arr) => {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    let sum = arr[left] + arr[right];
    if (sum === 0) {
      return [arr[left], arr[right]];
    } else if (sum > 0) {
      right--;
    } else {
      left++;
    }
  }
};

console.log(sumZero([-4, -3, -2, -1, 0, 1, 2, 5])); // [ -2, 2 ]
console.log(sumZero([-3, -2, -1, 0, 1, 2, 3])); // [ -3, 3 ]
console.log(sumZero([-2, 0, 1, 3])); // undefined
console.log(sumZero([1, 2, 3])); // undefined

1. 왼쪽, 오른쪽 좌표 역할을 할 변수 정의
2. 왼쪽의 좌표가 오른쪽의 좌표보다 작은 동안 반복을 돌리겠음(while)
   3-1. 왼쪽 좌표에 해당하는 값과 오른쪽 좌표에 해당하는 값을 합쳤을 때 0이 나오면 좌표 리턴 후 반복문 종료
   3-2. 합쳤을 때 합이 0보다 크면 오른쪽 좌표를 한 칸 이동(right--)
   3-3. 합이 0보다 작으면 왼쪽 좌표를 한 칸 이동(left++)
3. 해당하는 값을 못 찾고 반복문이 끝나면 undefined 반환

시간 복잡도 O(N)

🎇 예제 2

📌 Q. 정렬된 배열, 고유한 숫자 개수 세기

👇 예시

console.log(countUniqueValues([1, 2, 2, 5, 7, 7, 99])); // 5
console.log(countUniqueValues([1, 1, 1, 1, 1, 2])); // 2

📌 풀이

function countUniqueValues(arr) {
  if (arr.length === 0) return 0;
  var i = 0;
  for (var j = 1; j < arr.length; j++) {
    if (arr[i] !== arr[j]) {
      // 다른 값을 만나면
      i++;
      // arr[i]를 한 칸 옮기고
      arr[i] = arr[j];
      // 그 인덱스의 값을 다른 값으로 바꿔줌
      // 결과적으로 안 겹치는 숫자 1개씩 순서대로 정렬이 됨
    }
  }
  return i + 1;
}
console.log(countUniqueValues([1, 2, 2, 5, 7, 7, 99])); // 5
console.log(countUniqueValues([1, 1, 1, 1, 1, 2])); // 2

시간 복잡도 O(N)

🎆 내일 할 것

• sass 공부
• 알고리즘 강의 분할과 정복 패턴
• 리액트 강의 최대한
• 백준 1문제 풀이
• deep dive 정규표현식 읽기

📌 언젠가 해야되는 todo

• preload / modulepreload / prefetch 공부... 언제하지?
• deep dive 19장 프로토 타입
• deep dive 25장 클래스
• 테일윈드 다크모드 공부
• 사이트 하나 잡고 리액트(Sass나 tailwind)로 클론 코딩(+다크모드까지)

📚 이번 주 개인 목표

• 리액트 SPA 섹션 보기
• 알고리즘 강의 문제 해결, 시간 남으면 선택 어쩌고 문제 풀어보기
• 매일 백준이나 프로그래머스 알고리즘 풀이 1개
• deep dive 27장 배열 ✅
• deep dive 28장 number ✅
• deep dive 29장 Math ✅
• 포폴 페이지나 포폴에 넣을 개인 프로젝트에 대한 고민... ✅

📝 오늘의 일기

내일부터 일요일까지 수업 없다...연휴(?)를 잘 활용해야지