문제 설명 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예 prices return [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 입출력 예 설명 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다. 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다. 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

1.제일 기억할 풀이 - stack

function solution(prices) {
  const answer = new Array(prices.length).fill(0);
  const stack = [];
  let length = prices.length;

  for(let i = 0; i < length; i++) {
    while(stack.length && prices[i] < prices[stack[stack.length - 1]]) {
      let temp = stack.pop();
      answer[temp] = i - temp;
    }
    stack.push(i);
    console.log(stack,'stack')
  }

  while(stack.length) {
    let temp = stack.pop();
    console.log(`temp:${temp} =>${length-temp - 1}`)
    answer[temp] = length - temp - 1;
  }

  return answer;
}

// 스택활용(2)
function solution(prices) {
   const n=prices.length
   const answer = new Array(n).fill(0);
   const stack =[]; // [인덱스, 가격] 저장

   for (let i=0; i<n; i++){
       // 현재 가격보다 높은 이전 가격들 처리
       while (stack.length >0 && stack[stack.length-1][1] >prices[i]){
           console.log(stack[stack.length-1][1],'stack[stack.length-1][1]')
           console.log(stack[0][1],'stack[0][1]')
           console.log(prices[i],'prices[i]')
           const [prevIndex, prevPrice] = stack.pop();

           answer[prevIndex] = i-prevIndex
       }
       stack.push([i,prices[i]]) // 인덱스,값
       console.log(stack)
   }
    // 스택에 남은 항목들 처리 (끝까지 떨어지지 않은 경우)
    while (stack.length > 0) {
        const [index, price] = stack.pop();
        answer[index] = n-1-index;
    }
    console.log(answer,'answer')
    return answer;
}

기억할것

스택 = 아직 가격이 떨어지지 않은 시점들 for문 = 실시간으로 가격 하락 감지 마지막 while문 = 끝까지 안 떨어진 것들 정리

2.구현

function solution(prices) {
   return prices.map((currentPrice,i) => {
       let count = 0;
       // 현재 시점부터 끝까지 확인
       for (let j=i+1; j<prices.length; j++){
           count++;
           // 가격이 떨어지면 즉시 종료
           if (currentPrice > prices[j]){
               break;
           }
       }
       return count;
   })
}

3.처음풀이

function solution(prices) {
    const answer =[]
    prices.forEach((currentPrice,i)=> {
        let notFallTime = 1;
        for(let index =i+1; index<prices.length; index++){
           if(index===prices.length-1){return answer.push(notFallTime)}
           if(currentPrice <= prices[index]){
              notFallTime++
           }
           else{return answer.push(notFallTime)}
        }
    })
    answer.push(0)
    return answer;
}

3번 보충-forEach: 별도의 콜백함수 스코프

이유: forEach의 콜백은 독립적인 함수이므로 return이 그 콜백만 종료

// for문: 같은 함수 스코프 내
function test1() {
    for(let i = 0; i < 3; i++) {
        if(i === 1) return "함수 종료"; // 전체 함수 종료
    }
    return "완료"; // 실행되지 않음
}

// forEach: 별도의 콜백 함수 스코프
function test2() {
    [0,1,2].forEach(i => {
        if(i === 1) return; // 콜백만 종료
    });
    return "완료"; // 실행됨! ✅
}

각 상황에서 return의 의미

상황별 올바른 제어

// ❌ forEach에서 전체 중단 시도
arr.forEach(item => {
    if(condition) return; // 현재만 skip, 전체는 계속
});

// ✅ 전체 중단이 필요하면
// 방법 1: for...of 사용
for(const item of arr) {
    if(condition) break; // 전체 중단
}

// 방법 2: some() 사용  
arr.some(item => {
    if(condition) return true; // 전체 중단
    return false; // 계속
});

// 방법 3: try-catch (비추천)
try {
    arr.forEach(item => {
        if(condition) throw new Error();
    });
} catch(e) {}

forEacn -> return 대신 continue

문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자연수입니다. 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

function solution(progresses, speeds) {   
    let delayDay = Math.ceil((100-progresses[0]) / speeds[0])
    let count = 1
    let answer = []
    for (let i=1; i<progresses.length; i++){
        const currentDay =Math.ceil((100-progresses[i])/speeds[i])
        console.log(`i:${i},현재 값:${progresses[i]} /기준${delayDay}-현재${currentDay}, `)

        if(delayDay >= currentDay){
            console.log('현재날이 배포날에 포함')
            count ++ 
        }
        else{
            console.log('포함안됨. 따라서 현재 count를 push하고 다음값 계산필요')
            answer.push(count)
            console.log(answer,'----answer')
            delayDay = currentDay
            count =1
        }
    }
    console.log(`마지막그룹값 count:${count}`)
    answer.push(count)
    return answer
}

기억할 것

• for loop 하나로 해결하면 메모리 효율성O(1), 시간복잡도 O(n)
  • 따로 배열생성후 map+for는 O(n), 시간복잡도 O(2n)

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 512 MB 104194 59893 50113 57.003% 문제 요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const stdin = [];

rl.on('line', (line) => {
  stdin.push(line.trim());
});

rl.on('close', () => {
  const [N, K] = stdin[0].split(' ').map(Number);
  // 선입선출(FIFO)
  const q = Array.from({length:N}, (_,i)=> i+1);
  const answer = [];
  let currentIndex = 0;
  while(q.length >0){
    // K번째 사람을 N명 사람이 모두 제거될때까지 반복
    // 제거되는 순서
    for (let i=0; i<K; i++){
      // 가장 앞을 빼서 뒤에 넣어줌 
      const move = q.shift()
      q.push(move);
      // console.log(`move: ${move} - q: ${q}`)
    }
    // 제거할 K가 가장 마지막에 가서 정답배열에 추가 
    const removeVal = q.pop()
    answer.push(removeVal);
    // console.log(`removeVal: ${removeVal} - answer: ${answer}`)
  }
console.log('<' + answer.join(', ') + '>');
})

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 입출력 예 triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30

풀이

i=0 인덱스부터 시작할 때, dp[현재행][열] 접근가능한 열은 현재 인덱스와 [i][i+1] 접근가능.

1. Bottom-Up

테스트케이스 1개에서 시간초과 발생..!

이유는 ... 시간복잡도: O(n²) 추가 공간복잡도: O(n²) 배열 복사에 따른 추가 오버헤드 발생 모든 위치를 순회해야 함

2.Top-Down (메모이제이션 방식)

function solution(triangle) {
    const memo = Array.from({ length: triangle.length }, 
        (_, i) => new Array(i + 1).fill(-1));

    function dfs(row, col) {
        if (row === triangle.length - 1) return triangle[row][col];
        if (memo[row][col] !== -1) return memo[row][col];

        memo[row][col] = triangle[row][col] + 
            Math.max(dfs(row + 1, col), dfs(row + 1, col + 1));
        return memo[row][col];
    }

    return dfs(0, 0);
}

성능 개선 핵심 포인트

메모리 접근 패턴: 연속된 메모리 접근이 캐시 효율성 향상 불필요한 메모리 할당 제거

데이터 구조 선택: 1차원 배열 사용으로 메모리 효율성 향상 불필요한 차원 제거

연산 최적화: 중복 연산 제거 불필요한 복사 연산 제거 결론적으로, Top-Down 방식이 더 빠른 이유는:

필요한 경로만 계산 메모이제이션으로 중복 계산 즉시 방지 재귀 호출의 오버헤드가 배열 복사 오버헤드보다 작음

문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다. 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다. 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다. 연결할 수 없는 섬은 주어지지 않습니다. 입출력 예

n costs return 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4

풀이

[섬1,섬2,섬1과 섬2를 연결할 때 드는 비용]
최소의 비용으로 모든 섬이 서로 통행 가능하도록 return 최소 비용 
최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 대표적인 문제

1.문제 해결 접근 방법

• Kruskal 알고리즘 사용

모든 간선을 비용 기준으로 오름차순 정렬 Union-Find 자료구조를 사용하여 사이클 형성 방지 가장 낮은 비용의 간선부터 선택하여 MST 구성

• Union-Find 구현

각 섬의 부모를 저장하는 배열 필요 Find 연산: 특정 섬의 최상위 부모를 찾음 Union 연산: 두 섬을 하나의 집합으로 합침

2. 코드

function solution(n, costs) {
    // 비용을 기준으로 오름차순 정렬(가장 적은 비용의 다리부터 선택하기 위함
    costs.sort((a, b) => a[2] - b[2]);

    // 부모 배열 초기화 (처음에는 자기 자신이 부모)
    // Union-Find 연산을 위한 기본 설정
    const parent = Array.from({ length: n }, (_, i) => i);

    // Find 연산: 경로 압축을 통한 최적화
    // 특정 섬의 최상위 부모를 찾는 연산
    // 경로 압축기법 사용으로 성능 최적화
    // 재귀적으로 부모를 찾으며 경로 압축
    function find(x) {
        if (parent[x] === x) return x;
        return parent[x] = find(parent[x]); // 경로 압축
    }

    // Union 연산
    // 두 섬을 하나의 집합으로 합치는 연산
    // 사이클 형성 여부 확인
    // 이미 같은 집합에 속한 경우 false 반환
    function union(a, b) {
        const rootA = find(a);
        const rootB = find(b);

        if (rootA !== rootB) {
            parent[rootB] = rootA;
            return true;  // 연결 성공
        }
        return false;  // 이미 연결됨
    }

    let totalCost = 0;  // 총 건설 비용
    let bridges = 0;    // 연결된 다리 수

    // Kruskal 알고리즘 구현
    // 정렬된 순서대로 다리 건설 시도 
    // n-1개의 다리가 건설되면 종료 (MST:Minimum Spanning Tree) 완성
    for (const [island1, island2, cost] of costs) {
        // 사이클을 형성하지 않는 경우에만 다리를 건설
        if (union(island1, island2)) {
            totalCost += cost;
            bridges++;

            // 모든 섬이 연결되었는지 확인
            if (bridges === n - 1) break;
        }
    }

    return totalCost;
}

3. 시간 복잡도

• 정렬: O(ElogE) (E는 간선의 수)
• Union-Find연산 : O(a(N)) (a는 애커만 함수의 역함수로, 실질적으로 상수시간
• 전체 시간 복잡도 : O(ElogE) 이 알고리즘은 주어진 섬들을 최소 비용으로 연결하는 최적의 해를 보장합니다. 모든 섬이 연결되었는지 확인하면서, 사이클 형성을 방지하여 최소신장 트리를 구성합니다.

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 n vertex return 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3

풀이

가장 먼 노드의 최소 거리를 구하라 => BFS 문제 BFS 를 푸는 방법 : 힙

DFS vs BFS 선택의 문제

이전 코드는 DFS를 사용하고 있는데, 이 문제는 "최단 경로"를 찾는 문제이므로 BFS를 사용해야 했습니다. DFS는 깊이 우선 탐색이라 한 경로를 끝까지 탐색하기 때문에 최단 경로를 보장하지 않습니다. BFS는 너비 우선 탐색이라 가까운 노드부터 탐색하므로 자연스럽게 최단 경로를 찾을 수 있습니다.

거리 측정 방식 현재 코드는 단순히 방문한 노드의 수를 세고 있습니다(count 변수 사용). 각 노드까지의 실제 거리(간선의 개수)를 저장하지 않고 있습니다. 최단 거리를 저장하는 배열이 필요합니다.

코드의 핵심 내용

1. BFS를 사용하여 각 노드까지의 최단 거리를 계산합니다.
2. 거리 배열을 사용하여 각 노드까지의 최단 거리를 저장합니다.
3. 마지막으로 최대 거리를 가진 노드들의 개수를 세어 반환합니다.

이렇게 하면 1번 노드로부터 가장 멀리 떨어진 노드들의 정확한 개수를 구할 수 있습니다.

function solution(n, edge) {
    // 그래프 생성
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [v1, v2] of edge) {
        graph[v1].push(v2);
        graph[v2].push(v1);
    }

    // 거리를 저장할 배열: -1은 미방문을 의미
    const distance = Array(n + 1).fill(-1);
    distance[1] = 0; // 시작점인 1번 노드의 거리는 0

    // BFS를 위한 큐 생성 및 시작점 추가
    const queue = [1];

    // BFS 수행
    while (queue.length > 0) {
        const current = queue.shift();

        // 현재 노드의 이웃들을 확인
        for (const next of graph[current]) {
            // 미방문 노드인 경우
            if (distance[next] === -1) {
                distance[next] = distance[current] + 1; // 거리 갱신
                queue.push(next);
            }
        }
    }

    // 최대 거리 찾기
    const maxDistance = Math.max(...distance.slice(1));

    // 최대 거리를 가진 노드의 개수 반환
    return distance.filter(d => d === maxDistance).length;
}

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다. computer[i][i]는 항상 1입니다. 입출력 예 n computers return 3 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 2 3 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] 1 입출력 예 설명 예제 #1 아래와 같이 2개의 네트워크가 있습니다.

