![]()
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제의 키 포인트는 두가지로 생각한다. 첫 번째, 외각에 있는 요소 체크 후 제거. 이는 테두리에 있는 요소를 확인하는 것은 이 요소가 지게차로 제거할 수 있는지 확인하는 것이다. 나는 -1이라는 값을 이용해 BFS 알고리즘으로 4 방향으로 확인하며 탐색을 진행했다. 두 번째, 제거된 블럭으로 인해 태두리에 위치하게 되는 요소의 계산이다. 예를 들어보자.위의 사진과 같이 물건들이 있다고 가정하자. 명령어는 ["BB", "A"]가 주어졌을때, "BB" 명령어가 먼저 시행되며 해당 물건들에서 B 요소들은 모두 테두리와 상관없이 모두 제거된다. 제거..
문제https://www.acmicpc.net/problem/1753 풀이이번 문제는 다익스트라 알고리즘 문제이다. 필자는 BFS를 이용한 다익스트라 알고리즘 구현을 시도했지만, 시간 초과 에러가 발생했다.이유는 BFS의 탐색 방식에 있다. 필자의 BFS는 큐에 탐색할 경로의 정보를 담고 하나씩 가져오며 완전 탐색을 진행했다. 불필요한 경로까지 검증하면 시간 복잡도가 높아진다.... 이를 해결하기 위해서는 항상 최소의 값을 가져올 수 있는 최소힙을 이용해야 한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim..
문제https://www.acmicpc.net/problem/2606 풀이해당 문제는 DFS와 BFS 풀이 모두 가능한 문제이다. 간단한 문제이기 때문에 DFS와 BFS를 다시 연습하기 위해 풀이했다. BFS 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n');const n = +input.shift();const linked = +input.shift();const arr = input.map(e => e.split(' ').map(Number));const map = {};const ..
문제https://www.acmicpc.net/problem/5972 풀이다익스트라다와 BFS 알고리즘을 이용한 문제이며, 필자는 큐를 이용한 풀이를 진행했다. 1번부터 시작하며 큐에 시작하는 위치를 저장하고 순회를 시작한다. 순회하며 각 지점에 도달하기 까지의 최소 비용을 측정한다. 최단 거리의 경우 st 지점부터 ed 지점까지 소요되는 비용을 더하며 최소 비용을 구한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e);const [n, m] = input.shi..
문제https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이그냥 일반적인 BFS 문제로 처음 파악을 했다. 근데 풀어보니 틀리기도 했고 효율성 검사도 통과하지 않았다.const bfs = (arr, x) => { const start = Array.from({length: arr.length}, (_, i) => [i, x]); for(let i = 0; i = 0 && ny >= 0 && nx 1) continue; ..
문제https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이이번 문제는 최소 비용을로 각 노드를 연결해야 하는 문제이다. BFS 알고리즘을 이용해 인접한 노드를 방문하고 끝 지점까지 연결해야 하며 각 노드까지 연결되는데에 필요한 비용을 DP알고리즘을 이용해 저장한다.(시간 복잡도와 노드와 노드를 연결할 시 비용을 계산) 하지만, 이 문제에서는 한가지 트릭을 추가적으로 생각해야한다. 바로 한 노드로 들어오는 방향까지 생각해야한다. 이유는 커브길을 만들 ..
