const input = fs
.readFileSync("/dev/stdin")
.toString()
.trim()
.split("\n")
.map((v) => v.split(" ").map((v) => parseInt(v)));
const solution = (input) => {
const N = +input;
const DP = Array.from({ length: N + 1 }, () => 0);
for (let i = 2; i < N + 1; i++) {
DP[i] = DP[i - 1] + 1; // 1을 빼서 1로 만드는 연산의 횟수로 우선 설정
if (i % 2 === 0) {
// 2로 나눠진다면,
DP[i] = Math.min(DP[i], DP[i / 2] + 1); // 1을 빼서 1로 만드는 연산의 횟수와 2로 나눠 1로 만드는 횟수 중 더 작은 경우로 선택.
}
if (i % 3 === 0) {
DP[i] = Math.min(DP[i], DP[i / 3] + 1);
}
}
return DP[N];
};
console.log(solution(input)); // 3
N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.
1+2+3-4×5÷6 = 1
1÷2+3+4-5×6 = 12
1+2÷3×4-5+6 = 5
1÷2×3-4+5+6 = 7
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
// 백준 제출시
// const address="/dev/stdin"
// VSC 테스트시
const address = "./input.txt";
const input = require("fs")
.readFileSync(address)
.toString()
.trim()
.split("\n")
.map((v) => v.split(" ").map(Number));
const getOperations = (arr) => {
const operations = ["+", "-", "*", "/"];
operations.forEach((v, idx) => {
let amount = arr[idx];
for (let j = 0; j < amount; j++) {
operations.push(operations[idx]);
}
});
return operations;
};
function solution(input) {
const [N, A, amount] = input;
const operations = getOperations(amount);
const results = [];
let result = Number.MAX_SAFE_INTEGER;
let check = Array(N).fill(0);
const recursion = (idx) => {
if (idx === N - 1) return;
const copy = [...A];
let tmpOp = operations.slice(0, 2);
copy.splice(idx + 1, 0, tmpOp[0]);
copy.splice(N, 0, tmpOp[1]);
let tmp = operations.shift();
operations.push(tmp);
const test = eval(copy.join(""));
results.push(test);
};
recursion(0);
let min = Math.min(...results);
let max = Math.max(...results);
let answer = `${min}\n${max}`;
return answer;
}
console.log(solution(input));
2-2.연산자 배열의 위치를 바꾼다.
const changeArrayOrder = function(list, targetIdx, moveValue) {
// 배열값이 없는 경우 나가기
if (list.length < 0) return;
// 이동할 index 값을 변수에 선언
const newPosition = targetIdx + moveValue;
// 이동할 값이 0보다 작거나 최대값을 벗어나는 경우 종료
if (newPosition < 0 || newPosition >= list.length) return;
// 임의의 변수를 하나 만들고 배열 값 저장
const tempList = JSON.parse(JSON.stringify(list));
// 옮길 대상을 target 변수에 저장하기
const target = tempList.splice(targetIdx, 1)[0];
// 새로운 위치에 옮길 대상을 추가하기
tempList.splice(newPosition, 0, target);
return tempList;
};
풀이
시도 끝에 결국 실패. 여전히 재귀로 구현하는 것은 아직 어렵다.
// 백준 제출시
// const address="/dev/stdin"
// VSC 테스트시
const address = "./input.txt";
const input = require("fs")
.readFileSync(address)
.toString()
.trim()
.split("\n")
.map((v) => v.split(" ").map(Number));
const getOperations = (arr) => {
const operations = ["+", "-", "*", "/"];
operations.forEach((v, idx) => {
let amount = arr[idx];
for (let j = 0; j < amount; j++) {
operations.push(operations[idx]);
}
});
return operations;
};
function solution(input) {
const [N, A, amount] = input;
const operations = getOperations(amount);
const results = [];
let result = Number.MAX_SAFE_INTEGER;
let check = Array(N).fill(0);
const recursion = (idx) => {
if (idx === N - 1) return;
const copy = [...A];
let tmpOp = operations.slice(0, 2);
copy.splice(idx + 1, 0, tmpOp[0]);
copy.splice(N, 0, tmpOp[1]);
let tmp = operations.shift();
operations.push(tmp);
const test = eval(copy.join(""));
results.push(test);
};
recursion(0);
let min = Math.min(...results);
let max = Math.max(...results);
let answer = `${min}\n${max}`;
return answer;
}
console.log(solution(input));
- 12131213 처럼 딱히 규칙이 있지도 않고고, 1 <= N <= 80 으로 범위가 큰 수가 아니므로 완전탐색이 가능하다.
- 우선 수열이 좋은 수열인지(같은 순서가 연속해서 반복되지 않는지) 판단해야 한다. 해당 블로그를 참조하였다.
1211 => 길이 4, 1자리 비교, 나쁜 수열
1212 => 길이 4, 1자리 비교, 좋은 수열 1212 => 길이 4, 2자리 비교, 나쁜 수열
123123 => 길이 6, 1자리 비교, 좋은 수열 123123 => 길이 6, 2자리 비교, 좋은 수열 123123 => 길이 6, 3자리 비교, 나쁜 수열
- 해당 접근 방식을 코드로 짠다. 재귀를 이용해 전체 탐색을 했다.
시도
1차 시도
결과: 틀렸습니다
// 백준 제출시
// const address="/dev/stdin"
// VSC 테스트시
const address = "./input.txt";
const input = require("fs").readFileSync(address).toString().trim().split("\n");
const solution = (input) => {
const N = +input;
let stop = false;
let min = Number.MAX_SAFE_INTEGER;
const isGoodSequence = (str) => {
let len = str.length;
let loop = len / 2;
let start = len - 1;
let end = len;
for (let i = 1; i <= loop; i++) {
if (str.substring(start - i, end - i) === str.substring(start, end))
return false;
start -= 1;
}
return true;
};
const recursion = (len, str) => {
if (stop) return;
if (len === N) {
stop = true;
console.log(str);
min = min > Number(str) ? Number(str) : min;
}
// 수열은 1,2,3 중 하나로 이루어져 있다.
for (let i = 1; i <= 3; i++) {
if (isGoodSequence(str + i)) recursion(len + 1, str + i);
}
};
// 가장 작은 수를 구하는 것이므로 첫번째 자리는 항상 "1"이 되어야하고, 따라서 따로 탐색할 필요 x
recursion(1, "1");
return min;
};
console.log(solution(input));
2차 시도
결과: 맞았습니다!!
const address="/dev/stdin"
const input = require("fs").readFileSync(address).toString().trim().split("\n");
const solution = (input) => {
const N = +input;
let stop = false;
const isGoodSequence = (str) => {
let len = str.length;
let loop = len / 2;
let start = len - 1;
let end = len;
for (let i = 1; i <= loop; i++) {
if (str.substring(start - i, end - i) === str.substring(start, end))
return false;
start -= 1;
}
return true;
};
const recursion = (len, str) => {
if (stop) return;
if (len === N) {
stop = true;
console.log(str);
}
// 수열은 1,2,3 중 하나로 이루어져 있다.
for (let i = 1; i <= 3; i++) {
if (isGoodSequence(str + i)) recursion(len + 1, str + i);
}
};
// 가장 작은 수를 구하는 것이므로 첫번째 자리는 항상 "1"이 되어야하고, 따라서 따로 탐색할 필요 x
recursion(1, "1");
};
solution(input);
분석
왜 min 부분을 삭제하니 통과한 걸까?
우선 굳이 min 이 필요 없었다. 차례대로 작은수부터 대입하니까 반복문이 끝나기전 제일 먼저이자 마지막으로 찍힌 수가 어차피 가장 작은 수이기 때문이다.
1차 풀이도 틀리지는 않았는데 틀렸던 이유는 정답(min)의 출력타입이 number 였기 때문이다. 정답으로 제출한 코드 마지막 부분만 console.log(Number(string)) 으로 쳤더니 틀렸다고 나온다. 출력 타입도 str 이어야 하는 구나.
나보다 속도가 적게 나온 다른 사람 코드 분석
1. 좋은 수열인지 판별하는 함수에서 substring 메소드가 아닌 slice 메서드를 사용
2. 재귀 함수에서 정답을 도출할 때 string 대신 array 를 사용
3. 재귀 함수에서 백트래킹시 조건문을 좋은 수열일 경우에만 진행이 아닌 나쁜 수열일 경우 반복문을 패스하도록 설정.
const fs = require('fs');
// /dev/stdin
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map((v)=> v.split(" ").map((v)=> parseInt(v)))
// 숫자 1, 2, 3으로만 이루어지는 수열이 있다.
// 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면,
// 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.
// 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다.
function solution (N){
const arr = [1,2,3]
const result = []
const dfs = (depth, number = '') => {
if(result.length > 0) return
if (depth === N) {
result.push(number)
return
}
for(let i = 0; i < arr.length; i++) {
const nextArray = number + arr[i].toString()
if(isBad(nextArray)) continue
dfs(depth+1, nextArray)
}
}
dfs(0)
return result[0]
}
function isBad (str) {
for (let i = 1; i <= str.length/2; i++) {
const last = str.slice(-i)
const before = str.slice(-i*2, -i)
if (last === before) return true
}
return false
}
console.log(solution(...input[0]))
주어진 n 에서 n/2 만큼 스타트팀의 경우의 수를 구한다. 스타트팀을 구하면 남은 인원을 링크팀에 배치한다.
각 팀의 능력치를 구해 합의 차가 가장 작은 경우의 수를 구한다.
문제 접근
스타트팀 n 에서 n/2 를 순서에 상관없이 뽑는 조합의 문제이다.
ex) n = 6일 때 [1,2,3] 로 스타트팀을 구성한다면, [1,2,3] 이나 [2,1,3]이나 [3,1,2] 나 순서에 상관 없이 팀의 능력치는 각 팀원들로 만들 수 있는 모든 부분 집합 (x,y) 쌍의 합, 즉, (1,2)+(2,1)+(2,3)+{3,2)+(1,3)+(3,1) 이 될 것이기 때문이다.
2023년부터는 인턴과 기업 코딩테스트로 공부 방향을 잡았다. 어딜 가도 1차 관문이 되는 코딩테스트가 중요한 기회 때 발목 잡는 걸 원치 않았다.
알고리즘 공부 시작, 지난 2주 돌아보기
1월 알고리즘 학습 계획표
2023 목표를 인턴과 기업 코딩테스트로 잡고, 어딜 가서든 1차 관문이 되는 코딩테스트의 ‘기본’을 1,2월안에 마무리 하기로 했다. 3,4월에는 본격적으로 기출을 풀며 여름방학/하반기 인턴 코테 지원(4~5월 지원)을 준비하고 싶었기 때문이다. 그리하여 2월까지 세운 러프한 계획은 이러했다:
1월: 강의와 함께 빈출 알고리즘 핵심은 제대로 익혀두기(이코테 2021)
2월: 백준 추천 50제 풀며 1월 배운 내용 복습 + 보강
3월: 우테캠, 카카오, 토스 등 국내 기업 코딩테스트의 흐름을 주도하는 기업의 기출문제 풀어보기
4월: 2차 관문인 과제 코테 준비 시작
우선 이코테 2021 강의를 완강 + 80% 이해 및 체화를 목표로 1월 계획을 세웠다. 나는 정말 노베이스 상태에서 시작했기 때문에 전반적으로 어떻게 흘러가고 어떤 것들이 있는지 직접 한 번 훑고 싶었다. 지난 2주는 그런 시간이었다.
그리디, 완전 탐색, 그리고 그래프 탐색(dfs, bfs)였다. dfs,bfs 는 중요하다는 말을 하도 많이 들어 감이 안잡혔지만 최대한 이해하고 넘어가려 했다. (관련 노션 보러가기)
회고를 쓰며 찾아보니 판교로 가는 길에서는 1주일 한 개념씩, 2~3문제를 풀어볼 것을 권한다. 예정보다 3일을 더 투자하여 (5,6,7일) 예제를 확실히 이해하고 추가로 백준 문제를 풀었다. 더 많은 문제를 풀었으면 좋았겠다는 아쉬움이 어쩔 수 없이 남는다. 하지만 카페 글을 참조해보니 오히려 이정도가 딱 맞았다는 생각이 든다. 외려 1주에 2개념을 잡았던 초기 계획이 불필요하게 빡세다는 느낌도 든다. 이에 따라
Keep
- 무조건 문제 풀이보다 중요한 건 개념 이해
Problem
- 딱히 문제는 아니었지만... 한 개념 한 주씩 파는 것과 어떻게 다를지 다른 사람의 조언도 반영해볼 것.
- 예상했던 것보다 느슨해진다는 것
Try
- 한 개념 한 주씩: 두 개념 한 주씩 하던 지난 주와 후에 비교해볼 것
- 한 달 스프린트로 스터디를 개설하여 함께 뛰는 이가 있을 때 어떻게 달라질 수 있는지 비교해볼 것
- 불안요소를 글로써 가시화하고 제거할 수 있는 대책을 세우자.
다음 스텝은?
1. 한 개념 한 주씩 양치기 + 체화
다음 주부터는 본격적으로 양치기에 들어가려 한다. 지난 2주가 이코테 강의 위주의 전체 흐름 잡기 + 개념 익히기였다면, 다음 5주는 백준50제 위주의 양치기 체화 과정이 목표이다.
