문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이번 문제는 탐색이다. 하지만 입력되는 배열의 길이가 100만으로 매우 긴 모습을 알 수 있다. 이렇게 입력이 큰 문제의 경우 시간복잡도를 고려한 풀이 설계가 필요하다. 문제를 읽어보면 한 풍선의 양쪽 풍선 중 하나만 터트릴 수 있으며, 두 풍선 중 작은 풍선을 터트리는 것은 한번만 가능하다.(큰 풍선을 터트리는 것은 횟수 제한이 없다) 필자는 최종적으로 남는 풍선의 관점으로 풀이를 진행했다. 맨 마지막에 남는 풍선은 왼쪽 혹은 오른쪽의 풍선들보다 작은 수를 갖어야 한다. 이러한 점을 이용해 투 포인터 알고리즘을 적용해 마지막에 남을 수 있는 지 ..
코딩 테스트/프로그래머스 코딩 테스트 연습
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이해당 문제는 구현 문제였다. 이 문제에서 주의할 점은 두 가지가 있다. 첫 번째는 시간의 변환이다. 구현하는 기능 중 시간의 비교를 하는 과정이 포함되어 있다.이때 보다 효율적으로 시간을 관리하기 위해 (60 * 분) + 초 형식의 정수로 관리한다. 두 번째는 각 이벤트 처리이다.이 문제에서는 오프닝 건너뛰기, prev시 10초 미만이 남았을 때 00:00으로, next시 10초 미만이 남았을 때 영상의 끝으로 이동하는 이벤트가 있다. 이러한 이벤트는 각각 처리해야하는 타이밍이 존재한다.오프닝 건너뛰기는 각 명령어 입력 전에 측정하고 동작해야하며,..
문제 프로그래머스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://school.programmers.co.kr/learn/courses/30/lessons/340211 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제의 경우 각 로봇이 움직이는 시간별로 위치를 객체에 담아 중복되는 경우를 탐지해야한다. 코드function solution(points, routes) { let answer = 0; const map = new Map(); const pos = []; points.forEach(([y, x], i) => { map.set(i + 1, [y, x]); }); routes.forEach((e) => { le..