예제 #2 아래와 같이 1개의 네트워크가 있습니다.

풀이

function solution(n, computers) {
    const visited = Array(n).fill(false); // 방문한 컴퓨터를 기록하는 배열
    let networkCount = 0; // 네트워크 개수

    // DFS 함수 정의
    function dfs(current) {
        visited[current] = true; // 현재 컴퓨터를 방문 처리
        for (let i = 0; i < n; i++) {
            // 연결된 컴퓨터이면서 방문하지 않은 경우
            if (computers[current][i] === 1 && !visited[i]) {
                dfs(i); // 다음 컴퓨터로 DFS 재귀 호출
            }
        }
    }

    // 모든 컴퓨터를 탐색
    for (let i = 0; i < n; i++) {
        if (!visited[i]) { // 방문하지 않은 컴퓨터라면
            dfs(i); // DFS 호출
            networkCount++; // 하나의 네트워크가 완성됨
        }
    }

    return networkCount; // 네트워크 개수 반환
}

기본접근

변수 초기화: visited: 각 컴퓨터가 방문되었는지를 기록하는 배열입니다. 초기값은 모두 false입니다. networkCount: 발견된 네트워크의 개수를 세기 위한 변수입니다. DFS 함수: dfs(current): 현재 컴퓨터를 인자로 받아 해당 컴퓨터를 방문 처리하고, 연결된 모든 컴퓨터를 재귀적으로 탐색합니다. for 루프를 통해 모든 컴퓨터를 확인하고, 연결된 컴퓨터이면서 아직 방문하지 않은 컴퓨터에 대해서 DFS를 재귀 호출합니다. 전체 탐색: for 루프를 통해 모든 컴퓨터를 탐색합니다. 만약 방문하지 않은 컴퓨터를 발견하면 DFS를 호출하고, 그 후에 네트워크 개수를 증가시킵니다. 결과 반환: 모든 탐색이 끝난 후, 발견된 네트워크의 개수를 반환합니다.

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

