[STUDY] 탐욕 알고리즘 문제풀이 1 230901

SKY·2023년 9월 1일

coding_test_study greedy algorithm 부트캠프 탐욕법 알고리즘

JS Coding Test Study

목록 보기

7/20

~54일차~

1. 동전 0

https://www.acmicpc.net/problem/11047

강의에서 제시한 문제 해결 아이디어

각 화폐 단위는 서로 배수관계
가치가 큰 동전은 가치가 작은 동전들의 합으로 표현 가능

① 모든 화폐 단위를 내림차순으로 정렬
② 화폐의 단위를 확인하여, 해당 화폐로 나눌 때의 몫을 더하기

제출 답안

let fs = require('fs');
let input = fs.readFileSync('./input.txt').toString().split('\n');

//동전 n종류, 총 합 k
let [n, k] = input[0].split(' ').map(Number);

// 동전 종류 n개만큼 가져오기
let arr = []
for(let i = 1; i <=n; i++) {
  arr.push(Number(input[i]))
};

//내림차순 정렬
arr.sort((a,b) => b-a);

let coin = [];

//몫을 정수로 구해서 coin 배열에 넣어주고, 나머지를 다시 반환
for (let x = 0; x < arr.length; x++) {
  if (arr[x] < k) {
  coin.push(parseInt(k / arr[x]))
  return k %= arr[x]
  }
}

//coin 배열의 값 모두 더해서 출력
let answer = 0;
for (let i = 0; i < coin.length; i++ ) {
  answer += coin[i];
}

console.log(answer);

-오답 !

터미널 자체에서는 에러 메세지가 뜨지 않았는데, 뜯어봤을 때 몫을 구하는 for문에서 동작하지 않은 걸 알 수 있었다.

for (let x = 0; x < arr.length; x++) {
  if (arr[x] < k) {
    console.log(arr[x])
    }}

이렇게 작성했을 때는 화폐들이 정상적으로 출력이 되었고,

  if (arr[x] < k) {  
  console.log(parseInt(k / arr[x]))
  return k %= arr[x]
  }

push 대신 콘솔을 찍어 봤을 땐 4 하나만 나왔다.
아무래도 coin.push(parseInt(k / arr[x])) return k %= arr[x] 여기서 연결이 잘 되지 않는 듯 싶었다.

정답 예시

let fs = require('fs');
let input = fs.readFileSync('./input.txt').toString().split('\n');

let n = Number(input[0].split(' ')[0]);
let k = Number(input[0].split(' ')[1]);

let arr = [];
for(let i = 1; i <=n; i++) arr.push(Number(input[i]));

let cnt = 0;
// 총개수 n개에서 n-1 = 뒤에서부터 시작, 내림차순이 된다
for (let i = n-1; i>=0; i--) { 
  cnt += parseInt(k/arr[i]); // 해당 동전 몇개 사용 (몫)
  k%= arr[i]; // 해당 동전으로 거슬러 준 뒤 남은 금액 (나머지)
}

console.log(cnt);

정답예시와 비교
내 코드는 빈 배열에 몫을 하나씩 넣고 나중에 더 하는 방식이라 코드도 길어졌는데, 다음에는 정답 예시처럼 굳이 빈 배열을 만들 필요 없이 for문 안에서 더하는 걸 해봐야겠다.

2. ATM

https://www.acmicpc.net/problem/11399

강의에서 제시한 문제 해결 아이디어

필요한 시간의 합의 최솟값 계산
-> 오름차순 정렬 후 누적 합 계산

제출 답안

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

// 사람 수
let n = input[0].split(' ').map(Number);
// 각 사람이 돈을 인출하는데 걸리는 시간
let arr = input[1].split(' ').map(Number);
//시간 적게 소요되는 사람 우선 정렬
arr.sort((a,b) => a-b);

let answer = 0;

for (let i = 0; i < n; i++) { 
  arr.reduce((acc, cur) => acc += cur) // 누적해서 누적값 리턴(으로 생각)
  answer += acc;  //Error - acc 밖으로 뺄 수 없음
}
console.log(answer);

-오답 : 누적 계산을 너무 어렵게만 생각했다.

정답 예시


let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');


let n = Number(input[0]);
let arr = input[1].split(' ').map(Number);

arr.sort((a,b) => a-b);

let answer = 0;
let summary = 0;

for (let i = 0; i < n; i++) { 
  summary += arr[i];
  answer += summary;
}
console.log(answer);

3. 잃어버린 괄호

https://www.acmicpc.net/problem/1541

강의에서 제시한 문제 해결 아이디어

덧셈과 뺄셈 연산자로만 구성된 수식이 있을 때, 괄호를 적절히 넣어 값을 최소화 한다.
뺄셈 연산자를 기준으로 최대한 많은 수를 묶는다.

제출 답안

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

let minus = input[0].split('-');

// 미완성 미제출

-오답 : 뺄셈 제거 후, 나온 값을 소괄호로 감싸는 방식을 생각했고 제대로 구현할 방법을 못찾고 시간이 되어 미제출로 마무리.

정답 예시

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

let groups = input[0].split('-'); // [ '55', '50+40' ]
let answer = 0;

for (let i = 0; i < groups.length; i++) {
  // 각 그룹 내부에서 덧셈 연산 적용
  let cur = groups[i].split('+').map(Number).reduce((a,b)=> a+b);
  if(i == 0) answer += cur // 첫번째 그룹은 항상 덧셈
  else answer -= cur; // 두번째 그룹부터 뺄셈
}
console.log(answer);