알고리즘..
.
...
알탕 먹고 싶다.
당장히 문제를 푸는것 보단 이해 해야 한다.
--
어떤 수학쌤이 이런말을 했던것이 기억이 난다.
수학을 잘하려면
국어를 잘해야 한다!
문제를 이해를 해야 풀수 있다.!!
알고리즘 또한 문제를 이해를 해야 잘 풀 수 있다.
문해력을 요구하는 문제들도 많다.
간단한 문제를 뭐 되도않게 길게 적어놓고 손에 땀나게 해서
키보드만 고장나게 한다.!!!
지금 딱 말한다.!
그럼 시작하자! 렛츠기릿!
[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
이런 비슷한 문제들이 많이 나올테니
물건을 넣을때 가장 효율적인건 가장 큰거부터 넣고 그 후에 다른거 생각하면 된다.
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;
}
현재 가지고 있는 동전은 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;
}
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를 반대로 생각하면 끝*
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;
};
ㅇㅇ