알고리즘 개념 정리

강석우's avatar
강석우
Nov 11, 2024
알고리즘 개념 정리
Contents
투 포인터슬라이딩 윈도우해쉬스택큐버블정렬삽입정렬이분검색재귀함수이진트리순회 ( DFS : 깊이우선탐색 )순열 ( DFS )조합 ( DFS )그래프와 인접행렬그래프와 인접리스트넓이우선탐색 (BFS)

투 포인터

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

예시

  • 두 배열 합치기

    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를 삽입해주기

개념 사진
출처 : https://withhamit.tistory.com/172

방법

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

재귀함수

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

재귀함수 스택 예시
출처 : https://catsbi.oopy.io/dbcc8c79-4600-4655-b2e2-b76eb7309e60

함수가 끝나지 않은 채로 계속 호출이 되기 때문에 콜스택이 쌓인다.
따라서 함수의 호출 뒤에 적힌 나머지 로직은 반대 순서로 실행된다.
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이 출력된다.

이진트리순회 ( DFS : 깊이우선탐색 )

개념 : 트리 형태의 구조를 재귀함수를 통해 순차적으로 탐색한다.

이진트리

예시코드

const solution = (v) => {
  let answer;
  function DFS(v) {
    if (v > 7) return;
    else {
      console.log(v); // 전위 순회
      DFS(v * 2);
      //   console.log(v); // 중위 순회
      DFS(v * 2 + 1);
      //   console.log(v); // 후위 순회
    }
  }

  DFS(v);
  return answer;
};

순열 ( DFS )

위와 같은 문제가 나오며 순열을 구해야 한다면 공식처럼 외우고 아래의 공식을 쓰자.

const solution = (num, arr) => {
  let answer = [];
  let length = arr.length;
  let ch = Array.from({ length: length }, () => 0);
  let tmp = Array.from({ length: num });
  function DFS(n) {
    if (n === num) {
      answer.push(tmp.slice());
    } else {
      for (let i = 0; i < length; i++) {
        if (ch[i] === 0) {
          ch[i] = 1;
          tmp[n] = arr[i];
          DFS(n + 1);
          ch[i] = 0;
        }
      }
    }
  }

  DFS(0);
  return answer;
};

조합 ( DFS )

조합

개념 : 재귀를 통해 위의 공식을 구현한다.

문제

조합 문제

예시코드

const solution = (n, r) => {
  function DFS(n, r) {
    if (r === 0 || n === r) {
      return 1;
    } else {
      return DFS(n - 1, r - 1) + DFS(n - 1, r);
    }
  }
  return DFS(n, r);
};

메모이제이션을 통한 업그레이드

dy라는 배열을 만들어 값을 기억해두고 같은 계산이 나오면 계산하지 않고 꺼내 쓴다.

