문제https://www.acmicpc.net/problem/14888 풀이해당 문제는 완전탐색 문제이며, 필자는 DFS와 DP를 이용해 풀이했다. 숫자의 순서는 바뀌면 안되기에 연산자를 DP 배열에 담아가며 연산을 검증을 진행했다. 이전에 풀었던 스타트와 링크 문제와 비슷한 흐름으로 해결할 수 있었다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Number))const N = input.shift()[0];const toolNum =..
dp
문제 설명 https://www.acmicpc.net/problem/14501문제 풀이 방법이 문제는 DP를 이용한 풀이와 DFS를 이용한 재귀 함수로의 풀이가 가능한 문제이다.처음 이 문제를 봤을 때는 조합을 이용해 최대로 받을 수 있는 급여를 뽑아낸다 였지만, 이 문제에서 원하는 것은 근무일 수 혹은 상담 시간의 조합이 아니라 받을 총 급여의 최대값이라 DP를 이용해 풀었다. 나는 DP를 이용해 풀이를 진행해보았다. 최근 풀었던 가장 긴 바이토닉 부분 수열 문제에서 아이디어를 얻었다. 스케줄을 순회하며 급여를 체크하는 방향으로 설계했다. 이 문제에서는 주어진 스케줄의 역순으로 순회하며 값을 구했다.문제에서 처음 상담을 시작한 날짜에 따라 받게되는 급여의 최대값이 달라지기 때문이다. 정답 코드const..
문제https://www.acmicpc.net/problem/11054풀이이번 문제는 DP를 이용한 LIS 알고리즘 문제이다.처음 이 문제를 보고 바이토닉 수열이라는 개념에 대해 이해하기 쉽지 않았다... 각 자리수에서 좌/우로 증가, 감소하는 수들의 개수의 최대값을 구하는 문제이다. 좌에서 우로 이동하며 증가하는 수의 연속과 우에서 좌로 이동하며 증가하는 수의 연속을 측정한다. 이 두가지 과정의 결과를 이용해 바이토닉 수열의 최대값을 구할 수 있다. 각 과정에서 나온 증가되는 수의 개수는 dp1, dp2에 담기며, 두 배열에서 인덱스가 같은 값들을 더해주고, 이 중 최대 값을 제출한다. 코드const input = require('fs') .readFileSync(process.platform ===..
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12905?language=javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 방법 저장된 값을 사용하는 DP 알고리즘을 이용했다. 표를 순회하며 해당 칸의 숫자가 1이면 좌, 좌 대각선 위, 위 의 숫자 중 가장 작은 수에 1을 더해 재할당 해준다. 이렇게 재할당된 수를 다시 이용하며 DP 알고리즘을 적용한다. 그리고 answer의 값과 해당 칸의 수를 비교한 뒤 큰 값을 answer에 할당해준 다음 반복문이 끝나면..
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/136797 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 방법 이 문제를 처음 봤을 때는 BFS를 이용한 최단 기간 로직을 이용해 답을 구하는 줄 알았다. 하지만 경우의 수가 양손으로 먼저 나눠 2, number의 길이가 10만이기에 2^100000의 경우의 수가 나오기 때문에 BFS로는 시간 초과가 발생할거 같다. 그래서 이전 계산 결과를 이용하는 DP 알고리즘을 이용하기로 했다. dp[i][j]에서 i는 왼손, j는 오른손의 ..
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12900 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 길이가 1일 때는 1개의 경우, 2일 때는 2, 3일 때는 3, 4일 때는 5, 5일 때는 8 이 문제는 피보나치 수열을 이용한 문제로써, DP를 이용해 문제를 풀었다. 코드 function solution(n) { let arr = Array(n+1).fill(0); arr[0] = 1; arr[1] = 1; for(let i=2; i
