문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이해당 문제의 경우 각 인원별로 합산 점수와 두가지 점수를 비교해 등수를 책정해야 하는 문제이다. 문제의 접근법으로 누적합 알고리즘을 사용했는데, 근무태도 점수를 우선으로 내리 차순 정리(동점일 경우 평가 점수를 기준으로 올림 차순 정리)를 한 뒤 등 수를 누적합 알고리즘을 적용해 구하는 방식으로 접근했다. 이때 주의할 점이 누적합을 구현할 때 이미 점수 배열이 근무 태도 점수를 기준으로 정렬되어 있기 때문에 이전의 인원의 근무 태도 점수는 다음 인원보다 무조건 높으며 누적합 알고리즘을 구현할 때는 평가 점수를 이용해 등수를 계산하는 것이 좋다. 또..
분류 전체보기
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이해당 문제는 출발 지점을 지나 중간 분기점을 거쳐 최종 목표까지 도달할 때 필요한 최소 금액을 구하는 문제이다. 하지만 단순히 최소 금액을 도출하는 것이 아닌 두 가지 도착 지점이 있다는 점이 이 문제의 조건에 존재한다. 이렇게 특정 비용의 최소 값을 구하는 문제의 경우 다익스라 알고리즘을 사용할 수는 있지만, 해당 문제에서는 효율성 테스트를 진행하고 문제에서 분기점을 거친다는 점도 존재하여 다익스트라 알고리즘에서 파생된 플로이드 위샬 알고리즘을 사용했다. 우선 각 지점에서 다른 지점까지 도달할 수 있는 최소 비용을 구해야 한다. 이는 DP를 사용..
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제는 논리적 접근이 필요하다. 순위를 알려면 해당 선수의 각기 다른 상대의 승패 여부를 알아야 한다.즉, 전체 n명의 선수가 있고 특정 인원의 순위를 알고 싶다면 n-1의 전적이 필요하다. 이를 검증하기 위해서는 주어지는 전적들을 순회하며 각 선수의 승패 여부를 기록한다. 그리고 특정 인원(A)에게 패배한 선수(B)는 A가 패배한 선수들(C)에게는 항상 진다고 되어있다.이는 다음 사진에서 확인할 수 있다. 그렇다면 B는 항상 C에게 진다는 것을 염두하고 각 선수들의 승패를 기록하는 방식으로 접근하면 된다. 코드const solution = ..
문제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/21610 풀이이번 문제는 조건이 까다로운 구현 문제이다. 이 문제에서 가장 어려웠던 것은 기능의 구현이 아닌 문제 설명에 대한 이해이다. 구름이 처음 생성되는 구역은 [N-1, 0], [N-1, 1], [N, 0], [N, 1]이며, 이후 한 명령의 동작이 모두 끝나면 새로운 구름의 구역이 생성되는데 이 새롭게 생성된 구름을 이용해 다음 동작을 해야한다...... 이 부분을 햇갈려서 조금 오래 걸렸다...https://www.acmicpc.net/board/view/112464 그리고 다시한번 주의해야할 점을 알게되었다.바로 동기적인 데이터 갱신이다. 이 문제에서는 구름의 이동 동작을 구현할 때 구름의 생성과 삭제를 연속해서 했지만, 사실 구..
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이번 문제는 탐색이다. 하지만 입력되는 배열의 길이가 100만으로 매우 긴 모습을 알 수 있다. 이렇게 입력이 큰 문제의 경우 시간복잡도를 고려한 풀이 설계가 필요하다. 문제를 읽어보면 한 풍선의 양쪽 풍선 중 하나만 터트릴 수 있으며, 두 풍선 중 작은 풍선을 터트리는 것은 한번만 가능하다.(큰 풍선을 터트리는 것은 횟수 제한이 없다) 필자는 최종적으로 남는 풍선의 관점으로 풀이를 진행했다. 맨 마지막에 남는 풍선은 왼쪽 혹은 오른쪽의 풍선들보다 작은 수를 갖어야 한다. 이러한 점을 이용해 투 포인터 알고리즘을 적용해 마지막에 남을 수 있는 지 ..