const solution = (n, r) => {
  let dy = Array.from(Array(35), () => Array(35).fill(0));
  function DFS(n, r) {
    if (dy[n][r] > 0) return dy[n][r];
    if (r === 0 || n === r) {
      return 1;
    } else {
      return (dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
    }
  }
  return DFS(n, r);
};

그래프와 인접행렬

Graph(V,E) : V = 꼭지점, E = 선

  • 그래프에 해당하는 0으로 이루어진 배열을 만든 뒤 배열에 값을 넣어주며 인접행렬을 만든다.

  • 행 기준으로 계산을 하며 꼭지점이 어떤 꼭지점과 연결되어있는지 확인한다.

1. 무방향 그래프

무방향 그래프

양 방향으로 전환이 가능하기 때문에 아래와 같은 인접 행렬이 만들어진다.

꼭지점

1

2

3

4

5

1

0

1

1

0

0

2

1

0

0

1

1

3

1

0

0

1

0

4

0

1

1

0

0

5

0

1

0

0

0

2. 방향 그래프

방향그래프

한쪽 방향으로 전환이 가능하기 때문에 아래와 같은 인접 행렬이 만들어진다.

꼭지점

1

2

3

4

5

1

0

1

1

0

0

2

0

0

0

0

1

3

0

0

0

1

0

4

0

1

0

0

0

5

0

0

0

0

0

3. 가중치 방향그래프

가중치 방향 그래프

1 대신 가중치에 해당 하는 값을 행렬에 넣어준다.

꼭지점

1

2

3

4

5

1

0

2

4

0

0

2

0

0

0

0

5

3

0

0

0

5

0

4

0

2

0

0

0

5

0

0

0

0

0

그래프와 인접리스트

인접리스트

인접 행렬을 사용해 알고리즘을 풀게 되면 꼭지점이 10000개 와 같이 많게 되면 for문을 매번 10000번 돌려야 한다. 이는 매우 비효율적이므로 필요한 만큼만 for문을 돌리면 된다.

꼭지점\배열길이

0

1

2

3

4

5

1

2

3

4

2

3

5

3

4

4

2

5

5

위의 표와 같이 행에 꼭지점을 놓고 연결되는 꼭지점 자체를 인수로 넣어준다.
그리고 각 행의 배열 길이만큼 for문을 돌리면 된다.

문제

인접행렬 풀이

const solution = (num, arr) => {
  let answer = 0;
  let graph = Array.from(Array(num + 1), () => Array(num + 1).fill(0));
  let ch = Array.from({ length: num + 1 }, () => 0);
  let path = [];
  for (let [a, b] of arr) {
    graph[a][b] = 1;
  }
  function DFS(v) {
    if (v === num) {
      answer++;
      console.log(path);
    } else {
      for (let i = 1; i <= num; i++) {
        if (graph[v][i] === 1 && ch[i] === 0) {
          ch[i] = 1;
          path.push(i);
          DFS(i);
          ch[i] = 0;
          path.pop();
        }
      }
    }
  }
  path.push(1);
  ch[1] = 1;
  DFS(1);
  return answer;
};

console.log(
  solution(5, [
    [1, 2],
    [1, 3],
    [1, 4],
    [2, 1],
    [2, 3],
    [2, 5],
    [3, 4],
    [4, 2],
    [4, 5],
  ])
);

인접리스트 풀이

const solution = (n, arr) => {
  let answer = 0;
  let graph = Array.from(Array(n + 1), () => Array());
  let ch = Array.from({ length: n + 1 }, () => 0);

  for (let [a, b] of arr) {
    graph[a].push(b);
  }

  function DFS(v) {
    if (v === n) answer++;
    else {
      for (let i = 0; i < graph[v].length; i++) {
        if (ch[graph[v][i]] === 0) {
          ch[graph[v][i]] = 1;
          DFS(graph[v][i]);
          ch[graph[v][i]] = 0;
        }
      }
    }
  }

  ch[1] = 1;
  DFS(1);
  return answer;
};

console.log(
  solution(5, [
    [1, 2],
    [1, 3],
    [1, 4],
    [2, 1],
    [2, 3],
    [2, 5],
    [3, 4],
    [4, 2],
    [4, 5],
  ])
);

넓이우선탐색 (BFS)

BFS

최단거리를 찾을 때 사용되는 알고리즘.
각 계층 별로 한번에 찾는다.
→ 1번에서 2,3 → 2번에서 4,5 3번에서 6,7 이렇게 단계별로 찾는다.

문제

const solution = () => {
  let answer = "";
  let queue = [];
  queue.push(1);
  while (queue.length) {
    let v = queue.shift();
    answer += v + " ";
    for (let nv of [2 * v, 2 * v + 1]) {
      if (nv > 7) continue;
      queue.push(nv);
    }
  }
  return answer;
};

console.log(solution());

Share article

More articles

See more posts

함수형 프로그래밍 4주차

October 26, 2024
함수형 프로그래밍 4주차

함수형 프로그래밍 2주차

October 7, 2024
함수형 프로그래밍 2주차

석우의 개발블로그

RSS·Powered by Inblog