제한사항 n은 2 이상 100 이하인 자연수입니다. wires는 길이가 n-1인 정수형 2차원 배열입니다. wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다. 1 ≤ v1 < v2 ≤ n 입니다. 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다. 입출력 예 n wires result 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 4 [[1,2],[2,3],[3,4]] 0 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 입출력 예 설명 입출력 예 #1

다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.

4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다. 또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다. 입출력 예 #2

다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.

2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다. 입출력 예 #3

다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.

3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

풀이

function solution(n, wires) {
    // 트리 구조를 인접 리스트로 표현
    const graph = Array.from({ length: n + 1 }, () => []);

    // 그래프 초기화
    for (const [v1, v2] of wires) {
        graph[v1].push(v2);
        graph[v2].push(v1);
    }

    let minDifference = Infinity;

    // DFS 함수 정의
    function dfs(node, parent) {
        let count = 1; // 현재 노드 카운트
        for (const neighbor of graph[node]) {
            if (neighbor !== parent) {
                count += dfs(neighbor, node); // 자식 노드 탐색
            }
        }
        return count; // 서브트리의 송전탑 개수 반환
    }

    // 각 전선을 끊어보며 최소 차이를 계산
    for (const [v1, v2] of wires) {
        // 전선 v1-v2를 끊었을 때 v1에 대한 서브트리 계산
        const subtreeSize = dfs(v1, v2); // v1을 기준으로 서브트리 크기
        const otherSize = n - subtreeSize; // 나머지 송전탑 개수
        minDifference = Math.min(minDifference, Math.abs(subtreeSize - otherSize)); // 차이 계산
    }

    return minDifference; // 최소 차이 반환
}

문제이해

트리 구조: 송전탑들은 트리 형태로 연결되어 있습니다. 트리란 사이클이 없는 연결 그래프입니다. 전선 끊기: 전선 하나를 끊으면 두 개의 서브트리가 생성됩니다. 송전탑 개수 차이: 두 서브트리의 송전탑 수의 차이를 최소화해야 합니다. 기본 아이디어 DFS를 통한 서브트리 크기 계산: 각 전선을 끊었을 때 생성되는 서브트리의 송전탑 수를 계산합니다. 최소 차이 계산: 각 경우에 대해 두 서브트리의 송전탑 개수를 비교하고, 그 차이를 기록합니다.

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항 maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다. n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다. maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다. 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

풀이

function solution(maps) {
    const n = maps.length;        // 행의 수
    const m = maps[0].length;     // 열의 수
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // 남, 북, 동, 서 방향
    const queue = [[0, 0, 1]];    // [행, 열, 거리]
    const visited = Array.from({ length: n }, () => Array(m).fill(false)); // 방문 여부 초기화
    visited[0][0] = true;          // 시작점 방문 처리

    while (queue.length) {
        const [x, y, distance] = queue.shift(); // 큐에서 현재 위치와 거리 꺼내기

        // 도착점에 도착했을 때
        if (x === n - 1 && y === m - 1) {
            return distance; // 거리 반환
        }

        // 네 방향으로 이동
        for (const [dx, dy] of directions) {
            const nx = x + dx; // 새로운 행
            const ny = y + dy; // 새로운 열

            // 맵 범위와 벽 체크
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] === 1 && !visited[nx][ny]) {
                visited[nx][ny] = true; // 방문 처리
                queue.push([nx, ny, distance + 1]); // 큐에 추가
            }
        }
    }

    return -1; // 도착할 수 없는 경우
}

기억할 것

갈 수 있는 동서남북 directions 배열 지정 while(queue.length)로 자바스크립트는 while 문 조건에서 0인지 아닌지 체크해서 음수도 반복문 돌아가기 때문에 주의할 것. shift사용으로 최단거리를 구할 수 있게 된다!

*Array.from() * Array.from() 정적 메서드는 순회 가능 또는 유사배열 객체에서 얕게 복사된 새로운 Array 인스턴스를 생성한다.

Array.from(array, mapFn, thisArg) 매개변수

1. array : 배열로 변환할 순회 가능 또는 유사 배열 객체
2. mapFn(optional) : 배열의 모든 요소에 대해 호출할 함수, 이 함수를 제공하면 배열에 추가할 모든 값이 이 함수를 통해 먼저 전달되고, mapFn의 반환 값이 대신 배열에 추가됩니다. 이 함수는 다음 인수를 사용하여 호출됩니다.

• element : 배열에서 처리 중인 현재 요소
• index : 배열에서 처 리 중인 현재 요소의 인덱스

3. thisArg(optional) : mapFn실행 시에 this로 사용할 값. 다음과 같은 경우에 Array.from()을 사용하면 Array를 만들 수 있습니다. 순회 가능 객체(Map, Set과 같은 객체)인 경우. 또는 객체가 순회 가능이 아니라면, 유사 배열 객체(length 속성과 인덱싱된 요소가 있는 객체). 순회 가능이 아니거나 유사 배열이 아닌 일반 객체를 배열로 변환하려면 (속성 키, 값 또는 둘을 모두 열거하여) Object.keys(), Object.values(), 또는 Object.entries()를 사용해야 합니다. 비동기 순회 가능을 배열로 변환하려면 Array.fromAsync()를 사용합니다. Array.from(obj, mapFn, thisArg)는 중간 배열을 생성하지 않는다는 점과 배열이 아직 생성 중이기 때문에 전체 배열 없이 두 개의 인수(element, index)만 받는다는 점을 제외하면 Array.from(obj).map(mapFn, thisArg)과 동일한 결과를 가져옵니다.

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

제거한 바위의 위치 각 바위 사이의 거리 거리의 최솟값 [21, 17] [2, 9, 3, 11] 2 [2, 21] [11, 3, 3, 8] 3 [2, 11] [14, 3, 4, 4] 3 [11, 21] [2, 12, 3, 8] 2 [2, 14] [11, 6, 4, 4] 4 위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

제한사항 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다. 바위는 1개 이상 50,000개 이하가 있습니다. n 은 1 이상 바위의 개수 이하입니다. 입출력 예 distance rocks n return 25 [2, 14, 11, 21, 17] 2 4 입출력 예 설명 문제에 나온 예와 같습니다.

풀이

2) 기억할 풀이

맨 처음에 최소거리와 최대거리를 그냥 지정하고 while문 안에서 이분탐색 그대로 진행하면 되는 것이었다.

function solution(distance, rocks, n) {
    rocks.sort((a, b) => a - b); // 바위 정렬
    let left = 1; // 최소 거리
    let right = distance; // 최대 거리
    let answer = 0;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        let count = 0; // 제거할 바위 개수

        let lastPosition = 0; // 마지막 위치
        for (let rock of rocks) {
            if (rock - lastPosition < mid) {
                count++; // 바위를 제거해야 함
            } else {
                lastPosition = rock; // 현재 바위 위치로 업데이트
            }
        }

        // 마지막 바위와 도착지점 사이의 거리 체크
        if (distance - lastPosition < mid) {
            count++;
        }

        if (count <= n) {
            answer = mid; // 최소 거리 가능
            left = mid + 1; // 더 큰 거리 탐색
        } else {
            right = mid - 1; // 더 작은 거리 탐색
        }
    }

    return answer;
}

1) 처음 접근했던 방식

rocks 배열에서 무작위로 n개를 버리고, 남은 rocks배열에서 다음 코드와 함께 이분 탐색을 실행하고, arr배열에 거리의 최솟값을 push 한 다음 Math.max(...arr) 로 정답을 리턴해주면 되지 않을까?

