1. 문제 풀이문제 유형은 그래프 탐색입니다.매개 변수 roads를 통해 인접리스트 형식으로 변환거리 배열 d를 -1로 초기화 후 목적지(destination)에 대해서만 0으로 갱신큐에 dst 삽입 후 너비 우선 탐색 수행sources를 순회하면서 d[sourcese[i]] 값을 벡터에 삽입 후 반환 2. 코드#include using namespace std;queue q;vector adj[100'005];int d[100'005];vector solution(int n, vector> roads, vector src, int dst) { for(auto edge : roads) { adj[edge[0]].push_back(edge[1]); adj[edge[1]].pu..
프로그래머스
1. 문제 풀이 문제 유형은 parametric search입니다. 시간을 이분탐색으로 결정한 다음 그 시간 내 n명의 사람들이 입국 심사를 받을 수 있는지 판별하는 로직을 구현하여 탐색하여 풀이할 수 있습니다. 2. 코드#include using namespace std;using ll = long long;ll MX = 1'000'000'000LL * 100'000LL;bool solve(ll mx, int n, vector &t) { ll cnt{}; for(auto time : t) { cnt += mx / time; } return cnt >= n;}long long solution(int n, vector times) { ll st{0}, en{MX + ..
1. 문제 풀이 문제 유형은 슬라이딩 윈도우입니다. 저는 우선순위 큐를 응용하여 풀이하였습니다. {값, 인덱스} 정보를 저장하고 우선순위 큐 루트 노드의 범위의 벗어난 값이 있으면 모두 소거하는 방식으로 진행했습니다. 이렇게 풀이하면 O(N lg N)으로 풀이할 수 있습니다. 다른 O(N lg N) 방법은 세그먼트 트리를 응용하는 방법이 있는데 게시글 작성 후 바로 추가해 보겠습니다. 2. 코드2 - 1. 우선순위 큐, 슬라이딩 윈도우 기법#include using namespace std;using pi = pair;#define X first#define Y secondpriority_queue pq;int solution(vector s, int k) { for(int i = 0; i 2 -..
1. 문제 풀이 문제 유형은 투 포인터입니다. 보석 종류가 문자열로 주어지기 때문에 해시를 사용하여 보석 종류마다 숫자를 부여해 줍니다. 투 포인터를 사용하여 모든 보석을 포함하는 구간을 찾아 그 구간의 길이가 최소가 될 경우 갱신해 주는 방법을 사용했습니다. 투 포인터를 알고 있다면 무난하게 풀 수 있을 것 같습니다. 2. 코드#include using namespace std;int mx;unordered_map idx;vector solution(vector G) { for(auto x : G) { if(idx.find(x) == idx.end()) { idx[x] = mx++; } } int ansx{0}, ansy{100'000}; ..
1. 문제 풀이 장르별로 숫자를 부여하여 분류한 다음, 그 장르의 총 재생 횟수와 그 장르의 노래 식별 번호와 재생 횟수를 우선순위 큐(최대힙)에 저장하여 관리했습니다. 총 재생 횟수가 큰 순으로 정렬해도되지만 우선순위큐를 하나 더 선언해 넣어서 관리했습니다. 총 재생 횟수가 큰 장르에서 가장 많이 재생된 노래 식별 번호를 뽑아와 벡터에 저장해 반환하는 방법을 사용해 풀이했습니다. 2. 코드#include using namespace std;#define X first#define Y secondint offset = 0;unordered_map idx;vector cnt;priority_queue> songs[105];vector solution(vector g, vector p) { for(in..
1. 개요 프로그래머스에서 제공하는 코딩테스트 문제를 풀다가 이전에 도전했다가 바로 포기했던 스킬 체크 레벨 2 탄탄한 비기너가 갑자기 생각이 났다. 1년 전에 도전했다가 문제 이해도 제대로 못해서 포기했었는데 1년 전에 비해 실력이 늘었다고 생각하기 때문에 다시 한번 도전해았다. 결과는 아래와 같다. 평범하게 30분 정도 여유를 두고 두 문제를 풀이했다. 다른 게시글에서 확인해 보니 도전할 때마다 문제 set이 달라지는 거 같아서 문제 풀이 리뷰도 해보려고 한다. 2. 첫 번째 문제0과 1로만 이루어진 n * m 배열이 주어지고 1로 이루어진 가장 큰 정사각형의 넓이를 구하는 문제였다. 유형은 다이나믹 프로그래밍이었다. board[i][j]가 정사각형의 오른쪽 아래 꼭짓점이라고 했을 때, 정사각형의 ..
1. 문제 풀이 미리 기지국이 설치된 곳을 기준으로 구역이 나뉘게 됩니다. 그 구역별로 따로 계산을 해야 일관성을 가질 수 있다고 추측하였습니다. 따라서 구역을 구분하는 작업을 먼저 합니다. 여기서 주의할 점은 미리 설치된 기지국들은 서로 인접한 곳에 위치할 수 있다는 가능성입니다. 예를 들어, stations[i] 위치에 설치된 기지국의 전파가 닿는 위치에 stations[i + 1]이나 stations[i - 1] 등이 설치될 가능성을 배제할 수 없습니다. 따라서 각 statons의 위치 cx와 전파 거리 w에 대해서 {cx - w, cx + w}와 같은 line을 만들어 저장한 다음 그리디하게 선들을 merge하는 작업을 했습니다. 이로써 기지국의 전파가 닿지 않는 구역들이 구분되고 각 구역의 크기..
1. 문제 풀이 각 차량의 진출 지점에 대해서 내림차순으로 정렬합니다. 첫 단속카메라를 설치해야할 지점은 먼저 나간 차량의 진출 시점입니다. 그 후, 순회하면서 각 차량들의 진입, 진출 시점 사이의 단속카메라가 위치해있는지 확인하고 만약 없다면 그 차량의 진출 시점에 새로운 카메라를 설치해야합니다. 2. 코드#include using namespace std;using pi = pair;#define X first#define Y secondvector lines;int solution(vector> routes) { for(auto &cur : routes) { lines.push_back({cur[1], cur[0]}); } sort(lines.begin(), l..
