알고리즘 6일차

개발 log·2021년 8월 24일
BFS
0

알고리즘

목록 보기
5/11

DFS & BFS


재귀함수를 이용한 이진수 출력

  1. n = 0이면 멈추는 재귀함수 생성
  2. n을 2로 나눈 몫을 전달하는 재귀 작성
  3. 재귀 함수 스택이 쌓이다 종료구문을 만나면
  4. 스택에 쌓여있던 n을 2로 나눈 나머지를 tmp문자열에 추가
function solution(n) {
  let answer = 0,
    tmp = [];
  function DFS(n) {
    if (n === 0) return;
    else {
      DFS(parseInt(n / 2));
      tmp.push(n % 2);
    }
  }
  DFS(n);
  // 배열안의 원소들을 십진수처럼 바꾸는 구문
  for (let i = 0; i < tmp.length; i++) {
    answer = answer * 10 + tmp[i];
  }
  return answer;
}

이진트리 순회

  1. 전위순회 진행방향
    • 1 2 3 4 5 6 7
    • root에서 왼쪽 자식노드 끝까지 탐색 후
    • 끝에 도달했다면 오른쪽 자식노드에서 왼쪽 자식노드 끝까지 탐색 후
    • 이미 탐색한 부모로 올라가(탐색하지 않음) 오른쪽 자식노드를 보며 상승
  2. 중위순회 진행방향
    • 4 2 5 1 6 3 7
    • 왼쪽 노드 끝에서 시작
    • 부모노드를 보고 오른쪽 노드를 보고 없으면 부모노드로 이동
  3. 후위순회 진행방향
    • 4 5 2 6 7 3 1
    • 왼쪽 노드 끝에서 시작
    • 오른쪽 노드가 있는지 보고 그 안에 왼쪽 노드가 있다면 끝까지 이동
    • 왼쪽 노드를 모두 본 후 오른쪽 노드를 본다
    • 그리고 부모노드를 본다
let n = 1;

function solution(n) {
  let answer = "";
  function DFS(v) {
    if (v > 7) return;
    else {
      // 전위순회
      // answer += v + " ";

      DFS(v * 2);

      // 중위순회
      // answer += v + " ";

      DFS(v * 2 + 1);

      // 후위순회
      answer += v + " ";
    }
  }
  DFS(n);
  return answer;
}

부분집합 구하기(DFS)

  1. 깊이 L이 n이 될때 종료되는 재귀함수 생성
  2. 공집합이 아닌경우 tmp.length !== 0 answer에 tmp push
  3. tmp에 현재값을 추가한 경우와 그렇지 않은경우로 나누어 재귀
let n = 3;

function solution2(n) {
  let arr = Array.from({ length: n }, (v, i) => i + 1);
  let answer = [];
  let tmp = [];
  function DFS(L) {
    if (L === n) {
      if (tmp.length !== 0) answer.push(tmp.slice());
    } else {
      tmp.push(arr[L]);
      DFS(L + 1);
      tmp.pop();
      DFS(L + 1);
    }
  }
  DFS(0);
  return answer;
}

합이 같은 부분집합

  1. 부분집합을 뽑아내는 재귀생성
  2. 부분집합의 합을 받는 파라미터 sum
  3. sum이 total에서 sum을 뺀값과 같다면 true
let nums = [1, 3, 5, 6, 7, 10];

function solution(nums) {
  let answer = "NO",
    flag = false;
  let total = nums.reduce((a, b) => a + b, 0);
  let n = nums.length;
  function DFS(L, sum) {
    if (flag) return;
    if (L === n) {
      if (total - sum === sum) {
        answer = "YES";
        flag = true;
      }
    } else {
      DFS(L + 1, sum + nums[L]);
      DFS(L + 1, sum);
    }
  }
  DFS(0, 0);
  return answer;
}