let left = rocks.sort((a,b)=> a-b)[0] let right = distance - left

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다. 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다. 심사관은 1명 이상 100,000명 이하입니다. 입출력 예 n times return 6 [7, 10] 28 입출력 예 설명 가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

풀이

(2) 기억할 풀이

function solution(n, times) {
    let low = 1;
    let high = n * Math.min(...times);

    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        let totalPeople = 0;

        for (const time of times) {
            totalPeople += Math.floor(mid / time);
        }

        if (totalPeople >= n) {
            high = mid; // 더 적은 시간으로도 가능하므로 high를 줄임
        } else {
            low = mid + 1; // 더 많은 시간이 필요하므로 low를 늘림
        }
    }

    return low; // 모든 사람이 심사를 받는 데 걸리는 최소 시간
}

low는 1분, high는 n * min(times)로 설정합니다. 여기서 min(times)는 가장 빠른 심사관이 심사하는 데 걸리는 시간입니다. 시간 계산: 중간값 mid를 선택한 후, 각 심사관이 mid 분 동안 심사할 수 있는 최대 인원 수를 계산합니다. 이때, 각 심사관의 인원 수는 Math.floor(mid / time)로 계산됩니다. 조건 검사: 만약 총 심사할 수 있는 인원이 n명 이상이면 high를 mid로 줄이고, 그렇지 않으면 low를 mid + 1로 증가시킵니다. 결과 반환: 이진 탐색이 끝나면 low가 모든 사람이 심사를 받는 데 걸리는 최소 시간을 나타냅니다. 이진 탐색: low와 high를 설정하고, mid를 계산하여 심사 가능한 인원을 체크합니다. 시간 계산: 각 심사관이 mid 시간 동안 몇 명을 심사할 수 있는지 계산하여 총 인원을 구합니다. 조건에 따른 범위 조정: 인원이 충분하면 시간을 줄이기 위해 high를 조정하고, 부족하면 low를 증가시킵니다. 결과 반환: 이진 탐색이 종료된 후, low 값이 모든 사람의 심사가 끝나는 최소 시간을 반환합니다. 이 방법은 효율적으로 O(m log(n * min(times)))의 시간 복잡도를 가지며, m은 심사관의 수입니다.

(1) 처음 접근방식

배열 사이즈가 너무 커져서 시간초과로 런타임에러가 발생한다.

function solution(n, times) {
    let people = 0;
    let timeArray =[]
    const maxNum = Math.min(...times) *n
    let answer =0;
    // 배열을 만들어서 넣어야하나.. ? ? 
    // 최대값을 뽑은다음에 그 값이하로 배열을 만들고, 계산하면 안되나?! 

    for(const m of times){
        let currentTime =0
        let count = 1;

        while(currentTime < maxNum){
              currentTime = m*count
              timeArray.push(currentTime)
              count+=1
        }
    }
    const sortArr = timeArray.sort((a,b)=> a-b)
      for (let i = 0; i < sortArr.length; i++) {
        if (i + 1 === n) {
            return sortArr[i];
        }
    }
}

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입니다. 입출력 예 numbers target return [1, 1, 1, 1, 1] 3 5 [4, 1, 2, 1] 4 2 입출력 예 설명 입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4 +4-1+2-1 = 4 총 2가지 방법이 있으므로, 2를 return 합니다.

해결방법

DFS(Depth-First-Search)

• 그래프/트리의 한 경로를 끝까지 탐색한 후 다음 경로를 탐색하는 방식
• 주로 재귀함수나 스택으로 구현
• 메모리를 적게 사용하지만 최단 경로를 찾지 못할 수 있음

마지막 값까지 +/- 경우의 수를 계산해야야하므로 DFS로 풀어야 했다.

function solution(numbers, target) {
    const dfs = (index, currentSum) =>{
        if (index === numbers.length){
            return currentSum === target ? 1: 0
        }

        const addCase = dfs(index+1, currentSum + numbers[index])
        const subtractCase = dfs(index+1, currentSum - numbers[index])

        return addCase + subtractCase
    }
    return dfs(0,0)
}

풀이과정

return dfs(0,0) 으로 호출하여, index값 +1과 현재 sum값 재귀호출하고, 마지막 인덱스+1인 경우 target과 같은지 비교 후 종료

TS 1. interface / type / 연산자

1. interface

인덱싱 타입선언

interface StringArray {
  [index: number]: string;
}

let arr: StringArray = ['a','b','c'];
arr[0]; // 'a'
arr[0] = 10; // 타입 오류 발생 (string에 할당할 수 없다) 

*딕셔너리 타입선언 *

interface StringRegexDictionary {
  [key: string] : RegExp; // 정규표현식 타입
}

let obj: StringRegexDictionary = {
  //sth: /abc/
  cssFile: /\.css$/, // css 파일 정규식으로 작성
  jsFile: /\.js$/, // js로 끝나는 파일
}
// 장점
Object.keys(obj).forEach(function(value){
  // 이 안에 들어오는 값들의 정의가 string이 된다 
  // 자동으로 value가 string으로 추론된다. 
})

인터페이스 확장 (상속)

interface Person {
  name: string;
  age: number;
}

interface Developer extends Person {
  language: string;
}

let capt: Developer = {
  // Person 타입도 추가해주어야 에러가 안난다
  name: 'juur';
  age: 22;
  language: 'ts';
}

OOP(객체지향 프로그래밍) Object Oriented Programming 무엇이냐면 !)! 정리 추가하기.

2. 타입 별칭 (Type Aliases)

타입 별칭은 특정 타입이나 인터페이스를 참조할 수 있는 타입 변수 의미

type Person = {
  name: string;
  age: number;
}

interface와 type의 차이점

• type을 사용하면, 해당 타입 코드 전체를 바로 볼 수 있다.
• interface는 해당 코드가 아닌 없는 변수값들을 볼 수 있다.

타입 별칭은 새로운 타입 값을 하나 생성하는 것이 아니라 정의한 타입에 대해 나중에 쉽게 참고할 수 있게 이름을 부여하는 것과 같다

interface 사용시 해당 타입 마으스오버 + command 클릭 = 바로가기 type은 확장이 되지 않는다. <가장 큰 차이점>

• ts 공식문서 : 인터페이스는 확장이 가능한데 반해 타입 별칭은 확장이 불가능. 따라서, 가능한한 interface로 선언해서 사용하는 것을 추천한다.

3. 연산자

(1) union type(|)

타입가드 : if문 typeof로 타입확인하여 특정 동작하도록 하는 것 특정 타입으로 타입의 범위를 좁혀나가는(필터링 하는) 과정

let hee : string | number | boolean; 
const logMessage = (value: string | number) => {
  if(typeof value === 'number') {
    value.toLocaleString(); // 메소드 바로 사용 가능
  }
  if(typeof value ==='string') {
    value.toString();
  }
  throw new TypeError('value must be string or number'); // 나머지 타입은 타입에러 발생시킴
}

유니온 타입(|) 특징

| : 모든 속성 접근 가능하지 않고, 공통으로 갖고 있는 속성만 접근 가능함 혹은 타입가드이용하면 됨

(2) intersection type(&)

갖고 있는 타입 속성으로 노출되고 접근 가능 속성 중 하나라도 빠지면 타입에러 발생

TS 2. Enums

1. 이넘(Enums)

특정 값들의 집합을 의미하는 자료형 (ex. 드롭다운, 정해져있는 목록) 별도로 값 지정하지 않으면, 숫자형 0부터로 자동지정

(1) 숫자형 이넘

enum Shoes {
  Nike,
  Adidas
}

