공부/Javascript
패스트캠퍼스 JavaScript 코딩테스트 강의 2주차
leejinwoo1126
2023. 4. 24. 10:28
반응형
온라인 코드 테스트 사이트
https://www.jdoodle.com/execute-nodejs-online/
ch04. 그리디(탐욕) 알고리즘
추후 예정
문제 목록
더보기
문제 1-1) 동전0
문제 1-2) ATM
문제 1-3) 잃어버린 괄호
문제 2-1) 설탕배달(실버4)
문제 2-2) A -> B(실버2)
문제 2-3) 수들의 합
문제 2-4) 신입사원
문제 3-1) 주유소
문제 3-2) 회의실 배정
문제 3-3) 풍선 맞추기(골드5)
문제 3-4) 피보나치(실버1)
문제 4-1) 박 터뜨리기(실버4)
문제 4-2) 회문(골드5)
문제 4-3) 박스 채우기(골드3)
ch05. 이진 탐색
| 순차탐색 | 이진탐색 |
| - 리스트 안에 특정 데이터 찾기 위해 앞에서 부터 순차적으로 하나씩 확인하여 탐색 - 시간 복잡도 : O(N) |
- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색함 - 시간 복잡도 : O(logN) |
5-1. 이진 탐색(Binary Search)
- 정렬이 보장된 리스트에서 탐색 범위를 이분 하면서 원하는 값을 찾는다
- 이분 탐색에서 자주 하는 실수
- 탐색할 배열을 정렬하지 않는 경우
- 탐색 범위를 나타내는 변수의 정의와 부등호 등을 잘못 쓰는 경우
- 범위설정, 초기화 실수
이진 탐색 활용 대표 사례
- 매우 넓은 탐색 범위(억 단위, -10억 ~ 10억) 에서 최적의 해를 찾아야 하는 경우
- 데이터를 정렬한 뒤에 "다수의 쿼리(query)"를 처리해야 하는 경우
While Loop 활용한 이진 탐색 구현 방법
function binarySearchByWhileLoop(arr, target, left, right) {
while(left <= right) {
const mid = parseInt((left + right) / 2);
if(arr[mid] === target) return mid;
else if(arr[mid] < target) left = mid + 1;
else right = mid -1;
}
return -1;
}
const target = 7;
const arr = [1, 3, 5, 7, 9];
let result = binarySearchByWhileLoop(arr, target, 0, arr.length - 1);
if(result === -1) console.log('원소가 존재하지 않습니다.');
else console.log(`${result + 1} 번째 원소입니다.`); // 결과 : 4 번째 원소 입니다. (인덱스 0에 있는 원소 = 1번째 원소)
Recursive Function(재귀 함수) 활용한 이진 탐색 구현 방법
function binarySearchByRecursive(arr, target, left, right) {
if(left > right) return -1;
const mid = parseInt((left + right) / 2);
if(arr[mid] === target) return mid;
else if(arr[mid] < target) return binarySearchByRecursive(arr, target, mid + 1, right);
else return binarySearchByRecursive(arr, target, left, mid - 1);
}
const target = 1;
const arr = [1, 3, 5, 7, 9];
let result = binarySearchByRecursive(arr, target, 0, arr.length - 1);
if(result === -1) console.log('원소가 존재하지 않습니다.');
else console.log(`${result + 1} 번째 원소입니다.`); // 결과 : 1 번째 원소 입니다. (인덱스 0에 있는 원소 = 1번째 원소)
(이미지 삽입)
5-2. 정렬된 배열에서 특정한 값을 가지는 원소의 개수 구하기
정렬된 리스트의 범위 내에서 하한선(lowerBound)과 상한선(upperBound) 함수를 사용하여 특정 원소의 개수 구함
- lowerBound(array, target) : 정렬된 배열 array 에 x를 넣을 '가장 왼쪽 인덱스'를 반환
- upperBound(array, target) : 정렬된 배열 array 에 x를 넣을 '가장 오른쪽 인덱스'를 반환
리스트 내 원소의 개수 = upperBound 인덱스 - lowerBound 인덱스
lowerBound(), upperBound() 는 다른 알고리즘 풀이와 응용하여 사용 가능하므로 잘 이해 해두기 (ex. LIS 최장 증가 부분수열)
구현 코드
/*
정렬된 순서를 유지하면서 배열에 삽입할 가장 왼쪽 인덱스 반환
ex. 예시에서 1을 찾는 경우 lowerBound : 1
*/
function lowerBound(arr, target, left, right) {
while(left < right) {
const mid = parseInt((left + right) / 2);
if(arr[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return right;
}
/*
정렬된 순서를 유지하면서 배열에 삽입할 가장 오른족 인덱스 반환
ex. 예시에서 1을 찾는 경우 lowerBound : 2
*/
function upperBound(arr, target, left, right) {
while(left < right) {
const mid = parseInt((left + right) / 2);
if(arr[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return right;
}
/*
arr.length 하는 이유는 3을 찾을 경우
lowerBound : 3, upperBound : 4 (=arr.length) 생각해보기
*/
function countByRange(arr, leftValue, rightValue) {
const leftIndex = lowerBound(arr, leftValue, 0, arr.length);
const rightIndex= upperBound(arr, rightValue, 0, arr.length);
return rightIndex - leftIndex;
}
const arr = [1, 2, 2, 3];
console.log(countByRange(arr, 1, 1)); // 1의 개수 : 1개
console.log(countByRange(arr, 2, 2)); // 2의 개수 : 2개
console.log(countByRange(arr, 3, 3)); // 3의 개수 : 1개
배열 [1, 2, 2, 3] 있을 때
*1의 경우
- lowerBound = 0, upperBound = 1
*2의 경우
- lowerBound = 1, upperBound = 3
*3의 경우
- lowerBound = 3, upperBound = 4 (arr.length)
5-3. 매개 변수 탐색 (Parametric Search)
- 이진 탐색 조건 : 변경할 (최적화할) 값 x에 대해 f(x)가 단조 증가 혹은 단조 감소
- 단조 증가 함수( = 비내림차순) : x <= y 이면 f(x) <= f(y) 인 경우
- 매개 변수 탐색이란 ? 최적화 문제를 결정 문제 (예 / 아니오) 로 바꾸어 해결 하는 기법
- 문제를 거꾸로 푸는 것이기 때문에 통창렬이 요구됨
- 키워드 : "~의 최댓값을 구하시오." 또는 "~의 최솟값을 구하시오"
문제 풀이
문제1) 예산(실버3)
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]); // 지방의 수
const data = input[1].split(' ').map(Number);
const m = Number(input[2]); // 총 예산
let left = 0;
let right = data.reduce((a, b) => Math.max(a, b));
let result = 0;
while(left <= right) {
const mid = parseInt((left + right) / 2);
let total = 0;
for(let d of data) {
total += Math.min(d, mid);
}
if(total > m) {
right = mid - 1;
} else {
result = mid;
left = mid + 1;
}
}
console.log(result);
문제2) 나무자르기(실버3)
부등호 방향 잘 확인:(
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0].split(' ')[0]); // 나무의 수
const m = Number(input[0].split(' ')[1]); // 집으로 가져갈 나무의 길이
const data = input[1].split(' ').map(Number);
let left = 1;
let right = 2e9;
let result = 0;
while(left <= right) {
const h = parseInt((left + right) / 2);
let total = 0;
for(let t of data) {
if(h < t) total += (t - h);
}
console.log(total);
/*
if(total < m) {
right = mid - 1;
} else {
left = mid + 1;
result = mid;
}
*/
if(total >= m) {
left = h + 1;
result = h;
} else {
right = h - 1;
}
}
console.log(result);
문제3) 랜선 자르기(실버2)
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const k = Number(input[0].split(' ')[0]); // 이미 가지고 있는 랜선의 개수
const n = Number(input[0].split(' ')[1]); // 필요한 랜선의 개수
const data = [];
for(let i = 1; i <= k; i++) {
data.push(Number(input[i]));
}
let left = 1;
let right = data.reduce((a, b) => Math.max(a, b));
let result = 0; // 만들 수 있는 최대 랜선의 길이
while(left <= right) {
const l = parseInt((left + right) / 2);
let total = 0;
for(let len of data) {
total += parseInt(len / l);
}
if(total >= n) { // 만들 수 있는 랜선의 개수가 충분한 경우 길이 늘이기 (최대 길이 찾기 위해)
left = l + 1;
result = l;
} else { // 만들 수 있는 랜선의 갯수가 부족한 경우 길이 줄이기
right = l - 1;
}
}
console.log(result);
문제4) 숫자 카드 2(실버4)
lowerBound, upperBound 구현해서 범위로 개수 구하면 됨 => 부등호 헷갈리면 [1, 2, 2, 3]에서 1의 개수 찾던 경우 생각해보기
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
function lowerBound(arr, target, left, right) {
while(left < right) {
const mid = parseInt((left + right) / 2);
if(arr[mid] >= target) right = mid;
else left = mid + 1;
}
return right;
}
function upperBound(arr, target, left, right) {
while(left < right) {
const mid = parseInt((left + right) / 2);
if(arr[mid] > target) right = mid;
else left = mid + 1;
}
return right;
}
const n = Number(input[0]); // 상근이가 가지고 잇는 숫자 카드 개수
const card1 = input[1].split(' ').map(Number); // 카드2
card1.sort((a, b) => a - b);
const m = Number(input[2]);
const card2 = input[3].split(' ').map(Number); // 카드2
let result = "";
for(let c2 of card2) {
const leftIdx = lowerBound(card1, c2, 0, card1.length);
const rightIdx = upperBound(card1, c2, 0, card1.length);
result += `${rightIdx - leftIdx} `;
}
console.log(result);
문제5) 병사 배치하기(실버2)
LIS (최장 증가 부분 수열)에 대한 개념을 몰라서 풀 수 없었던 문제
- dp 배열 마지막 값과 비교시 큰 경우 마지막에 추가
- 그게 아닌 경우 이분 탐색(lowerBound)을 사용해서 삽입할 적절한 위치를 찾아 값을 대체
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
function lowerBound(arr, target, left, right) {
while(left < right) {
const mid = parseInt((left + right)/ 2);
if(arr[mid] >= target) right = mid;
else left = mid + 1;
}
return right;
}
let n = Number(input[0]); // 병사의 수
let data = input[1].split(' ').map(Number);
data.reverse();
const dp = [0];
for(let s of data) {
if(dp[dp.length - 1] < s) {
dp.push(s);
} else {
const leftIdx = lowerBound(dp, s, 0, dp.length);
dp[leftIdx] = s;
}
}
console.log(n - (dp.length - 1)); // LIS가 되기 위해 제외되야 할 병사 수
주의. 알고리즘이 끝난 후 결과가 LIS (최장 증가 부분 수열) 개수를 뜻하는 것이지 결과 자체가 정확한 LIS는 아님
참고. https://withhamit.tistory.com/197
최장 감소 수열 (LDS), 최장 증가 수열 (LIS)
최장 감소 수열 (LDS: Longest Decreasing Sequence)과 최장 증가 수열(LIS: Longest Increasing Sequence)에 대해 알아보겠습니다. 저는 코드를 최장 감소 수열에 대해서 짰기 때문에 최장 감소 수열을 설명하겠습
withhamit.tistory.com
문제6) K번째 수 (골드2)
문제 설명, 문제 풀이를 위한 아이디어 무엇하나 생각나지 않았다. ("2차원 배열을 1차원 배열로 만들어서 정렬한 다음 K번째 수를 어떻게 구할 수 있지?") 그나마 설명듣고 손으로 그려보고 나서야 이해를 할 수 있었다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]); // 배열의 크기
const k = Number(input[1]); // k번째 수
let left = 1;
let right = 10 ** 10; // 10^10
let result = 0;
while(left <= right) {
const mid = parseInt((left + right) / 2);
let totalCnt = 0;
for(let i = 1; i <= n; i++) {
totalCnt += Math.min(parseInt(mid / i), n); // parseInt 안하면 답이 틀리게 나옴
}
//console.log(`left : ${left}, right : ${right}, mid : ${mid}, total : ${totalCnt}`);
if(totalCnt >= k) {
right = mid -1;
result = mid;
} else {
left = mid + 1;
}
}
console.log(result);
K번째 숫자(값)가 S라 할 때, 전체 숫자 중에서 S보다 작거나 같은 숫자의 개수가 K개 보다 작으면 안됨
= 이진 탐색을 했을 때 mid보다 작거나 같은 데이터 수가 k개 이상이 되는 조건을 만족하는 최소 mid 값을 구함
Ch06. 백트래킹
| 순열(Permitation) | 조합(Combination) |
| 서로 다른 n개 중에서 r개를 중복없이 뽑는 것 (이때 순서 구분 있음) |
서로 다른 n 개 중에서 r개를 중복없이 뽑는 것 (이때 순서 구분 x) |
| 만약 1,2,3,4 중 2개를 중복없이 뽑을 때 1,2 2,1 .. 와 같이 순서에 따라 의미를 가지므로 4P2 = 4 * 3 = 12 |
만약 1,2,3,4 중 2개를 중복 없이 뽑을 때 1,2 1,3 1,4 2,3 2,4 3,4 와 같이 순서 구분 없이 동일하게 보므로 (1,2 = 2,1) 4C2 = 4 * 3 / 2! = 6 |
참고. https://www.youtube.com/watch?v=hwd7B9fbrpA
문제 1-1) N과 M(1) (실버3)
- nPm : n 개중 M개를 선택할 때 중복 없이 순서를 고려하여 나열한 순열 (1,2,3 과 1,3,2 는 다르게 본다 => 순서 의미 가짐)
강의 답안의 경우 DFS 실행시 배열의 인덱스를 담아주고, 결과에서 해당 인덱스 값을 뽑아서 처리해주는 방식
// 내 답안
function dfs(depth) {
if(depth === m) {
result += selected.join(' ');
result += '\n';
return;
}
for(let i = 1; i <= n; i++) {
if(visited[i]) continue;
selected.push(i);
visited[i] = true;
dfs(depth + 1);
visited[i] = false;
selected.pop();
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, m] = input[0].split(' ').map(Number);
const selected = [];
const visited = new Array(n + 1).fill(false);
let result = '';
dfs(0);
console.log(result);
//강의 답안
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
let [n, m] = input[0].split(' ').map(Number); // 1부터 N까지 자연수 중에서 중복 없이 N개를 고른 수열
let arr = []; // 순열을 계산하고자 하는 원소(element)가 담긴 배열
for(let i = 1; i <= n; i++) arr.push(i);
let visited = new Array(n).fill(false); // 각 원소 인덱스(index)별 방문 여부
let selected = []; // 현재 순열에 포함된 원소 (element)
let answer = "";
function dfs(arr, depth) {
if(depth === m) { // 최대 depth까지 내려왔을 때 모든 순열을 확인하는 부분
let result = []; // 순열 결과 저장용 테이블
for(let i of selected) result.push(arr[i]);
for(let x of result) answer += `${x} `;
answer += "\n";
return;
}
for(let i = 0; i < arr.length; i++) { // 하나씩 원소 인덱스(index)를 확인하며
if(visited[i]) continue; // 중복을 허용하지 않으므로 이미 처리된 원소라면 무시
selected.push(i); // 현재 원소 선택
visited[i] = true; // 현재 원소 방문 처리
dfs(arr, depth + 1); // 재귀 함수 호출
selected.pop(); // 현재 원소 선택 취소
visited[i] = false; // 현재 원소 방문 처리 취소
}
}
dfs(arr, 0); // 실행
console.log(answer);
문제 1-2) 모든 순열 (실버 3)
function dfs(depth) {
if(depth === n) { // 정답인 경우
result += selected.join(' ');
result += '\n';
return;
}
for(let i = 1; i <= n; i++) {
if(visited[i]) continue;
selected.push(i);
visited[i] = true;
dfs(num + 1);
visited[i] = false;
selected.pop();
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]);
const selected = [];
const visited = new Array(n + 1).fill(false);
let result = '';
dfs(0);
console.log(result);
문제 1-3) 0 만들기 (골드5)
- 중복 순열 문제 (n파이r => n^r)
- 1~N까지의 수가 주어졌을 때 세가지 연산(+, -, 공백)을 사용하여 0이 되는 모든 수식을 찾아야 함
- 테스트 케이스 및 자연수 N의 최대값은 9
- 3개의 연산 중에서 중복포함 연속적으로 N번 선택해야 하므로 경우의 수는 3^8 (9개 숫자 사이에 들어갈 수 있는 연산은 8개까지)
- N = 4일때 경우의 수는 3^3 = 27
참고. eval()
직접 코드 작성해서 틀린 이유가 operator 연산자 순서가 달라서 였음 .. 수정 전 => ['+', '-', ' ']
// 내 답안
function dfs(limit, depth) {
if(depth === limit - 1) {
let formula = '';
// selected에 연산자 순서가 다 들어가 있음
for(let i = 1; i <= limit; i++) {
if(i === limit) {
formula += `${i}`;
} else {
formula += `${i}${operators[selected[i - 1]]}`;
}
}
const value = eval(formula.replace(/\s/g, '')); // 정규표현식으로 공백 제거
if(value === 0) {
result += formula;
result += '\n';
}
return;
}
for(let i = 0; i < 3; i++) {
selected.push(i);
dfs(limit, depth + 1);
selected.pop();
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
let selected;
let result;
const operators = [' ', '+', '-']; // 순서가 안 맞아서 틀림;
const n = Number(input[0]);
for(let i = 1; i <= n; i++) {
const _num = Number(input[i]);
selected = [];
result = '';
dfs(_num, 0);
console.log(result);
}
// 강의 답안 참고--------------------------------------------------------------
function dfs(result, n, depth) {
if(depth === n - 1) {
let formula = '';
for(let i = 0; i < n-1; i++) {
formula += `${arr[i]}${result[i]}`;
}
formula += `${arr[n-1]}`; // 마지막 숫자는 여기에서 처리*
const value = eval(formula.split(' ').join('')); // 공백 제거 후 수식 연산*
if(value === 0) console.log(`${formula}`);
return;
}
// 연산자 순서 틀리면 답이 다르게 나옴
for(let i of [' ', '+', '-']) {
result.push(i);
dfs(result, n, depth + 1);
result.pop();
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
let arr;
const testCase = Number(input[0]);
for(let i = 1; i <= testCase; i++) {
const _num = Number(input[i]);
arr = [];
for(let i = 1; i <= _num; i++) arr.push(i);
dfs([], _num, 0);
console.log(); // 줄바꿈용
}
문제 2-1) N과 M(2) (실버3)
1부터 N까지 자연수 중에서 중복 없이 N개를 고른 조합
// 내 답안
function dfs(depth, start) {
if(depth === m) {
result += selected.join(' ');
result += '\n';
return;
}
for(let i = start; i <= n; i++) {
selected.push(i);
dfs(depth + 1, i + 1);
selected.pop();
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, m] = input[0].split(' ').map(Number);
const selected = [];
let result = '';
dfs(0, 1);
console.log(result);
//강의 답안
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
let [n, m] = input[0].split(' ').map(Number);
let arr = [];
for(let i = 1; i <= n; i++) arr.push(i);
let visited = new Array(n).fill(false);
let selected = [];
let answer = "";
function dfs(arr, depth, start) {
if(depth === m) { //결과 처리
let result = [];
for(let i of selected) result.push(arr[i]);
for(let x of result) answer += `${x} `;
answer += "\n";
return;
}
for(let i = start; i < arr.length; i++) {
if(visited[i]) continue; // 중복을 허용하지 않으므로 이미 처리된 원소라면 무시
selected.push(i); // 현재 원소 선택
visited[i] = true;
dfs(arr, depth + 1, i + 1);
selected.pop(); // 현재 원소 선택 취소
visited[i] = false;
}
}
dfs(arr, 0, 0);
console.log(answer);
문제 2-2) N과 M(3) (실버3)
- 중복 허용하는 순열 출력 문제, visited 배열만 없으면 됨
function dfs(depth) {
if(depth === m) {
result += selected.join(' ');
result += '\n';
return;
}
for(let i = 1; i <= n; i++) {
selected.push(i);
dfs(depth + 1);
selected.pop();
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, m] = input[0].split(' ').map(Number);
const selected = [];
let result = '';
dfs(0);
console.log(result);
문제 2-3) N과 M(4) (실버3)
- 중복 조합을 구하는 문제
- 비내림차순 (= 중복을 허용한 오름차순이란 의미) 순열로 '문제 2-2' 에서 조금 변형만 하면 됨
// 내 답안
function dfs(depth) {
if(depth === m) {
result += selected.join(' ');
result += '\n';
return;
}
for(let i = 1; i <= n; i++) {
// 현재의 값이 이전 값보다 작다면 continue
if(selected[selected.length - 1] > i) continue;
selected.push(i);
dfs(depth + 1);
selected.pop();
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, m] = input[0].split(' ').map(Number);
const selected = [];
let result = '';
dfs(0);
console.log(result);
// 강의 답안
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
let [n, m] = input[0].split(' ').map(Number);
let arr = [];
for(let i = 1; i <= n; i++) arr.push(i);
let selected = [];
let answer = "";
function dfs(arr, depth, start) {
if(depth === m) { // 조합(combination) 결과 저장용 테이블
let result = [];
for(let i of selected) result.push(arr[i]); // 인덱스에 대한 값을 결과에 담음
for(let x of result) answer += `${x} `;
answer += "\n";
return;
}
for(let i = start; i < arr.length; i++) {
selected.push(i); // 인덱스를 넣어주고
dfs(arr, depth + 1, i);
selected.pop();
}
}
dfs(arr, 0, 0);
console.log(answer);
문제 3-1) 외판원 순회 2 (실버2)
여러 부분에서 실수가 많아 시간을 배로 소비했다.
1) 인접 행렬 선언 초기화
2) 시작번호를 0으로 하려다가 dfs 반복문, 변수 선언 부분이 꼬여 버림 => 연산 편의 위해 1번 인덱스부터 시작하도록 하기 !
2) 조건에 충족할 때 2차원 배열 A[i][j] 가 코드로 이해가 되지 않아 시간 소요
3) 그리고 마지막 출발 지점(1)으로 돌아갈 때 finalCost에서 adjacencyMatric[current][1] 지정하지 않아 시간 소요
let minValue = 1e7;
function dfs(depth) {
if(depth === n - 1) {
let totalCost = 0;
let current = 1; // 1번 노드에서 출발 지정일 때*
for(let next of selected) {
let cost = adjacencyMatrix[current][next]; // current -> next 노드로 가기 위한 비용
if(cost === 0) return; // 비용이 0이면 갈 수 없다는 뜻
totalCost += cost;
current = next;
}
let finalCost = adjacencyMatrix[current][1]; // 현재 노드에서 1번 노드로 가는 cost 확인*
if(finalCost === 0) return;
totalCost += finalCost;
minValue = Math.min(minValue, totalCost);
return;
}
// 1번 노드부터 출발한다 가정할 때 2,3,4/2,4,3/3,4,2/3,2,4/4,2,3/4,3,2 순열 나옴
for(let i = 2; i <= n; i++) {
if(visited[i]) continue;
selected.push(i);
visited[i] = true;
dfs(depth + 1);
visited[i] = false;
selected.pop();
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]);
const adjacencyMatrix = [];
for(let i = 0; i <= n; i++) adjacencyMatrix.push([0]);
/*
[
[ 0 ],
[ 0, 0, 10, 15, 20 ],
[ 0, 5, 0, 9, 10 ],
[ 0, 6, 13, 0, 12 ],
[ 0, 8, 8, 9, 0 ]
]
*/
for(let i = 1; i <= n; i++) {
const line = input[i].split(' ').map(Number);
for(let j = 0; j < n; j++) {
adjacencyMatrix[i].push(line[j]);
}
}
let visited = new Array(n).fill(false);
let selected = [];
dfs(0);
console.log(minValue);
// 두번째 풀이
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
// 초기화
const n = Number(input[0]);
const matrix = Array.from({length : n + 1}, () => [0]); // new Array().fill() 을 할 경우 얕은 복사되므로 이렇게 함
for(let i = 1; i <= n; i++) {
const line = input[i].split(' ').map(Number);
for(let j = 0; j < line.length; j++) matrix[i].push(line[j]);
}
const visited = new Array(n + 1).fill(false);
const selected = [];
let result = 10 ** 10;
function dfs(depth) {
if(depth === n - 1) {
let value = 0;
let current = 1;
for(let next of selected) {
const cost = matrix[current][next];
if(cost === 0) return;
value += cost;
current = next;
}
const lastCost = matrix[current][1]; // 1번 기준일 때 마지막 노드에서 1로 돌아가는 비용
if(lastCost !== 0) {
value += lastCost;
result = Math.min(result, value);
}
return;
}
for(let i = 2; i <= n; i++) {
if(visited[i]) continue;
visited[i] = true;
selected.push(i);
dfs(depth + 1);
selected.pop();
visited[i] = false;
}
}
// 실행 : 1번부터 start한다고 가정
dfs(0);
console.log(result); // 결과 35 (1 -> 1로 돌아오는 최소 비용)
문제 3-2) 도영이가 만든 맛있는 음식(실버2)
- 조합 문제
- 입력 때문에 2차원 배열을 어떻게 처리해야 되는지 싶어 아이디어가 떠오르지 않았음
- 단순히 2차원 배열은 결과에서만 사용하고 인덱스로만 조합을 구해서 처리하면 되었고, 곱의 신맛과 합의 단맛의 차의 최소값을 찾는 문제였다. ( 문제를 읽고 이해하고 아이디어 떠오르는 능력이 부족하구나.. )
function dfs(arr, depth, start) {
if(depth >= 1) {
let totalA = 1; // 신맛 곱
let totalB = 0; // 쓴만 합
for(let i of selected) {
totalA *= arr[i][0];
totalB += arr[i][1];
}
result = Math.min(result, Math.abs(totalA - totalB));
}
for(let i = start; i < arr.length; i++) {
selected.push(i);
dfs(arr, depth + 1, i + 1);
selected.pop();
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]);
const arr = [];
for(let i = 1; i < n + 1; i++) {
arr.push(input[i].split(' ').map(Number));
}
const selected = [];
let result = 10 ** 10;
dfs(arr, 0, 0);
console.log(result);
문제 3-3) 로또(실버2)
- 가능한 모든 조합의 수를 구함( 6 <= K <= 13)
- 예) 8C6 = 8 * 7 * 6 * 5 * 4 * 3 / 6! = 28가지
문제 풀이 형식은 거의 동일한데, 변수 선언이나 출력형식이 맞지 않아 시간 소비함
// 내 답안 1
function dfs(arr, depth, start) {
if(depth === 6) {
for(let i of selected) result += `${arr[i]} `;
result += '\n';
return;
}
for(let i = start; i < arr.length; i++) {
if(visited[i]) continue;
visited[i] = true;
selected.push(i);
dfs(arr, depth + 1, i +1);
selected.pop();
visited[i] = false;
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
let visited;
let selected;
let result;
for(let i = 0; i < input.length; i++) {
const data = input[i].split(' ').map(Number);
if(data[0] === 0) break;
const n = data[0];
const arr = data.slice(1);
visited = new Array(n).fill(false);
selected = [];
result = '';
dfs(arr, 0, 0);
console.log(result);
}
// 내 답안 2 ---------------------------------------------------------
let result;
let arr;
let selected;
let visited;
function dfs(arr, cnt, start) {
if(cnt === 6) {
result += selected.join(' ');
result += '\n';
return;
}
for(let i = start; i < arr.length; i++) {
if(visited[i]) continue;
selected.push(arr[i]);
visited[i] = true;
dfs(arr, cnt + 1, i + 1);
visited[i] = false;
selected.pop();
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
for(let i = 0; i < input.length; i++) {
const data = input[i].split(' ').map(Number);
if(data[0] === 0) break;
const n = data[0];
arr = data.slice(1);
selected = [];
visited = new Array(n).fill(false);
result = '';
dfs(arr, 0, 0);
console.log(result);
}
문제 4-1) N-Queen(골드4)
n = 4 일때 답이 2
// 내 답안
/*
이전 행의 퀸의 위치를 고려하려 유효성 체크
1. 같은 행 또는 열에 있는지
2. 이전 행의 퀸의 대각선 방향에 있는지
*/
function isAvailable(row, col) {
for(let [_r, _c] of selected) {
if(row === _r || col === _c) return false;
if(Math.abs(row - _r) === Math.abs(col - _c)) return false;
}
return true;
}
function dfs(row) {
if(row === n) {
result++;
return;
}
for(let col = 0; col < n; col++) {
if(!isAvailable(row, col)) continue;
selected.push([row, col]);
dfs(row + 1);
selected.pop();
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]);
const selected = [];
let result = 0;
dfs(0);
console.log(result);
// 강의 답안
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]); // 전체 맵의 크기
let queens = []; // 현재 체스판에 놓인 퀸 (queen)의 위치 정보들
function possible(x, y) { // (x,y) 위치에 퀸을 놓을 수 있는지 확인
for(let [a, b] of queens) { // 현재까지 놓았던 모든 퀸(queen)의 위치를 하나씩 확인하며
if(a === x || b === y) return false; // 행 또는 열이 같다면
if(Math.abs(a - x) === Math.abs(b - y)) return false; // 대각선에 위치한다면
}
return true;
}
let cnt = 0;
function dfs(row) {
if(row === n) cnt += 1; // 퀸을 N개 배치할 수 있는 경우 카운트
for(let i = 0; i < n; i++) { // 현재 행(row)에 존재하는 열을 하나씩 확인하며
if(!possible(row, i)) continue; // 현재 위치에 놓을 수 없다면 무시
queens.push([row, i]); // 현재 위치에 퀸을 놓기
dfs(row + 1);
queens.pop(); // 현재 위치에서 퀸을 제거하기
}
}
dfs(0);
console.log(cnt);
문제 4-2) 알파벳(골드4)
- 2차원 배열내에 범위를 벗어나지 않고, 이미 조회한 알파벳이 아닌 경우 깊이 우선 탐색하여 최대 깊이를 출력하면 되는 문제
첫번째 코드의 경우 답은 나오나 제출시 시간초과 발생함
- 알파벳 사용 여부 확인시 0(1) 시간 복잡도를 보장해야 하는데, Set.has()가 그렇지 않았음
- 비슷한 상황으로 예전에 Array.prototype.indexOf()로 문제 풀이 했을 때 시간초과 발생했던 기억남
// 시간 초과 발생 => 원인 Set.has()
function dfs(depth, x, y) {
maxDepth = Math.max(maxDepth, depth); // 최대 깊이 (=결과값)
for(let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if(visited.has(arr[nx][ny])) continue;
visited.add(arr[nx][ny]);
dfs(depth + 1, nx, ny);
visited.delete(arr[nx][ny]);
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [r, c] = input[0].split(' ').map(Number); // r : 행, c : 열
const arr = [];
for(let i = 1; i <= r; i++) arr.push(input[i]);
// 네 방향
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const visited = new Set(); // 방문한적 있는 알파벳 집합
let maxDepth = 0;
// 기준 (0,0) 부터 시작
visited.add(arr[0][0]);
dfs(1, 0, 0);
console.log(maxDepth);
알파벳은 26개이고 A~Z 유니코드는 65 ~ 90에 해당 (아래 위키 주소 참고)
String.prototype.charCodeAt()로 String에 대한 유니코드를 확인 가능
// 통과
function dfs(depth, x, y) {
maxDepth = Math.max(maxDepth, depth);
for(let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
const uniCodeIndex = arr[nx][ny].charCodeAt() - 65;
if(visited[uniCodeIndex]) continue;
visited[uniCodeIndex] = true;
dfs(depth + 1, nx, ny);
visited[uniCodeIndex] = false;
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [r, c] = input[0].split(' ').map(Number); // r : 행, c : 열
const arr = [];
for(let i = 1; i <= r; i++) {
arr.push(input[i]);
}
// 네 방향
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const visited = new Array(26).fill(false);
let maxDepth = 0;
// 기준 (0,0) 부터 시작
visited[arr[0][0].charCodeAt() - 65] = true;
dfs(1, 0, 0);
console.log(maxDepth);
참고.
Set.has()와 Array.inclueds()시간 복잡도
문제 4-3) 부등호(실버1)
1) 0~9 숫자 10개 중에 부등호의 갯수가 k 개일때 k+1 개 만큼 숫자를 뽑아 나열 (중복x)
2) depth === k + 1 만족할 때 부등호 조건이 만족하는 지 확인하고 최대값과 최소값을 구함
순열이기 때문에 제일 처음 조건을 만족하는게 최소값이고, 마지막으로 만족하는게 최대값
k = 2일때 10P3 = 10 * 9 * 8 = 720개 순열이 구해짐
(시작) 021 031 032 041 042 ... 894 895 896 897 (끝)
let minValue = '';
let maxValue = '';
function dfs(depth) {
if(depth === k + 1) {
let isSatisfied = true;
for(let i = 0; i < k; i++) {
if(data[i] === '>') {
if(selected[i] < selected[i + 1]) isSatisfied = false;
} else if(data[i] === '<') {
if(selected[i] > selected[i + 1]) isSatisfied = false;
}
}
// 순열이니깐 첫번째 값이 가장 작은 값이고 마지막이 제일 큰값이 됨
if(isSatisfied) {
const value = selected.join('');
if(minValue === '') minValue = value;
else maxValue = value;
}
return;
}
// 0~9 숫자 중에 k + 1개 뽑아서 순서있게 나열(순열)
for(let i = 0; i < 10; i++) {
if(visited[i]) continue;
selected.push(i);
visited[i] = true;
dfs(depth + 1);
selected.pop();
visited[i] = false;
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const k = Number(input[0]); // 부등호 개수
const data = input[1].split(' '); // <> 부등호 배열
const visited = new Array(10).fill(false);
const selected = [];
dfs(0);
console.log(`${maxValue}\n${minValue}`);
학습 후기 ( + 인증 사진)
2주차에는 본격적으로 알고리즘 문제 풀이에 들어갔는데, 과거에 한번 풀어봤을 뿐 다시보니 익숙치 않아 시간 소모가 컸다.
- 탐욕(그리디) 알고리즘의 경우 문제에 대한 이해도나 아이디어 생각이 어려움 => 추후 복습하여 약점 보완
- 이진 탐색의 경우 부등호 방향이 헷갈렸는데 이젠 구분이 되고, LIS (최장 증가 수열) 를 구현하는 방법에 대해 처음 알게 됨
- 백트래킹의 경우 재귀함수 호출 방식이 낯설었으나, 순열과 조합에 개념을 재학습하고 문제 풀이하다보니 깨달음을 얻음(아래 문제 참고)
문제 3-1) 외판원 순회 2 (실버2)
문제 3-2) 도영이가 만든 맛있는 음식(실버2)
입력 형태가 다른데 결과적으로 line을 인덱스라 보고 그 인덱스 번호에 따른 순열, 조합을 구해서 조건에 맞으면 결과 처리하는 방식으로 풀이하면 되는거였다! 😃
https://fastcampus.co.kr/dev_online_upjscodingtest
UPSKILL : Javascript 코딩테스트 131개 예제 & CS지식으로 끝내기 | 패스트캠퍼스
25시간 대비 과정 / '코테 레전드' 유튜버 강사님께 핵심만 배우고 빠르게 합격하세요.
fastcampus.co.kr
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
반응형