9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N-Queen문제 풀이 복습차원에서 적습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim() const N = +input; let answer = 0; next(0, Array(N).fill(0)) console.log(answer) function next(row,board) { if(row === N){ answer++ return } for(let i=0; i
풀이 방법 dfs를 통한 백트래킹 문제입니다. 코드는 아래와 같습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n"); const N = +input.shift(); const data = input.map((v) => v.split(" ").map(Number)); const eggsState = data.map((v) => v[0]); let answer = 0; dfs(0, eggsState); console.log(answer); function dfs(index, arr) { //순회를 마치면 탈출 if (index === N) { const count = arr.fil..
1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제풀이 방법 25명중 무작위로 7명을 뽑습니다. 7명중 4명 이상이 ‘이다솜파’라면 dfs함수를 실행합니다. dfs함수는 무작위로 뽑힌 7명이 인접한 자리에 앉아있는지 확인하는 함수입니다. dfs를 활용하여 인접한지 확인할 수 있습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n") .map((v) => v.split("")); let a..
7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 꼭 알아야 하는 개념인 LCS를 활용한 문제입니다. LCS는 2차원 DP로 푸는 경우가 많아서 이 문제를 처음 봤을 때 고민을 많이 했습니다. 복습 차원에서 글을 적습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n") const N = +input.shift() const dp = Array(N+1).fill(0) let max = 0; fo..
알고리즘 문제를 푸는데, LCS문제가 종종 나와서 이번에 한번 개념을 확실하게 잡고자 글을 적어봅니다. LCS (Longest Common Subsequence) 두 개의 문자 서열 X,Y가 주어졌을 때, X와 Y에서 공통으로 나타나는 부분 문자 서열을 찾는 알고리즘. 부분 서열의 길이가 최대가 되도록 하는 문자서열을 찾는다. 문제를 푸는 방법? 단순하게 풀기 브루트 포스(Brute-Force Approach) X의 모든 부분 서열에서 Y의 부분 서열인 것의 길이를 구한다음 최댓값을 구한다. X의 부분 서열의 개수는 지수 시간 복잡도를 가진다 따라서 이렇게 푸는 방법은 옳지않다. X = { x1, x2, x3 … x(m-1), x(m) } Y ={ y1, y2, y3 … y(n-1), y(n) } Z =..
8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 푸는데 상당히 오래 걸렸습니다. 5시간 정도 걸렸습니다.. 처음 문제를 풀었을 때 15점에서 멈춰서 어디서 잘못된 건지 한참을 찾았는데, 처음 풀이방법이 맞긴 맞아서 코드를 새로 짰습니다. 개인적으로 특히 그리디 문제를 풀 때 코드가 더러워 지는데, 그리디 연습을 많이 해야겠네요.. 풀이 방법 풀이 자체는 간단합니다. 데이터를 정렬합니다. 출발 마을을 기준으로 오름차순으로 정렬을 해줍니다. 출발 마을이 같을 경우 도착 마을이 빠른 순서대로 정..