const myShoes = Shoes.Nike;
console.log(myShoes); // 0

(2) 문자형 이넘

enum Shoes {
  Nike:'나이키',
  Adidas:'아디다스'
}

const myShoes = Shoes.Nike;
console.log(myShoes); // 나이키

(3) 이넘 활용 사례

예외처리 케이스 줄어들 수 있다.

enum Answer {
  Yes ='Y', 
  No = 'N',
}
function askQuestion(answer: string) {
  // 단순히 아래처럼 문자열 비교가 아니라 enum 을 활용해서 좀 더 정확하게 
  // if (answer ==='yes') {console.log('정답입니다')}
  if (answer === Answer.Yes) {console.log('정답입니다')}
  if (answer === Answer.No) {console.log('오답입니다')}
} 
askQuestion(Answer.Yes);
//  XX => askQuestion('Yes'); // Enum 에서 제공하는 값만 넘길 수 있다.

TS 3. class ES 2015(ES6)부터 지원 - 프로토타입을 이용한 상속

1. class 역할 : 인스턴스를 만들어준다

constructor() {} => 초기화 메소드

class Person {
  // 클래스 로직  :객체 기본속성, 혹은 api 등 설정 가능
  constructor(name, age) {
    console.log('생성 되었습니다');
    this.name = name;
    this.age = age;
  }
}

const hee = new Person('hee', 300); // 생성
console.log(hee); // 객체 생성 Person {name: 'hee', age: 300}

2. class 쓰는 이유?

기본 전제 > JS가 프로토타입 기반 언어이다

자바스크립트 프로토타입 (class가 프로토타입 ) 프로토타입을 이용한 상속

admin.__proto__를 통해 user를 상속받는다. admin 객체를 추가할 수 있고, admin.name과 admin.age에도 접근 가능하다.

3. 프로토타입 활용 사례

Built-in Javascript API 또는 Javascript Native API => Prototype을 일상생활에서 이미 쓰고 있었다. 단순히 객체정보 확장 뿐만 아니라, 기능들을 바로 바로 쓸 수 있다.

4. ES6이전/이후 class 차이

클래스라는 것은, 기존 문법의 syntatic sugar(보기 좋은 코드) 정도의 느낌 = 추가적 기능 = 기존 제공하던 성질 변경없이 문법만 추가

*1) ES6 이전 *

class 없이 사용 가능!

function Person(name, age) {
  this.name = name; 
  this.age = age;
}

const hee = new Person('희', 300);

2) ES6 이후

자바 개발자 혹은, 객체지향 언어 개발자들을 위해, 자바스크립트를 쓰기 수월하게 class 문법 제공한 것 하지만 babel 통해 돌려보면, 실질적으론 위처럼 생성자 함수를 썼다는 것을 알 수 있다. 기존 prototype 기반 유지, class 없이 충분히 위 함수처럼 사용 가능하다.

class Person {
  constructor(name, age) {
    this.name = name;
    this.age = age; 
  }
}

const hee = new Person('희2', 300);

5. 타입스크립트의 class

타입스크립트에선 class 최상단에 멤버변수(속성들) 타입을 선언해줘야 한다. constructor에 들어오는 파라미터 타입도 구체적으로 정할 수 있다

또, 변수의 유효 범위도 설정할 수 있다.

class Person {
  private name: string; 
  public age: number; // 기본 public
  readonly log: string; // 읽기만 가능

  constructor(name: string, age: number) {
    this.name = name;
    this.age = age; 
  }
}

6. 리액트 문법 : 클래스->훅 기반 함수형 코드

(1) 이전

class App extends React.Component { ... }

(2) 이후

function App() {
  return <div>Hello World</div>
}

TS 4. 제네릭

1. 제네릭 개념

타입을 마치 함수의 파라미터처럼 사용하는 것을 의미 함수의 이름 바로 뒤에 <T>라는 코드 추가. 그리고 함수의 인자와 반환 값에 모두 T라는 타입을 추가. 이렇게 되면 함수를 호출할 때 넘긴 타입에 대해 타입스크립트가 추정할 수 있게 된다. 따라서, 함수의 입력 값에 대한 타입과 출력 값에 대한 타입이 동일한지 검증할 수 있게 된다.

function logText<T>(text: T):T {
  return text; 
}

// 두 가지 방법으로 호출 가능 
// #1 호출시점 타입 넘겨주기 가능
const text = logText<string>("Hello generic!");
// #2
const text2 = logText("Hello generic!!");

2. 제네릭 장점

동일 코드를 타입을 받기 위해 불필요하게 함수 사용하는 경우를 줄일 수 있다. 만약 유니온타입으로 쓴 경우엔, 공통으로 쓸 수 있는 메소드만 미리 보여주기 가능하다.

반환값이 문자여도, number 타입을 유니온타입으로 추가해주었기에 ex.split('')사용 시, 타입오류가 뜨게 된다. => 제네릭 사용 시, 이런 오류가 해결된다! 같은 코드를 호출시점에 타입 정의해주어 타입추론해서 반환값까지 알 수 있게 된다.

function logText(text: string | number) {
  console.log(text);
  // text. toLocaleString / toString / valueOf 뜸
  return text; 
}

const a = logText('a');
a.split(''); // 사용 시에 반환 타입이 string/number 2개로 
// 이 부분에서 ts오류가 뜨게 된다. 

3. 제네릭 적용

interface Dropdown <T>{
  value: T,
  selected: boolean
}

const emails:Dropdown<string>[] = [
  { value: 'naver.com', selected: true },
  { value: 'gmail.com', selected: false },
  { value: 'hanmail.net', selected: false },
];

const numberOfProducts :Dropdown<number>[]= [
  { value: 1, selected: true },
  { value: 2, selected: false },
  { value: 3, selected: false },
];

function createDropdownItem<T>(item:Dropdown<T>) {
  const option = document.createElement('option');
  if(typeof item.value ==='string') {
    option.value = item.value.toString();
    option.innerText = item.value.toString();
  }
  option.selected = item.selected;
  return option;
}

// NOTE: 이메일 드롭 다운 아이템 추가
emails.forEach(function (email) {
  const item = createDropdownItem<string>(email);
  const selectTag = document.querySelector('#email-dropdown');
  selectTag?.appendChild(item);
});

4. 제네릭의 타입제한

제네릭 더 엄격하게 쓸 때! split('') ,forEach 등 배열 메소드 사용하려고 할 때, T를 제한해서 T[]로 사용한다.

(1) T[]로 배열 메소드 사용 가능

function logTextLength<T>(text: T[]):T[] {
  console.log(text.length);
  text.forEach((text)=> console.log(text))
  return text;
}
logTextLength<string>(['hi','hee'])

(2) 정의된 타입 이용하기 (generic은 확장의 의미보단 제한의 의미다)

제네릭에 타입제한이 생긴 것!

(3) keyof로 제네릭 타입 제한하기

함수호출하는 시점 제네릭의 타입만 잘 넘겨주면 정확하게 타입 잘 선언한 모습. 인터페이스 속성만 받도록 제한하겠다. ShoppingItem의 키들 중 한 가지가 바로 T로 들어올 것이란 의미

TS 5. 타입 추론 (type Inference)

1. 타입 추론의 기본

변수를 선언하거나 초기화 할 때 타입이 추론된다. 이외에도 변수, 속성, 인자의 기본 값, 함수의 반환 값 등을 설정할 때 타입 추론이 일어난다.

ES6-Default Value(인자 기본값 정의)

