본문 바로가기
JavaScript17
프로그래머스 부대복귀 javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정점 사이의 간선의 길이가 1로 정해져 있다. 이게 유동적이면 bfs로 해결할 수 없지만 (다익스트라, 플로이드 와샬 등 사용으로 해결) 1로 일정하기에 bfs로 풀었다. 1. graph에 경로들을 담아두고 2. bfs 돌리면서 visited의 최소 시간으로 방문한 값을 저장하다. 3. map 돌리면서 출력 function solution(n, roads, sources, destination) { const graph = new Array(n+1).fill(null).map(_=>[]); for(let [a.. 2022. 10. 23.
프로그래머스 카운트 다운 javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dp를 사용해서 [50, *1, *2, *3] 4가지 경우의 수를 따져보면 된다. target은 최대 10만이므로 dp 배열은 넉넉하게 30만으로 만들어줬다. 다트 던지는 횟수는 늘어남으로 현재 dp 위치 던진 다트 개수 + 1을 dp의 얻은 점수 위치와 비교한다. 만약현재 "dp 위치 던진 다트 개수 + 1" 이 더 작으면 교체한다. 만약 같다면 싱글과 볼을 최대한 많이 던지는 방법을 찾아야 하므로 싱글과 볼 일때 카운트를 +1 해서 둘중에 큰값을 삽입한다. if(dp[i+(addIdx)][0] === dp.. 2022. 10. 10.
백준 1162 도로포장 javascript 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 일반적인 dijkstra에 도로포장 유무를 추가하면 된다. dp 배열을 원래 1차 배열로 했으나 도로 포장 K개 이므로 dp[N][K] 를 생성한다. // 도로를 포장하지 않을 경우 if (totalW < dp[arrV][pqPavedRoad]) { dp[arrV][pqPavedRoad] = totalW; pq.add([totalW, arrV, pqPavedRoad]); } // 도로를 포장 할 경우 if (pqPavedRoa.. 2022. 9. 9.
프로그래머스 멀리 뛰기 javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 점화식은 dp[i] = dp[i-1] + dp[i-2] 이다. function solution(n) { var answer = 0; const dp = new Array(n).fill(0); dp[0] = 1; dp[1] = 2; for(let i = 2; i < n; i++){ dp[i] = (dp[i-1] + dp[i-2]) % 1234567; } return dp[n-1]; } 조금 반대로 풀게 되면 아래와 같은 코드로도 가능하다. function solution(n) { var answer = 0; c.. 2022. 9. 5.
프로그래머스 방문 길이 javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 0,0에서 위, 오른쪽, 아래, 왼쪽 으로 가는데 평범한 탐색 문제인줄 알고 2d array로 방문체크를 하려했는데 set을 사용하는게 더 편할거 같아 바꿨습니다. set에 추가하는데 a점에서 b점으로 가는경우와 b점에서 a점으로 가능 경우 둘 다 저장했습니다. function solution(dirs) { var answer = 0; const isValid = (x,y) => 0 2022. 9. 3.
프로그래머스 숫자 블록 javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 소수를 구하는 문제이다. 그렙시는 길이가 1,000,000,000인 도로에 1번 블록부터 시작하여 "10,000,000"번 블록까지 구하는 문제이다. "10,000,000"번 블록까지 구하는 것이기에 "10,000,000" 블록을 넘어가는 수에 대해서는 연산하지 않으면 된다. 해당 부분이 없으면 효율성에서 에러가 났다. function solution(begin, end) { const answer = []; const isPrime = (i) =>{ const sqrt = Math.sqrt(i); for(l.. 2022. 9. 3.
프로그래머스 N-Queen javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다. 체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요. 제한사항 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다. n은 12이하의 자연수 입니다. .. 2022. 8. 28.
백준 배 1092 javascript 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 예제 4번 10 // N 크레인 개수 11 17 5 2 20 7 5 5 20 7 // 크레인이 들 수 있는 무게 배열 5 // 박스 개수 18 18 15 15 17 // 박스들의 무게 무게 제한이 있는 N 개의 크레인으로 M개의 박스를 몇분안에 옴길 수 있는가? 각 박스의 무게는 따로 주어진다. 크레인 N개의 배열을 오름차순으로 정렬하고 박스 M개 배열을 오름차순으로 정렬한다. 들 수 있는 무게가 제일 큰 크레인에게 가장 큰 무게를 가진 박스부터.. 2022. 8. 24.
프로그래머스 등산 코스 정하기 javascript , python 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 파란색 정점이 입구, 빨간색 정점이 산봉우리, 검은색 정점은 쉼터이다. 각 정점사이의 간선은 걷는 시간을 의미한다. 입구에서 산봉우리까지 갔다가 다시 돌아올 때 해당 루트가 지나간 간선들의 최대값이 가장 작은 루트를- 구하여라. 루트는 여러가지가 있다. 1 => 2 => 4 => 5 => 4 => 2 => 1 // 각 사이의 간선은 [3, 2, 3, 3, 2, 3] // 간선들의 최대 값은 3 1 => 2 => 4 => 6 => 5 => 4 => 2 => 1 // 각 사이의 간선은 [3, 2, 1, 1, 3,.. 2022. 8. 23.
위상 정렬 *** 위상정렬은 방향이 정해져있는 그래프에서 사용할 수 있다. (양방향 X) *** 1. 진입 차수가 0인 정점을 찾아 Queue에 넣는다. 2. Queue에서 정점 하나를 뺀후, 해당 정점에 연결된 간선을 제거한다. 3. 2번을 통해 간선이 제거된 정점이 진입차수가 0이라면 Queue에 추가한다. 4. 1번으로 다시 간다. V = 정점 E = 간선 시간 복잡도는 O(V+E) 만약 사이클이 있는 경우는 아래 그림과 같다 N = 6 일 경우 결과 배열에 총 6개가 아닌 [1, 6] 단 2개만 들어있을 것이다. 나머지는 진입 차수가 1보다 크기 때문에다. 아래는 배운 위상정렬로 풀 수 있는 문제이다. 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주.. 2022. 8. 5.
백준 임계경로 1948번 javascript 위상정렬을 사용하여 풀 수 있는 문제입니다. 다만 역발상이 필요합니다. 아래 그림과 같이 위상정렬 + 위상 정렬 반대가 경로 최대값(12) 이라면 해당 정점들 사이의 간선은 1분도 쉬지 않고 달려야 하는 간선입니다. const fs = require("fs"); const stdin = ( process.platform === "linux" ? fs.readFileSync("/dev/stdin").toString() : `7 9 1 2 4 1 3 2 1 4 3 2 6 3 2 7 5 3 5 1 4 6 4 5 6 2 6 7 5 1 7` ).split("\n"); const input = (() => { let line = 0; return () => stdin[line++]; })(); const N = +.. 2022. 8. 5.
백준 후위 표기식 1918번 javascript 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 문제의 예제는 통과했었지만 아래 반례처럼 b+c*d 의 경우 틀려서 찾느라 고생했다. 원리는 1. for문을 돌며 하나씩 stack 에 넣으며, 2. stack에서 소괄호가 완성되면 3. 해당 부분을 change 함수에 넣어 계산 후 4. 다시 stack에 넣어주는 방식이다. // https://www.acmicpc.net/problem/1918 const fs = require("fs"); const stdin = ( process.platform === .. 2022. 7. 19.

티스토리툴바