문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이해당 문제는 출발 지점을 지나 중간 분기점을 거쳐 최종 목표까지 도달할 때 필요한 최소 금액을 구하는 문제이다. 하지만 단순히 최소 금액을 도출하는 것이 아닌 두 가지 도착 지점이 있다는 점이 이 문제의 조건에 존재한다. 이렇게 특정 비용의 최소 값을 구하는 문제의 경우 다익스라 알고리즘을 사용할 수는 있지만, 해당 문제에서는 효율성 테스트를 진행하고 문제에서 분기점을 거친다는 점도 존재하여 다익스트라 알고리즘에서 파생된 플로이드 위샬 알고리즘을 사용했다. 우선 각 지점에서 다른 지점까지 도달할 수 있는 최소 비용을 구해야 한다. 이는 DP를 사용..
코딩 테스트/프로그래머스 코딩 테스트 연습
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제는 논리적 접근이 필요하다. 순위를 알려면 해당 선수의 각기 다른 상대의 승패 여부를 알아야 한다.즉, 전체 n명의 선수가 있고 특정 인원의 순위를 알고 싶다면 n-1의 전적이 필요하다. 이를 검증하기 위해서는 주어지는 전적들을 순회하며 각 선수의 승패 여부를 기록한다. 그리고 특정 인원(A)에게 패배한 선수(B)는 A가 패배한 선수들(C)에게는 항상 진다고 되어있다.이는 다음 사진에서 확인할 수 있다. 그렇다면 B는 항상 C에게 진다는 것을 염두하고 각 선수들의 승패를 기록하는 방식으로 접근하면 된다. 코드const solution = ..
문제 프로그래머스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을 더해준..