바둑이 승차

  1. 컷엣지!
  2. 바둑이를 태우는 경우와 그렇지 않은 경우를 나누는 재귀 생성
  3. 컷 엣지를 위해 현재까지 지나간 바둑이들의 무게를 담는 tsum을 생성
  4. total에서 tsum을 뺐을때(남은 바둑이 무게)의 값과 sum의 합이 answer보다 작으면 return
let nums = [81, 58, 42, 33, 61];
let c = 259;

function solution(nums, c) {
  let answer = Number.MIN_SAFE_INTEGER;
  let total = nums.reduce((a, b) => a + b, 0);
  let n = nums.length;
  function DFS(L, sum, tsum) {
    // 컷 엣지 부분 1
    if (sum > c) return;
    // 앞으로 태울 바둑이들의 무게
    // 더이상 진행할 필요 없다
    if (sum + (total - tsum) < answer) return;
    if (L === n) {
      answer = Math.max(answer, sum);
    } else {
      DFS(L + 1, sum + nums[L], tsum + nums[L]);
      DFS(L + 1, sum, tsum + nums[L]);
    }
  }
  DFS(0, 0, 0);
  return answer;
}

최대점수 구하기(DFS)


let nums = [
  [15, 6],
  [30, 11],
  [23, 8],
  [14, 4],
  [10, 3],
  [20, 7],
];
let m = 25;

function solution(nums, m) {
  let answer = Number.MIN_SAFE_INTEGER;
  let n = nums.length;

  function DFS(L, sum, time) {
    if (time > m) return;
    if (L === n) {
      answer = Math.max(answer, sum);
    } else {
      DFS(L + 1, sum + nums[L][0], time + nums[L][1]);
      DFS(L + 1, sum, time);
    }
  }
  DFS(0, 0, 0);
  return answer;
}

중복순열 구하기

let n = 3;
let m = 3;

function solution(n, m) {
  let answer = [],
    tmp = [];

  function DFS(L) {
    if (L === m) {
      answer.push(tmp.slice());
    } else {
      for (let i = 1; i <= n; i++) {
        tmp.push(i);
        // 종료지점을 알기위해 씀
        DFS(L + 1);
        tmp.pop();
      }
    }
  }
  DFS(0);
  return answer;
}

순열 구하기


let nums = [3, 6, 9, 12];
let m = 2;

function solution(nums, m) {
  let answer = [],
    tmp = [];
  // 체크배열
  let ch = Array.from({ length: nums.length }, () => 0);

  function DFS(L) {
    if (L === nums.length) {
      answer.push(tmp.slice());
    } else {
      for (let i = 0; i < nums.length; i++) {
        if (ch[i] === 0) {
          ch[i] = 1;
          tmp.push(nums[i]);
          DFS(L + 1);
          tmp.pop();
          ch[i] = 0;
        }
      }
    }
  }
  DFS(0);
  return answer;
}

조합의 경우수(메모이제이션)

nCr

let n = 5;
let r = 3;

