본문 바로가기
Algorithm29
프로그래머스 부대복귀 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.
프로그래머스 줄 서는 방법 javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다. [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] 사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성.. 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.
백준 구간 합 구하기 2042번 javascript 세그먼트 트리를 쓰면 해결할 수 있는 문제이다. javascript 풀고 실행해보니 5%에서 에러가 뿜뿜 나는데 정신이 혼미해졌다. 반례 예시 찾아보니 1. 세그먼트 트리 범위 // N * 4로 많이 사용 const segmentTree = new Array(N * 4).fill(0); 2. 세그먼트 트리 업데이트 할 때 기존 배열에 값을 넣어줘야지 다음 업데이트 때 두 수의 차이를 반영할 수 있다 const diff = BigInt(c) - arr[b - 1]; // 아래 부분 추가 arr[b - 1] = BigInt(c); 반례 찾아보고 돌려봤는데도 이상이 없어서 python으로 돌려봤는데 정답! 다시보니 정수 크기가 좀 컸다. 그래서 숫자들을 BigInt로 바꿔서 계산하니 정답이 되었다. 세그먼트 .. 2022. 8. 15.
위상 정렬 *** 위상정렬은 방향이 정해져있는 그래프에서 사용할 수 있다. (양방향 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.

티스토리툴바