문제https://www.acmicpc.net/problem/2579 풀이처음 이 문제를 풀때는 BFS로 접근했지만 나는 풀이 방법을 찾지 못했다... 시간초과 에러가 발생했다.... 그래서 순수하게 동적 계획법을 사용해 풀이하기로 결정했다. 이 문제를 잘 보면 특정 패턴이 보일 것이다. n 번째에 도달하는 방법은 두가지가 있다. 첫 번째로는 n-1 번째에서 한칸 뛰어넘어 온 경우이고, 두 번째는 n-2 번째에서 두칸을 넘어온 경우이다. 이때 두칸을 넘어온 경우는 문제가 되지 않지만, 한 칸을 넘어온 경우는 3칸을 연속해서 넘으면 안된다는 제한이 있다. 위와 같은 제한을 피하는 방법은 n-3칸에서 두칸 넘고 n-1칸에서 한칸 넘는 방법이 있다. 코드const input = require('fs') .r..
코테준비
문제https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이이번 문제는 최소 비용을로 각 노드를 연결해야 하는 문제이다. BFS 알고리즘을 이용해 인접한 노드를 방문하고 끝 지점까지 연결해야 하며 각 노드까지 연결되는데에 필요한 비용을 DP알고리즘을 이용해 저장한다.(시간 복잡도와 노드와 노드를 연결할 시 비용을 계산) 하지만, 이 문제에서는 한가지 트릭을 추가적으로 생각해야한다. 바로 한 노드로 들어오는 방향까지 생각해야한다. 이유는 커브길을 만들 ..
문제https://www.acmicpc.net/problem/1926 풀이이 문제는 BFS 알고리즘을 이용해 그래프 탐색을 진행해야 한다. 그림은 연결되어 있기 때문에 연결된 노드를 탐색하며 방문했음을 기록해야합니다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Number));const [y, x] = input.shift();const map = input;const check = Array.from({ length: y }, () ..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42861# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해당 문제는 크루스칼 알고리즘을 이용해 최단 신장 트리를 구하며 풀이하는 문제이다.크루스칼 알고리즘을 이 문제를 통해 처음 알게되었는데, BFS 그래프 탐색인데 cost를 오름차순으로 정렬해 부모를 비교해 처리하는 알고리즘이라 생각한다. 코드const find = (parent, x) => { if (parent[x] === x) { return x; } return parent[x]..
문제https://school.programmers.co.kr/learn/courses/30/lessons/ 풀이해당 문제는 BFS를 이용한 다익스트라다 문제이며, 처음 문제를 풀때는 주어지는 sources별로 마지막 도착지인 destination까지의 거리를 측정했었다. 하지만 이렇게 풀게 되면 시간 초과가 발생한다.function solution(n, roads, sources, destination) { const answer = []; const road = Array.from({length: n + 1}, () => []); const level = Array.from({length: n + 1}, () => Infinity); for(let i = 0; i fal..
문제https://school.programmers.co.kr/learn/courses/30/lessons/161988# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이이 문제를 보고 펄스 수열이라는 말이 눈에 거슬렸다. -1과 1을 번갈아가며 곱셈되는 동작을.... 펄스 동작이 1부터 곱해지냐 아니면 -1부터 곱해지냐는 정해져 있는 것이다. 첫번째 풀이는 전부 1 혹은 -1 씩 번갈아 가며 요소들에 곱해준 배열을 구한 뒤 누적합을 구했었지만, 이렇게 풀이한 경우 부분 수열의 합을 구할 수 없기에 통과하지 못했다.function solution(sequ..