함수 호출할 때, b를 넘기지 않으면 기본적으로 10의 값을 넘긴다. 함수 내부에 변수 선언하면 c의 타입은 string, 타입 추론일어남

문자열 + 숫자 = 문자가 나오게 된다. 10 + '10' = '1010'

function getB(b=10) {
  const c = 'hi';
  return b+c; // '10hi'
}

2. 인터페이스와 제네릭을 이용한 타입 추론 방식

3. 복잡한 구조에서의 타입 추론방식

4. 가장 적절한 타입

Best Common Type : TS의 알고리즘, 가장 근접한 타입 추론 모든 값들을 union으로 묶어간다.

5. TypeScript in Visual Studio Code

https://code.visualstudio.com/docs/languages/typescript nodeModules 하위 파일 확인하면 다음과 같다 세부 내용 읽어보고 도움될 것 같은 부분은 따로 정리하는 것으로!

TS 6. 타입 단언 (type assertion), 타입 가드

1. 타입 단언 (as 타입)

타입스크립트보다 개발자가 타입 더 잘 알 때, 타입단언 사용!

2. DOM API 조작할 때

일반적으로 document.속성에서 제공하는 속성들 웹페이지 태그정보로 접근하고, 조작할 수 있는 api 대표적으로, document.querySelector()

// DOM API 조작
// <div id = "app">hi</div>

const div = document.querySelector('div');

() 안에 'div' 선언하면 #app으로 작성했을 때보다 구체적인 태그 타입이 입력된다. vs내부에서 lib.dom.d.ts 타입이 선언되어 있기 때문이다.

div가 없을 수 있다.-> 이 경우 const div = document.querySelector('div') as HTMLDivElement; if(div) { div.innerText } 식으로 사용

타입단언하지 않으면 null타입도 추가된다.

3. 타입 가드

유니온으로 타입이 되어 있는 경우, 공통 속성이 아니면 속성값 없다고 경고가 뜬다.

*타입가드를 적용하면 에러가 뜨지 않는다 ! 예제 *

4. 타입 가드 실제 적용

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
제한사항 word의 길이는 1 이상 5 이하입니다. word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다. 입출력 예 word result "AAAAE" 6 "AAAE" 10 "I" 1563 "EIO" 1189 입출력 예 설명 입출력 예 #1 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다. 입출력 예 #2 "AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다. 입출력 예 #3 "I"는 1563번째 단어입니다. 입출력 예 #4 "EIO"는 1189번째 단어입니다.

풀이

좀 더 생각하고 정리해보자.

function solution(word) {
  const alphabets = ["A", "E", "I", "O", "U"];
  const w1 = 5 ** 0;
  const w2 = 5 ** 1;
  const w3 = 5 ** 2;
  const w4 = 5 ** 3;
  const w5 = 5 ** 4;

  // 각 자리수별 값: 1부터 시작해서 각 자리수마다 5배씩 늘어남
  const values = [
    w1, // 1
    w1 + w2, // 6
    w1 + w2 + w3, // 31
    w1 + w2 + w3 + w4, // 156
    w1 + w2 + w3 + w4 + w5, // 781
  ];
  // A, E, I, O, U -> 5개 / 1 ~ 5
  // AA, AE, AI, AO, AU
  // EA, EE, EI, EO, EU ... -> 25개 / 6(5+1) ~ 30(5+5*5)

  return word.split("").reduce((answer, char, index) => {
    // 현재 알파벳의 인덱스 * 현재 자리수의 값
    return answer + alphabets.indexOf(char) * values[4 - index] + 1;
  }, 0);
}

처음 접근방식

function solution(word) {
    const vowels = ['A', 'E', 'I', 'O', 'U'];
    let order = 0;

    // 각 길이에 대해 가능한 단어 수 계산
    for (let i = 1; i < word.length; i++) {
        order += Math.pow(5, i); // 5^1 + 5^2 + ... + 5^(length-1)
    }

    // 주어진 단어의 각 문자에 대해 순서 계산
    for (let i = 0; i < word.length; i++) {
        const index = vowels.indexOf(word[i]); // 현재 문자에 대한 인덱스
        order += index * Math.pow(5, word.length - i - 1); // 해당 자리에서 가능한 조합 수
    }

    // 1부터 시작하므로 1을 더해줌
    return order + 1;
}

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. *입출력 예 *numbers return "17" 3 "011" 2 입출력 예 설명 예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다. 11과 011은 같은 숫자로 취급합니다.

풀이

재귀적 순열 생성 (숫자를 이어서 다양한 조합생성용으로 필요하다) 중복 제거를 위해 Set 사용 (같은 숫자일 경우엔 중복이 발생하므로 Set으로 중복제거!) 효율적인 소수 판별 로직 (만들어진 숫자가 소수인지 판단하는 것이 필요하다!)

function solution(numbers) {
   const numberSet = new Set();

   // 순열 생성 함수
   function generatePermutations(current, remain) {
       if (current.length > 0) {
           numberSet.add(Number(current));
       }

       for (let i = 0; i < remain.length; i++) {
           const newCurrent = current + remain[i];
           const newRemain = remain.slice(0, i) + remain.slice(i + 1);
           generatePermutations(newCurrent, newRemain);
       }
   }

   // 소수 판별 함수
   function isPrime(num) {
       if (num <= 1) return false;

       for (let i = 2; i <= Math.sqrt(num); i++) {
           if (num % i === 0) return false;
       }
       return true;
   }

   // 순열 생성
   generatePermutations('', numbers);

   // 소수 개수 세기
   return Array.from(numberSet).filter(isPrime).length;
}

문제

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항 genres[i]는 고유번호가 i인 노래의 장르입니다. plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다. genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다. 장르 종류는 100개 미만입니다. 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다. 모든 장르는 재생된 횟수가 다릅니다. 입출력 예 genres plays return ["classic", "pop", "classic", "classic", "pop"] [500, 600, 150, 800, 2500] [4, 1, 3, 0]

풀이

• 처음에 잘못생각했던 부분 > 장르 가장 많은 순 2개를 뽑아, 각 장르 2개 곡 기록으로 오해

• 객체로 key값에 해당하는 value를 먼저 만들어 준 다음, object는 순서가 없기 때문에 entries를 사용해서 value 순 내림차순 (b-a) 로 큰 순서대로 장르 배열 완성

• 장르배열 개수만큼 빈 배열을 만들어 준 다음, 해당 배열 인덱스0부터 장르 인기순이기 때문에 해당하는 장르와 일치한다면 index값과 숫자값 배열을 넣어준다.

• 그리고 다시 노래 value순으로 내림차순하고, 최대 2값이기 때문에 sort 후 바로 slice!!

• 그런 다음 1차원 배열로 만들어주기 위해 flat()함수를 사용하고 각 배열에서의 0번째 인덱스 값을 뽑아서 answer로 반환해준다.

  function solution(genres, plays) {
    const genresObject = {}
    let answer =[]
    // 장르 가장 많은 순 뽑기 
    // 장르 내 많이 재생된 노래 수록
    for (let i=0; i<genres.length; i++){
        if(!genresObject[genres[i]]) genresObject[genres[i]]=plays[i]
        else genresObject[genres[i]] += plays[i]
    }
    const maxSortedGenres = Object.entries(genresObject).sort((a,b) => b[1]-a[1]).map(v=>v[0])
    const dynamicArray = Array.from({ length: maxSortedGenres.length }, () => []);
  
    for (i=0; i<genres.length; i++){
       const index = maxSortedGenres.findIndex(v => v === genres[i])
       dynamicArray[index].push([i,plays[i]])
    }
    const sortArr= dynamicArray.map(genre=> genre.sort((a,b) => b[1]-a[1]).slice(0,2))
    console.log(sortArr,'sortArr')
    console.log(sortArr.flat(),'sortArr.flat()')
    sortArr.flat().forEach(v=> answer.push(v[0]))
    return answer;
  

}