function solution(n, r) {
  let answer = 0;

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

메모이제이션

function solution2(n, r) {
  let answer = 0;
  let dy = Array.from(Array(6), () => Array(5).fill(0));

  function DFS(n, r) {
    if (dy[n][r] > 0) return dy[n][r];
    if (n === r || r === 0) return 1;
    else {
      return (dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
    }
  }
  answer = DFS(n, r);
  console.log(dy);
  return answer;
}

수열 추측하기


let n = 4;
let f = 16;

function solution(n, f) {
  let answer;
  let flag = false;

  let dy = Array.from(Array(11), () => Array(11).fill(0));
  let ch = Array.from({ length: n + 1 }, () => 0);

  let p = [],
    b = [];

  function comb(n, r) {
    if (dy[n][r] > 0) return dy[n][r];
    if (n === r || r === 0) return 1;
    else {
      return (dy[n][r] = comb(n - 1, r - 1) + comb(n - 1, r));
    }
  }

  function DFS(L, sum) {
    if (flag) return;
    if (L === n) {
      console.log(sum);
      if (sum === f) {
        answer = p.slice();
        flag = true;
      }
    } else {
      for (let i = 1; i <= n; i++) {
        if (ch[i] === 0) {
          ch[i] = 1;
          p.push(i);
          DFS(L + 1, sum + p[p.length - 1] * b[L]);
          ch[i] = 0;
          p.pop();
        }
      }
    }
  }

  b.push(1);
  for (let i = 1; i < n; i++) {
    b.push(comb(n - 1, i));
  }

  DFS(0, 0);
  return answer;
}

조합 구하기

let n = 4;
let m = 2;

function solution(n, m) {
  let answer = [];
  let tmp = [];

  function DFS(L, s) {
    if (L === m) {
      answer.push(tmp.slice());
    } else {
      for (let i = s; i <= n; i++) {
        tmp.push(i);
        DFS(L + 1, i + 1);
        tmp.pop();
      }
    }
  }
  DFS(0, 1);
  return answer;
}

수들의 조합

let nums = [2, 4, 5, 8, 12];
let m = 3;
let k = 6;

function solution2(nums, m, k) {
  let answer = 0;
  function DFS(L, s, sum) {
    if (L === m) {
      if (sum % k === 0) answer++;
    } else {
      for (let i = s; i < nums.length; i++) {
        DFS(L + 1, i + 1, sum + nums[i]);
      }
    }
  }
  DFS(0, 0, 0);
  return answer;
}

이진트리 레벨탐색

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

송아지 찾기

let s = 5;
let e = 14;

function solution2(s, e) {
  let answer;

  function BFS() {
    let ch = Array.from({ length: 10001 }, () => 0);
    let que = [];
    que.push(s);
    ch[s] = 1;
    let L = 0;
    while (que.length) {
      let len = que.length;
      // 레벨의 개수만큼 for문
      for (let i = 0; i < len; i++) {
        let x = que.shift();
        // 자식들을 조건에맞게 que에 push
        for (let nx of [x - 1, x + 1, x + 5]) {
          if (nx === e) return ++L;
          if (nx > 0 && nx < 10001 && ch[nx] === 0) {
            ch[nx] = 1;
            que.push(nx);
          }
        }
      }
      L++;
    }
  }
  answer = BFS();
  return answer;
}

미로의 최단거리 통로(BFS)

let board = [
  [0, 0, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1, 1, 0],
  [0, 0, 0, 1, 0, 0, 0],
  [1, 1, 0, 1, 0, 1, 1],
  [1, 1, 0, 1, 0, 0, 0],
  [1, 0, 0, 0, 1, 0, 0],
  [1, 0, 1, 0, 0, 0, 0],
];

function solution(board) {
  let dist = Array.from({ length: board.length }, () =>
    Array.from({ length: board.length }, () => 0)
  );
  let dx = [-1, 0, 1, 0];
  let dy = [0, 1, 0, -1];
  function BFS(x, y) {
    let que = [];
    que.push([x, y]);
    while (que.length) {
      let curr = que.shift();
      for (let j = 0; j < 4; j++) {
        let nx = curr[0] + dx[j];
        let ny = curr[1] + dy[j];
        if (
          nx >= 0 &&
          nx < board.length &&
          ny >= 0 &&
          ny < board.length &&
          board[nx][ny] === 0
        ) {
          board[nx][ny] = 1;
          dist[nx][ny] = dist[curr[0]][curr[1]] + 1;
          que.push([nx, ny]);
        }
      }
    }
  }
  BFS(0, 0);
  if (dist[board.length - 1][board.length - 1] === 0) return -1;
  return dist[board.length - 1][board.length - 1];
}
profile
개발 log
프론트엔드 개발자
이전 포스트

알고리즘 7일차

다음 포스트

알고리즘 5일차

0개의 댓글