문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이번 문제는 탐색이다. 하지만 입력되는 배열의 길이가 100만으로 매우 긴 모습을 알 수 있다. 이렇게 입력이 큰 문제의 경우 시간복잡도를 고려한 풀이 설계가 필요하다. 문제를 읽어보면 한 풍선의 양쪽 풍선 중 하나만 터트릴 수 있으며, 두 풍선 중 작은 풍선을 터트리는 것은 한번만 가능하다.(큰 풍선을 터트리는 것은 횟수 제한이 없다) 필자는 최종적으로 남는 풍선의 관점으로 풀이를 진행했다. 맨 마지막에 남는 풍선은 왼쪽 혹은 오른쪽의 풍선들보다 작은 수를 갖어야 한다. 이러한 점을 이용해 투 포인터 알고리즘을 적용해 마지막에 남을 수 있는 지 ..
코테준비
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이문제를 보고 인물들의 계층 구조를 보고 먼저 생각한 알고리즘은 DFS이다. 이 문제의 경우 재귀를 이용하는 방법 대신 Stack으로 탐색 노드를 저장해 pop하여 탐색할 수 있도록 설계했다. 이 문제에서 햇갈렸던 점이 소개해 준 사람이 얻는 이득을 계산하는 로직이였는데, 이는 이득의 합 계산이 아닌 각 이득의 10퍼씩 전달해야한다. 이말은 (10 + 20 + 30) * 0.1이 아니라 (10 * 0.1)+(20 * 0.1)+(30 * 0.1)으로 계산해야 한다. 코드function solution(enroll, referral, seller, a..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이해당 문제를 풀이할 때 처음에는 DFS 접근법을 조합으로 생각했지만, 구현하다 보니 DFS보다는 DP로 접근해 각 구역에 도착할 수 있는 가지수를 저장해 사용하는 것이 더 좋다고 생각해 DP를 사용하기로 했다. DP를 사용해 현위치에서 이전위치(상, 좌 위치에 있는) 값을 현제 위치에 더해준다. 이런 방법에서 중요한 부분은 조건처리이다. 이전 위치가 지도를 벗어나거나 물웅덩이라면 0을 더해준..
문제https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=javascript 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이처음 이 문제를 DFS 방식으로 풀이를 진행해 봤지만 시간 초과에러가 발생했다. 삼각형의 높이 즉, 주어지는 2차원 배열의 길이는 1~500 이였고 이는 1개씩 증가하는 수의 개수로 인해 경우의 수가 많아진다. 시간 복잡도로 인해 발생한 시간 초과 에러를 해결하기 위해서는 DP과 메모이제이션 알고리즘을 사용하기로 했다.triangle 2중 배열을 메모이제이..
문제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/2292 풀이벌집의 방 수가 6의 배수대로 증가하는 모습을 보며 2 번째 방의 시작인 2와 끝인 7의 변화를 지정해 주며, 입력되는 N이 해당 범위 내에 속하는 지를 확인하며 시뮬레이션 한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n');let n = +input.shift();if (n === 1) console.log(1);else { let cnt = 1; let [min, max] = [2, 7]; while ..
