문제https://www.acmicpc.net/problem/2573 풀이DFS나 BFS를 이용해도 다 되는 문제이며 필자는 BFS를 이용해 문제를 풀었다. 나는 실수로 BFS의 방문 처리를 잘못해 에러가 발생했었다.. 이런 실수는 조심하자.... 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n');let [n, m] = input.shift().split(' ').map(Number);const map = input.map(e => e.split(' ').map(Number));const..
코딩 테스트
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이해당 문제는 구현 문제였다. 이 문제에서 주의할 점은 두 가지가 있다. 첫 번째는 시간의 변환이다. 구현하는 기능 중 시간의 비교를 하는 과정이 포함되어 있다.이때 보다 효율적으로 시간을 관리하기 위해 (60 * 분) + 초 형식의 정수로 관리한다. 두 번째는 각 이벤트 처리이다.이 문제에서는 오프닝 건너뛰기, prev시 10초 미만이 남았을 때 00:00으로, next시 10초 미만이 남았을 때 영상의 끝으로 이동하는 이벤트가 있다. 이러한 이벤트는 각각 처리해야하는 타이밍이 존재한다.오프닝 건너뛰기는 각 명령어 입력 전에 측정하고 동작해야하며,..
문제https://www.acmicpc.net/problem/23288 풀이해당 문제는 구현이 조금 까다로울뿐 BFS를 이용한 탐색 문제이다. 주사위가 굴러가는 조건들을 조심히 구현하는 것이 중요하다. 필자도 조건을 잘못 설정해서 10분정도 해맸다... 주사위가 굴러간 좌표에 있는 숫자와 주사위 하단의 숫자를 비교한 뒤 주사위를 굴릴 방향을 정하고, 현재 위치의 숫자의 크기와 인접 좌표에 같은 숫자의 개수를 구해주면 문제의 풀이는 끝난다. 인접 좌표에서 같은 숫자의 수를 구할 때 BFS가 사용되는데, 필자는 주사위를 굴릴때 마다 방문 여부를 기록하는 객체를 생성해 방문여부를 기록했다. 코드const input = require('fs') .readFileSync(process.platform === '..
문제 프로그래머스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중 배열을 메모이제이..
