완전탐색_ver.2

야 나 개 ·2021년 12월 14일
0
post-thumbnail

알고리즘..
.
...
알탕 먹고 싶다.

당장히 문제를 푸는것 보단 이해 해야 한다.

--

어떤 수학쌤이 이런말을 했던것이 기억이 난다.

수학을 잘하려면
국어를 잘해야 한다!
문제를 이해를 해야 풀수 있다.!!

알고리즘 또한 문제를 이해를 해야 잘 풀 수 있다.
문해력을 요구하는 문제들도 많다.

간단한 문제를 뭐 되도않게 길게 적어놓고 손에 땀나게 해서
키보드만 고장나게 한다.!!!

지금 딱 말한다.!

알고리즘 쉽다 쉽다 쉽다!!

그럼 시작하자! 렛츠기릿!

1번문제

[70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.

-> 최소 박스를 사용해서 그 박스의 갯수를 구해라

예제

let output = movingStuff([70, 50, 80, 50], 100);
console.log(output); // 3

let output = movingStuff([60, 80, 120, 90, 130], 140);
console.log(output); // 4

생각하자

이런 비슷한 문제들이 많이 나올테니
물건을 넣을때 가장 효율적인건 가장 큰거부터 넣고 그 후에 다른거 생각하면 된다.

  1. 최대값, 최소값을 찾자
    -> arr.sort((a,b) => a - b)
    오름차순으로 하게 되면 최소값은 [0]번째 인덱스고 최대값은 배열에 마지막에 있다.

  2. 최소값과 최대값을 더하고 리미트보다 작으면 박스에 충분히 들어가니
    박스갯수를 하나 올린다.

  3. 위 조건이 만족 못하면, 최대값을 줄이면서 경우를 따져보자

첫번째 코드

function movingStuff(stuff, limit) {
  // TODO: 여기에 코드를 작성합니다.
  // 구하고자 하는 변수를 선언하고 
  // 박스 갯수를 구하는 반복문을 작성
  // 처음엔 가장 가벼운 짐과 가장 무거운짐 (최소,최대값 찾기)
  // stuff를 sort함수를 사용해서 최소값을 구한다.
  // 예를 들어 [70, 50, 80, 50]
  let sort = stuff.sort((a,b) => a - b) //[50,50,70,80]

  let count = 0;
  let minNum = 0 // 최소값50
  let maxNum = stuff.length - 1 // 최대값80
  // 리미트 안에서 구해야한다. 
  // 최대값이 최소값보다 같거나 크다.
  
  while(minNum <= maxNum){
    if((sort[minNum] + sort[maxNum]) <= limit){
      minNum++ ; // 최소값 증가 
      maxNum-- ; // 최대값 감소
      count++ ; // 박스개수 증가
    } else { // 무게가 초과 경우
      maxNum-- ;
      count++ ;
    }
  }
  return count;
}

두번째 코드

(여긴 특징이 박스에 두개 들어가면 총 짐에서 박스를 뺀다.)

function movingStuff(stuff, limit) {
  // TODO: 여기에 코드를 작성합니다.
  let twoBox = 0;
  // 오름차순 정렬
  let sortStuff = stuff.sort((a,b) => a - b);
  let minNum = 0;
  let maxNum = sortStuff.length - 1;
  while(minNum < maxNum){
    if((sortStuff[minNum] + sortStuff[maxNum]) <= limit){
      minNum++;
      maxNum--;
      twoBox++;
    } else {
      maxNum--;
    }
  }
  return stuff.length - twoBox;
}

2번문제

현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다.
동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.

예제

// 4000원을 받았을 때 500원짜리 동전 8개를 반환합니다.
const output1 = test1(4000);
console.log(output1); // --> 8

// 4972원을 받았을 때 500원짜리 동전 9개, 100원짜리 동전 4개, 50원짜리 동전 1개, 10원짜리 동전 2개, 1원짜리 동전 2개, 총 18개를 반환합니다.
const output2 = test1(4972);
console.log(output2); // --> 18

생각하자

1.문제에서 필요한 자료를 안줄때가 있다.
간단해서 안주는거다.......
지금 가지고 있다는 동전을 배열에 담아 준다.

앞에서 문제랑 비슷하다.
큰 동전부터 나눠주면 동전의 개수가 최소화가 된다.

풀이

function partTimeJob(k) {
  // TODO: 여기에 코드를 작성하세요.
  // 내림차순 배열을 하나 만든다. 
  // 동전 배열을 만든다. 
  // 예를 들어 4972원
  let coin = [500, 100, 50, 10, 5, 1];
  let count = 0;
  // 반복문으로 조건을 찾아보자.
  // 동전의 갯수와 나머지 식 
  for(let el of coin){
    //동전의 갯수 
    count += parseInt(k / el) // 동전마다 계산
    k = k - (el * parseInt(k / el)) // 계산하고 남은돈
  }
  return count;
}

3번문제

N * N의 크기를 가진 보드판 위에서 게임을 하려고 합니다. 게임의 룰은 다음과 같습니다.

좌표 왼쪽 상단(0, 0)에 말을 놓는다.
말은 상, 하, 좌, 우로 이동할 수 있고, 플레이어가 조작할 수 있다.
조작의 기회는 딱 한 번 주어진다.
조작할 때 U, D, L, R은 각각 상, 하, 좌, 우를 의미하며 한 줄에 띄어쓰기 없이 써야 한다.
예시: UDDLLRRDRR, RRRRR
한 번 움직일 때마다 한 칸씩 움직이게 되며, 그 칸 안의 요소인 숫자를 획득할 수 있다.
방문한 곳을 또 방문해도 숫자를 획득할 수 있다.
보드 밖을 나간 말은 OUT 처리가 된다.
칸 안의 숫자는 0 또는 1이다.
단, 좌표 왼쪽 상단(0, 0)은 항상 0이다.
획득한 숫자를 합산하여 숫자가 제일 큰 사람이 이기게 된다.
보드판이 담긴 board와 조작하려고 하는 문자열 operation이 주어질 때, 말이 해당 칸을 지나가면서 획득한 숫자의 합을 구하는 함수를 작성하세요.

예시

const board1 = [
  [0, 0, 0, 1],
  [1, 1, 1, 0],
  [1, 1, 0, 0],
  [0, 0, 0, 0]
]
const output1 = boardGame(board1, 'RRDLLD');
console.log(output1); // 4

생각하기

보드를 그래프로 옮겨보자

배열은 X,Y를 반대로 생각하면 끝*

  1. 시작 위치는 어디 인가.
    (0,0)
  2. 좌우으로 움직이러면
    x축에서 한칸 더하거나 빼주면 된다.
  3. 상하로 움직이려면
    y축에서 한칸 더하거나 빼주면 된다.
  4. 그리고 보드에 벗어나는 조건은 생각해야한다.
    x,y가 음수 일때 그리고 x,y가 보드길이보다 클때.
    그땐 OUT!

첫번째 문제풀이

function boardGame(board, operation) {
  // TODO: 여기에 코드를 작성하세요.
  // 출발점 (0,0)
  // x = 0
  // y = 0
  // 최종목표는 구하는 변수를 만든다. 
  let score = 0;
  // 출발점
  let x = 0;
  let y = 0;
  // 현재 위치 변수 설정
  let current = board[0][0]
  //반복문으로 움직이는 방향 설정 
  for(let i = 0; i < operation.length; i++){
    if(operation[i] === 'U'){
      y -= 1 , x += 0;
    }
    if(operation[i] === 'D'){
      y += 1 , x += 0;
    }
    if(operation[i] === 'R'){
      y += 0 , x += 1;
    }
    if(operation[i] === 'L'){
       y += 0 , x -= 1;
    }
    //보드가 아웃일때!!!!! 
    if(x < 0 || y < 0 || board.length < y || board.length < x){
      return 'OUT';
    }
    //현재 위치 설정
    current = board[y][x];
    score = score + current;
  }
  return score;
};

두번째 풀이

1.보드의 말 움직임을 객체로 만든다.
2.out여부를 판단하는 함수를 만든다.
3.operation에 따라서 X축과 Y축을 움직이면서 스코어에 점수를 더해준다.

// LOOK UP TABLE을 사용한다면 조건문을 추상화시킬 수 있습니다.
function boardGame(board, operation) {
  // TODO: 여기에 코드를 작성하세요.
  const DIR = {
    'U': [-1, 0],
    'D': [1, 0],
    'L': [0, -1],
    'R': [0, 1]
  }
  const LEN = board.length;
  const isValid = (y, x) => 0 <= y && y < LEN && 0 <= x && x < LEN;

  let Y = 0;
  let X = 0;
  let score = 0;
  for (let i = 0; i < operation.length; i++) {
    const [dY, dX] = DIR[operation[i]];
    Y += dY;
    X += dX;
    if (isValid(Y, X) === false) return 'OUT';
    score += board[Y][X];
  }
  return score;
};

profile
야 나도 개발자 될 수 있어

1개의 댓글

comment-user-thumbnail
2021년 12월 14일

ㅇㅇ

답글 달기