알고리즘 개념 정리

투 포인터

리스트에 순차적으로 접근해야할 때 두 개의 점 위치를 기록하며 처리하는 알고리즘.

예시

• 두 배열 합치기

  

  const solution = (arr1, arr2) => {
    let answer = [];
    let p1 = 0;
    let p2 = 0;
    while (p1 < arr1.length && p2 < arr2.length) {
      if (arr1[p1] < arr2[p2]) {
        answer.push(arr1[p2]);
        p1++;
      } else {
        answer.push(arr2[p2]);
        p2++;
      }
    }
    while (p1 < arr1.length) answer.push(arr1[p1++]);
    while (p2 < arr2.length) answer.push(arr2[p2++]);
  
    return answer;
  };
  
  console.log(solution([1, 3, 5], [2, 3, 6, 7, 9]));

• 

슬라이딩 윈도우

해쉬

스택

큐

버블정렬

개념 : 이중 포문을 통해 한 바퀴마다 가장 큰 값을 맨 뒤로 밀어주기

방법

1. 이중 포문을 만들어준다.

   // 두 개씩 비교하기 때문에모든 index를 돌 필요 없이 전체 길이-1 만큼 돌면 됨 
   for (let i = 0; i < arr.length - 1; i++) {
   // 가장 큰 값이 하나씩 확정되기 때문에 i만큼 빼고 순회하면 된다.
       for (let j = 0; j < arr.length - 1 - i; j++) {
            logic
       }
   }

2. 내부에서 index를 돌아가며 두 개의 값을 비교하고 앞의 값이 뒤의 값보다 크다면 서로의 자리를 바꿔준다.

   [bubble[j], bubble[j + 1]] = [bubble[j + 1], bubble[j]];

3. 끝!

예시 문제

const solution = (arr) => {
  let bubble = arr;
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [bubble[j], bubble[j + 1]] = [bubble[j + 1], bubble[j]];
      }
    }
  }
  return bubble;
};

console.log(solution([13, 5, 11, 7, 23, 15]));

삽입정렬

개념 : 뒤에서 앞으로 탐색을 통해 값 비교를 하고 tmp를 삽입해주기

방법

1. 이중 포문을 만들어 준다.

   for (let i = 0; i < arr.length; i++) {
     for (j = i - 1; j >= 0; j--) {
       logic
     }
   }

2. tmp 에 arr[i]을 임시 값으로 넣어준다.

3. j를 돌리며 tmp 와 arr[j] 의 값 비교를 해준다.

4. 비교 결과에 따라 arr을 수정해준다.

   1. tmp < arr[j] 일 경우 arr[j+1] = arr[j]

   2. tmp >= arr[j] 일 경우 arr[j+1] = tmp가 된다.

5. 끝!

예시문제

const solution = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    let tmp = arr[i],
      j;
    for (j = i - 1; j >= 0; j--) {
      if (arr[j] > tmp) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }
    arr[j + 1] = tmp;
  }
  return arr;
};

console.log(solution([11, 7, 5, 6, 10, 9]));