1일차. DFS(깊이 우선 탐색)

[ollykingking]

관련 문제

소수 찾기

문제 1

• dfs를 이용하여 "135"가 주어진 경우 [135, 153, 315, 351, 513, 531] 를 리턴하는 함수 만들기

문제 2

• dfs를 이용하여 "135"가 주어진 경우 [1, 13, 135, 15, 153, 3, 31, 315, 35, 351, 5, 51, 513, 53, 531]을 리턴하는 함수 만들기

문제 3

• 문제 2에서 생성한 dfs에서 "115"가 주어진 경우 [1, 11, 115, 15, 151, 1, 11, 115, 15, 151, 5, 51, 511, 51, 511]를 리턴하였다면 중복을 제거하여라.

문제 4

• 문제3에서 만든 dfs함수를 사용해서 소수 찾기 문제 해결

참고) 소수 판별 함수

function isPrime(number) {
    if (number <= 1) return false; // 1 이하의 숫자는 소수가 아님
    if (number <= 3) return true; // 2와 3은 소수

    // 2부터 number의 제곱근까지의 수로 나누어 떨어지는지 확인
    for (let i = 2; i <= Math.sqrt(number); i++) {
        if (number % i === 0) {
            return false;
        }
    }
    return true;
}

답은 여기에 코멘트로 다는걸로해요.

[ollykingking]

문제 1.

function q1(number) {
  const result = [];

  function dfs(current, remaining) {
    if (remaining.length === 0) {
      result.push(Number(current));
      return;
    }

    for (let i = 0; i < remaining.length; i++) {
      const nextChar = remaining[i];
      const newCurrent = current + nextChar;
      const newRemaining = remaining.slice(0, i) + remaining.slice(i + 1); // i번째 숫자만 제거
      dfs(newCurrent, newRemaining);
    }
  }

  dfs('', number);
  return result;
}

문제 2.

function q2(number) {
  const result = [];

  function dfs(current, remaining) {
    if (current) { // 수가 있으면 다 넣음
      result.push(Number(current));
    }

    for (let i = 0; i < remaining.length; i++) {
      const nextChar = remaining[i];
      const newCurrent = current + nextChar;
      const newRemaining = remaining.slice(0, i) + remaining.slice(i + 1); // i번째 숫자만 제거
      dfs(newCurrent, newRemaining);
    }
  }

  dfs('', number);
  return result;
}

문제 3.

function q3(number) {
  const result = new Set(); // set 자료구조 사용

  function dfs(current, remaining) {
    if (current) {
      result.add(Number(current));
    }

    for (let i = 0; i < remaining.length; i++) {
      const nextChar = remaining[i];
      const newCurrent = current + nextChar;
      const newRemaining = remaining.slice(0, i) + remaining.slice(i + 1); // i번째 숫자만 제거
      dfs(newCurrent, newRemaining);
    }
  }

  dfs('', number);
  return Array.from(result);
}

문제 4.

function q3(number) {
  const result = new Set();

  function dfs(current, remaining) {
    if (current) {
      result.add(Number(current));
    }

    for (let i = 0; i < remaining.length; i++) {
      const nextChar = remaining[i];
      const newCurrent = current + nextChar;
      const newRemaining = remaining.slice(0, i) + remaining.slice(i + 1); // i번째 숫자만 제거
      dfs(newCurrent, newRemaining);
    }
  }

  dfs('', number);
  return Array.from(result);
}

function isPrime(number) {
    if (number <= 1) return false; // 1 이하의 숫자는 소수가 아님
    if (number <= 3) return true; // 2와 3은 소수

    // 2부터 number의 제곱근까지의 수로 나누어 떨어지는지 확인
    for (let i = 2; i <= Math.sqrt(number); i++) {
        if (number % i === 0) {
            return false;
        }
    }
    return true;
}

function solution(number) {
  const numberArray = q3(number);
  const primeNumbers = numberArray.filter((number) => isPrime(number));
  return primeNumbers.length;
}