패스트캠퍼스 JavaScript 코딩테스트 강의 2주차

온라인 코드 테스트 사이트

https://replit.com/

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) 

• 정렬이 보장된 리스트에서 탐색 범위를 이분 하면서 원하는 값을 찾는다
• 이분 탐색에서 자주 하는 실수 
  • 탐색할 배열을 정렬하지 않는 경우
  • 탐색 범위를 나타내는 변수의 정의와 부등호 등을 잘못 쓰는 경우 
  • 범위설정, 초기화 실수

 

이진 탐색 활용 대표 사례 

1. 매우 넓은 탐색 범위(억 단위, -10억 ~ 10억) 에서 최적의 해를 찾아야 하는 경우
2. 데이터를 정렬한 뒤에 "다수의 쿼리(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

*조건식 부등호가 헷갈릴때는 0, 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)

 

 

문제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 2,1 1,3 3,1 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);

 

참고. 

String.prototype.charCodeAt()

위키 백과 - 유니코드

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을 인덱스라 보고 그 인덱스 번호에 따른 순열, 조합을 구해서 조건에 맞으면 결과 처리하는 방식으로 풀이하면 되는거였다! 😃

 

백트래킹 - 로또 문제 풀이

 

이진탐색 - K번째 수 문제 증명

백트래킹 - 외판원 순회(2)

---

https://fastcampus.co.kr/dev_online_upjscodingtest

UPSKILL : Javascript 코딩테스트 131개 예제 & CS지식으로 끝내기 | 패스트캠퍼스

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.