### 다른 사람 풀이
엄청 깔끔한 코드 
sort에서 장르가 같지 않으면 내림차순 정렬 / count 내림차순 정렬 / 인덱스 기준으로는 오름차순 정렬! 

map으론 객체 구조 만들 때, genre : t
count: plays[i] , index: i 값 -- 이 부분 기억하자! 

```tsx
function solution(genres, plays) {
    let dic = {};
    genres.forEach((t,i)=> {
        dic[t] = dic[t] ?  dic[t] + plays[i] :plays[i];        
    });

    let dupDic = {};
    return genres          
          .map((t,i)=> ({genre : t, count:plays[i] , index:i}))
          .sort((a,b)=>{               
               if(a.genre !== b.genre) return dic[b.genre] - dic[a.genre];
               if(a.count !== b.count) return b.count - a.count;
               return a.index - b.index;
           })
           .filter(t=>  {
               if(dupDic[t.genre] >= 2) return false;
               dupDic[t.genre] = dupDic[t.genre] ? dupDic[t.genre]+ 1 : 1;
               return true;
            })
           .map(t=> t.index);    
}

회고

갑자기 핸드폰이 망가져서 애플매장 다녀오고 성지가서 핸드폰 산 날... 이게 무슨 날벼락~!! 갑자기 New 폰이 생겨버렸다 ㅎㅎ

이진 트리를 표현한 배열 nedes를 인자로 받습니다. 예를 들어서 nodes가 [1,2,3,4,5,6,7]이면 해당 이진 트리에 대하여 전위 순회, 중위 순회, 후위 순회 결과를 반환하는 solution()함수를 구현하세요
제약조건 입력 노드값의 개수는 1개 이상 1,000개 이하다 노드값은 정수형이며 중복되지 않는다
문제 분석하고 풀기 말 그대로 전위, 중위, 후외 순회를 반환하면 되는 문제

function preorder(nodes, idx) {
  // idx가 노드 배열의 길이보다 작을 떄 
  if(idx <nodes.length){
    // 루트 노드를 출력한 다음, 
    //왼쪽 오른쪽 서브트리를 재귀 호출하여 출력 순서대로 이어붙임 
    let ret = `${nodes[idx]}`
    ret += preorder(nodes, idx*2+1);
    ret += preorder(nodes, idx*2+2);
    return ret;
  }
  // idx>= nodes.length일 때는 빈 문자열 반환
  reutn ""; 

}

function inorder(nodes, idx){
  // idx가 노드 배열의 길이보다 작을 때
  if (idx < nodes.length) {
    // 왼쪽 서브 트리를 먼저 재귀호출하여 출력 순서대로 이어붙임
    let ret=inorder(nodes, idx*2+1);
    // 루트 노드를 출력한 다음 오른쪽 서브 트리를 재귀호출하여 
    // 출력 순서대로 이어붙임 
    ret += `${nodes[idx]}`
    ret += inorder(nodes, idx*2+2);
    return ret;
  }
  // idx >= nodes.length일 때는 빈 문자열 반환 
  return ""; 
}

function postorder(nodex,idx){
  // idx가 노드 배열의 길이보다 작을 때 
  if(idx< nodes.length){
    // 왼쪽 서브 트리와 오른쪽 서브 트리를 재귀 호출하여 출력 순서대로 이어붙임
    let ret=postorder(nodes,idx*2+1);
    ret += postorder(nodes, idx*2+2);
    ret += `${nodes[idx]}`
    return ret
  }
  // idx>=nodes.length일 때는 빈 문자열 반환
  return ""; 
}

function solution(nodes){
  // 전위 순회, 중위 순회, 후위 순회 결과 계산
  // 노드 배열과 루트 노드의 인덱스를 매개변수로 각각 호출
  return [
    preorder(nodes,0).slice(0,-1), // 마지막 공백 제거
    inorder(nodes,0).slice(0,-1), // 마지막 공백 제거
    postorder(nodes,0).slice(0,-1)
  ]
}

위 코드는 nodes는 노드 배열을 의미하며 solution()함수에서는 이 nodes 배열과 루트 노드의 인덱스를 preorder(), inorder(), postorder() 함수에 인수로 전달하여 전위 순회, 중위 순회, 후위 순회 결과를 각각 계산하고 이를 배열로 반환한다.

preorder(), inorder(), postorder() 함수에서는 idx가 노드배열 길이보다 작을 때만 재귀 호출하도록 하며 idx가 노드 배열의 길이와 같거나 크면 빈 문자열을 반환한다. solution()함수에서는 반환된 결과 문자열에서 마지막 공백을 제거한 뒤 배열로 반환한다.

이 문제의 핵심은 '배열로 표현한 이진 트리를 순회하는 코드를 구현하라' 이다. 앞서 배열로 트리를 표현할 때 루트 노드가 인덱스 0이 될 수도, 인덱스 1이 될 수도 있지만 1을 자주 쓴다고 했다. 여기서는 1이 아닌 0을 쓰는 경우를 보여주기 위해 루트 노드의 인덱스를 0으로 하였다.

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.
제한사항 행의 개수 N : 100,000 이하의 자연수 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다. 점수 : 100 이하의 자연수

풀이

DP로 풀어야하는 것 까지 이해가 됐는데, 그 다음 생각을 어떻게 할지..!

(1) reduce 이용

reduce() 메서드는 배열의 각 요소에 대해 주어진 리듀서 함수를 실행하고, 하나의 결과값을 반환

const array = [1,2,3,4]
const initialValue = 0;
const sumWithInitial = array.reduce((accumlator, currentValue) => accumulator + currentValue, initialValue);

리듀서 함수는 4개의 인자를 갖는다.

1. 누산기 (acc)
2. 현재값 (cur)
3. 현재 인덱스 (idx)
4. 원본 배열 (src)

리듀서 함수의 반환 값은 누산기에 할당되고, 누산기는 순회 중 유지되므로 결국 최종 결과는 하나의 값이 된다.

arr.reduce(callback, [initialValue]) 매개변수 callback : 배열의 각 요소에 대해 실행할 함수. 다음 4가지 인수를 받는다. accumulator : 누산기는 콜백의 반환값을 누적. 콜백의 이전 반환값 또는 콜백의 첫 번째 호출이면서 initialValue를 제공한 경우에는 initialValue의 값

currentValue : 처리할 현재 요소 currentIndex : 처리할 현재 요소의 인덱스. initialValue를 제공한 경우 0, 아니면 1부터 시작. array : reduce()를 호출한 배열

initialValue : callback의 최초 호출에서 첫 번째 인수에 제공하는 값. 초기값을 제공하지 않으면 배열의 첫번째 요소 사용. 빈 배열에서 초기값 없이 reduce()호출하면 오류 발생

배열의 첫 번째 요소 [1,2,3,5] 에서 다음 배열의 겹치지 않는 인덱스를 더해준다.

열은 3개. reduce안은 2번 실행

function solution(land) {
    return Math.max(
    ...land.reduce((a,c) => {
        return [c[0] + Math.max(a[1],a[2],a[3]),
               c[1] + Math.max(a[0],a[2],a[3]),
                c[2]+ Math.max(a[0],a[1],a[3]),
                c[3]+Math.max(a[0],a[1],a[2])]
    }))
}

(2) 반복문에서 현재값+=이전값으로 저장

function solution(land) {
    for(let i=1; i<land.length; i++){
        land[i][0] += Math.max(land[i-1][1],land[i-1][2],land[i-1][3])
        land[i][1] += Math.max(land[i-1][0],land[i-1][2],land[i-1][3])
        land[i][2] += Math.max(land[i-1][0],land[i-1][1],land[i-1][3])
        land[i][3] += Math.max(land[i-1][0],land[i-1][1],land[i-1][2])
    }
    return Math.max(...land[land.length-1])
}

문제

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.
x에 n을 더합니다 x에 2를 곱합니다. x에 3을 곱합니다. 자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

해결방법

내가 푼 방식으로는 테스트케이스를 다 통과하지 못했다. 그래서 다른 풀이방법 찾아봤음.

디버깅 이해 필요함. 풀이 방법을 찾아보니 DP가 시간 효율성은 더 좋았고, BFS로도 문제를 해결할 순 있었다.

풀이 2: BFS + Map은 추가된 요소 반복문 추가로 돌수 있다

초기 인덱스 값 0으로 설정하고, 배열 arr에 Map key값 추가해줘서 현재 반복문이 아닌 while문에서 조건 검사 다시해서 돌고, 인덱스값을 통해 shift 역할을 할 수 있다.

하지만 Map은 그 자체로 [current, count] 으로 꺼낼 수 있기 때문에 굳이 index, array를 이용할 필요가 없었다. !

최적화된 코드로 기억해두자.

그리고 반복문 돌 때, 처음에 존재하지 않은 key값일 때 count값 기록해두고, 다음 차례일 때 cnt+1된 값으로 다시 key값에 count값 기록된다.

function solution(x, y, n) {
    if (x === y) return 0;

    const queue = new Map([[x, 0]]);  // key: 숫자, value: 연산 횟수
    for ( let [cur,cnt] of queue){
        for (const next of [cur + n, cur * 2, cur * 3]) {
            if (next === y) return cnt + 1;
            if (next > y || queue.has(next)) continue;

            queue.set(next, cnt + 1);
        }
    }

    return -1;
}

풀이 1: BFS 풀이

set으로 문제풀이하면 시간초과가 떠서 map으로 풀어야 한다.

function solution(x, y, n) {
    if (x === y) return 0;

    const queue = new Map([[x, 0]]);  // key: 숫자, value: 연산 횟수
    let index = 0;
    const arr = [x];  // queue 역할

    while (index < arr.length) {

        const cur = arr[index++];
        const cnt = queue.get(cur);

        for (const next of [cur + n, cur * 2, cur * 3]) {
            if (next === y) return cnt + 1;
            if (next > y || queue.has(next)) continue;

            queue.set(next, cnt + 1);
            arr.push(next);
        }
    }

    return -1;
}

풀이 2: DP 풀이

DP 배열의 의미

dp[i]: 숫자 x에서 i를 만들기 위한 최소 연산 횟수 배열을 Infinity로 초기화하는 것은 아직 도달하지 못한 숫자를 표시하기 위함 dp[x] = 0: 시작 숫자는 연산이 필요 없으므로 0으로 초기화

function solution(x, y, n) {
    const dp = new Array(y+1).fill(Infinity);
    dp[x] = 0;
    for(let i=x; i<y; i++){
        dp[i+n] = Math.min(dp[i+n],dp[i]+1);
        dp[i*2] = Math.min(dp[i*2],dp[i]+1);
        dp[i*3] = Math.min(dp[i*3],dp[i]+1);
    }
    return dp[y]!==Infinity? dp[y] : -1;
}

BFS, DFS, DP의 차이점과 공통점

*공통점 : * 1. 모두 문제 해결을 위한 체계적인 접근 방법 2. 상태 공간을 탐색한다는 점 3. 방문 처리가 필요한 경우가 많음
*차이점 : * *1.탐색방식 * 1)BFS : 레벨단위 탐색 2)DFS : 경로단위 탐색 3)DP : 하위문제 단위 탐색 *2.메모리 사용 * 1)BFS : 큐에 많은 상태 저장 2)DFS : 재귀스택 사용 3)DP : 결과값 테이블 사용 *3.최적해 보장 * 1)BFS: 최단경로 보장 2)DFS: 최단경로 보장x 3)DP: 최적부분 구조일 때 최적해 보장
*이 문제의 경우 BFS나 DP가 적합한 이유: *1. 최소 연산 횟수를 찾아야 함. 2. 상태가 숫자 하나로 단순함 3. 중복 계산을 피해야 함.

BFS(너비 우선 탐색)

• 특징: 같은 레벨의 모든 노드를 먼저 탐색
• 구현: Queue 사용
• 장점: 최단 경로 보장
• shift 연산 사용 시, 시간 복잡도 => O(n) 맨 앞에 있는 값을 제거한 후에 기존 배열에 있던 모든 원소를 한 자리씩 왼쪽으로 이동시켜야 하기 때문에 시간 복잡도가 O(n)이다.

• shift 연산을 배열과 인덱스를 사용한 큐로 구현 가능하다. O(1)

  // BFS 예시 
  const queue = [[start, 0]];
  while(queue.length) {
   const [current, count] = queue.shift();
   // 인접한 모든 노드를 큐에 추가
  }

DFS(깊이 우선 탐색)

• 특징: 한 경로를 끝까지 탐색한 후 다음 경로 탐색
• 구현: Stack 또는 재귀 사용
• 장점: 메모리 사용이 적음

  function dfs(current, count){
  if(종료조건) return;
  // 다음 노드로 재귀 호출
  dfs(next, count+1);
  }

DP(동적 계획법)

• 특징: 문제를 작은 하위문제로 나누어 해결
• 구현: Map이나 배열에 결과 저장
• 장점: 중복계산 방지

  // DP 예시 (앞서 본 코드)
  const dp = new Array(y+1).fill(Infinity);
  dp[x]=0;
  for(let i=x; i<y; i++) {
   dp[i+n]= Math.min(dp[i+n],dp[i]+1); 
  }  

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.
큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.
다음은 두 큐를 나타내는 예시입니다.
queue1 = [3, 2, 7, 2] queue2 = [4, 6, 5, 1] 두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.
queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다. queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다. 따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.
길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.
제한사항 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000 1 ≤ queue1의 원소, queue2의 원소 ≤ 109 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

풀이

항상 문제를 쉽게 푸는 방법으로 생각을 하기..! 이 문제는 합이 같을 때까지 배열에서 한 값을 다른 쪽 배열로 집어넣는것 이런 발상을 하는 연습을 더 하자..!

function solution(queue1, queue2) {
    const arraySum= (arr) => arr.reduce((acc,cur)=> acc+cur);
    let sum1 = queue1.reduce((acc,cur)=> acc+cur,0) 
    let sum2 = queue2.reduce((acc,cur)=> acc+cur,0)
    const totalLength = queue1.length + queue2.length
    let queue1Idx = 0
    let queue2Idx = 0
    let answer =0

    while(sum1 !== sum2){
      if(sum1>sum2){
          sum1 -= queue1[queue1Idx]
          queue2.push(queue1[queue1Idx])
          sum2 += queue1[queue1Idx++]
      }
      else{
          sum1 += queue2[queue2Idx]
          queue1.push(queue2[queue2Idx])
          sum2 -= queue2[queue2Idx++]
      }
      answer++
      if(queue1Idx>=totalLength || queue2Idx>=totalLength) return -1

    }

    return answer;
}