🖋️ 완전탐색 알고리즘 풀이

카펫

• 중앙에는 노란색
• 테두리 1줄은 갈색으로 칠해져 있는 격자 모양
• 카펫의 가로, 세로 구하기
  
  
• 카펫에서 갈색 격자의 수 brown
• 노란색 격자의 수 yellow
• 세로 길이 <= 가로 길이
• 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return

• 나의 코드

function solution(brown, yellow) {
    const answer = [];
    const sum = brown + yellow;
    
    // 노란색 격자 개수
    const yTotal = (col, row) => {
        return (col - 2) * (row - 2);
    }
    
    // 갈색 세로 최솟값 3부터 절반까지 탐색
    for (let h = 3; h <= (brown / 2); h++) {
        // 총 개수가 세로 격자 수로 나눠지면 
        if (sum % h === 0) {
            const w = sum / h;
            // 노란색 총 개수 구하기 (세로-2 & 가로-2)
            if (yTotal(h, w) === yellow) return [w, h];
        }
    }
    
    return answer;
}

피로도

• 일정 피로도를 사용해서 던전을 탐험
• 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"
• 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"
• 하루에 한 번씩 탐험할 수 있는 던전 여러개
• 한 유저가 오늘 이 던전들을 최대한 많이 탐험, 던전 수 구하기
  
  
• 유저의 현재 피로도 k
• 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons
• 유저가 탐험할수 있는 최대 던전 수를 return

• 나의 코드

function solution(k, dungeons) {
    let answer = -1;
    // DFS 활용한 백 트래킹을 위한 visited 함수 정의
    const visited = Array.from({length : dungeons.length}, () => true);
    
    const dfs = (fatigue, cnt) => {
        // 피로도 조건을 통과한 cnt 값으로 최대값 갱신
        answer = Math.max(cnt, answer);
      
        // dungeons 의 배열 완전 탐색
        for (let i = 0; i < visited.length; i++) {
            const [minF, consumeF] = dungeons[i];
            if (visited[i] && minF <= fatigue) {
                visited[i] = false;
                dfs(fatigue - consumeF, cnt+1);
                visited[i] = true;
            }
        }
    }
    
    dfs(k, 0);
    
    return answer;
}

전력망을 둘로 나누기

• n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결
• 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할
• 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추기
  
  
• 송전탑의 개수 n
• 전선 정보 wires
• 두 전력망이 가지고 있는 송전탑 개수의 최소 차이(절대값)를 return

• 나의 코드

function solution(n, wires) {
    let answer = 101;
  
    // 트리 정의
    let tree = Array.from(Array(n+1),()=>[])
    wires.map(([a,b])=>{
        tree[a].push(b);
        tree[b].push(a);
    });
    
    // 제외 노드외의 root 의 전력망
    const bfs = (root, splitNum) => {
        let count = 0;
        let visited = [];
        let queue = [root];
        visited[root] = true;

        while (queue.length) {
            const node = queue.pop();
            tree[node].forEach((v) => {
                if (v !== splitNum && !visited[v]) {
                    visited[node] = true;
                    queue.push(v);
                }
            })
            count++;
        }
        return count;
    }

    // [a, b] 로 각각의 전력망 최솟값 구하기
    wires.forEach(([a, b]) => {
        answer = Math.min(answer, Math.abs(bfs(a, b) - bfs(b, a)));
    })

    return answer;
}

• 더 좋은 풀이 (경로를 역추적하거나 재구성하는 데 유용)

function solution(n, wires) {

    // 트리 정의
    const tree = Array.from({ length: n }, () => []);
    for (const [a, b] of wires) {
        tree[a - 1].push(b - 1);
        tree[b - 1].push(a - 1);
    }

    // BFS 와 DP 초기화
    const visited = new Array(n).fill(-1);
    const queue = [0];
    const dp = new Array(n).fill(1);
    let answer = n;

    // BFS 를 통해 부모-자식 관계 기록 (BFS 순회)
    // 레벨별 순서로 트리의 각 노드를 방문하고
    // 방문한 노드와 해당 상위 노드를 추적하는 것
    for (let i = 0; i < queue.length; ++i) {
        const node = queue[i];
        for (const v of tree[node]) {
            // 방문한 노드 표시 및 상위 노드 추적
            if (v !== visited[node]) {
                visited[v] = node;
                queue.push(v);
            }
        }
    }

    // BFS 역순으로 리프노드부터 visited 기록 순대로 최소차이 계산
    // dp[v] - (n - dp[v]) => Math.abs(n - 2 * dp[v])
    // dp 상위 노드로 갈 때마다 +1
    // 루트 노드는 방문 안해도 돼서 -1
    while (queue.length - 1) {
        const v = queue.pop();
        dp[visited[v]] += dp[v];
        let diff = Math.abs(n - 2 * dp[v]);
        answer = Math.min(answer, diff);
    }

    return answer;
}

모음사전

• 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용
• 길이 5 이하의 모든 단어가 수록
• 주어진 단어가 사전에서 몇 번째 단어인지

첫 번째 단어는 "A"
그다음은 "AA"
마지막 단어는 "UUUUU"

• 단어 하나 word
• 이 단어가 사전에서 몇 번째 단어인지 return

• 풀이

function solution(word) {
  const result = [];
  const vowels = [..."AEIOU"];
    
  const dfs = (word, length) => {
    if (length === word.length) {
        result.push(word);
        return;
    }
    vowels.forEach((vowel) => {
        dfs(word + vowel, length);
    });
  };
    
  // 길이 1 ~ 5 의 모든 단어 구하기 (dfs)
  for (let len = 1; len <= 5; len++) dfs("", len);
  // 정렬 후 해당 idx 반환
  return result.sort().indexOf(word) + 1;
}