문제https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이이번 문제는 최소 비용을로 각 노드를 연결해야 하는 문제이다. BFS 알고리즘을 이용해 인접한 노드를 방문하고 끝 지점까지 연결해야 하며 각 노드까지 연결되는데에 필요한 비용을 DP알고리즘을 이용해 저장한다.(시간 복잡도와 노드와 노드를 연결할 시 비용을 계산) 하지만, 이 문제에서는 한가지 트릭을 추가적으로 생각해야한다. 바로 한 노드로 들어오는 방향까지 생각해야한다. 이유는 커브길을 만들 ..
dp
문제https://school.programmers.co.kr/learn/courses/30/lessons/161988# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이이 문제를 보고 펄스 수열이라는 말이 눈에 거슬렸다. -1과 1을 번갈아가며 곱셈되는 동작을.... 펄스 동작이 1부터 곱해지냐 아니면 -1부터 곱해지냐는 정해져 있는 것이다. 첫번째 풀이는 전부 1 혹은 -1 씩 번갈아 가며 요소들에 곱해준 배열을 구한 뒤 누적합을 구했었지만, 이렇게 풀이한 경우 부분 수열의 합을 구할 수 없기에 통과하지 못했다.function solution(sequ..
문제https://school.programmers.co.kr/learn/courses/30/lessons/12971# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이문제의 첫 인상은 0번 요소와 1번 요소를 선택했을 때 1개씩 건너뛰어 선택한 조합을 구하면 되지 않을까 라는 생각을 했다. 하지만, 이 경우 한개를 건너뛴 선택이 더 클 수 있다고 생각했다. 그래서 다른 접근법을 생각해봤다. 우선 문제의 제한 조건을 보고 2중 이상의 for문을 사용한 접근법은 시간복잡도상 초과될 것이라 생각해 DP를 이용해 메모이제이션을 구현해 풀이를 진행했다. 문제의 ..
문제https://www.acmicpc.net/problem/11053 풀이이 문제는 LIS 알고리즘과 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();const arr = input.shift();const temp = Array.from({ length: n..
문제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 =..
문제 설명 https://www.acmicpc.net/problem/14501문제 풀이 방법이 문제는 DP를 이용한 풀이와 DFS를 이용한 재귀 함수로의 풀이가 가능한 문제이다.처음 이 문제를 봤을 때는 조합을 이용해 최대로 받을 수 있는 급여를 뽑아낸다 였지만, 이 문제에서 원하는 것은 근무일 수 혹은 상담 시간의 조합이 아니라 받을 총 급여의 최대값이라 DP를 이용해 풀었다. 나는 DP를 이용해 풀이를 진행해보았다. 최근 풀었던 가장 긴 바이토닉 부분 수열 문제에서 아이디어를 얻었다. 스케줄을 순회하며 급여를 체크하는 방향으로 설계했다. 이 문제에서는 주어진 스케줄의 역순으로 순회하며 값을 구했다.문제에서 처음 상담을 시작한 날짜에 따라 받게되는 급여의 최대값이 달라지기 때문이다. 정답 코드const..
