알고리즘 개념 정리

투 포인터

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

예시

• 두 배열 합치기

  

  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]));

이분검색

개념 : 정렬된 배열의 중간값 비교 후 일치하지 않는 절반 버리기 + 반복

방법

1. 정렬된 배열을 가져온다.

2. 0번 인덱스 값을 lt, 마지막 인덱스 값을 rt로 저장한다.

3. lt와 rt 값을 더하고 2로 나눈 값과 중간 인덱스 값을 비교한다.

4. 비교 결과에 따라 lt와 rt를 변경한다.

   1. 중간 인덱스 값이 더 크다면 rt를 mid인덱스 값-1로 변경한다.

   2. 나눈 값이 더 크다면 lt를 mid 인덱스 값 + 1로 변경한다.

5. 반복해서 찾는다.

6. 끝!

예시문제

const solution = (target, arr) => {
  let answer;
  arr.sort((a, b) => a - b);
  let lt = 0;
  let rt = arr.length - 1;
  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (arr[mid] === target) {
      answer = mid + 1;
      break;
    } else if (arr[mid] > target) {
      rt = mid - 1;
    } else if (arr[mid] < target) {
      lt = mid + 1;
    }
  }
  return answer;
};

console.log(solution(32, [23, 87, 65, 12, 57, 32, 99, 81]));

재귀함수

개념 : 자기 자신을 참조하는 함수.

함수가 끝나지 않은 채로 계속 호출이 되기 때문에 콜스택이 쌓인다.
따라서 함수의 호출 뒤에 적힌 나머지 로직은 반대 순서로 실행된다.
ex) 내부 호출 전 로직 : fac(5)→fac(4)→fac(3)→fac(2)→fac(1)
내부 호출 뒤 로직 : fac(1)→fac(2)→fac(3)→fac(4)→fac(5)

예시문제

const solution = (num) => {
  function DFS(n) {
    if (n === 0) return;
    else {
      DFS(n - 1);
      console.log(n);
    }
  }

  DFS(num);
};

solution(3);

위의 console.log(n)을 DFS(n-1) 윗줄로 옮긴다면 3,2,1이 출력된다.