본문 바로가기

대딩192

[프로그래머스 lv3] 스티커 모으기(2) 풀이 해설규칙을 만족시키면서 스티커를 뗄 때 스티커의 가장 큰 합을 구하는 문제이다.동적 계획법을 이용하여 답을 구해보자.dp[i][j][k]를 i번까지 스티커를 사용했을 때 얻을 수 있는 최대 합이라고 설정한다.이때, j는 첫번째 스티커의 사용여부(0, 1), k는 i번째 스티커의 사용여부(0, 1) 이다. i번째 스티커를 사용한다면 i-1번째 스티커는 사용할 수 없다.따라서, dp[i][j][1] = dp[i-1][j][0] + sticker[i] 가 된다. i번째 스티커를 사용하지 않는다면, i-1번째 스티커는 사용해도 되고 사용하지 않아도 된다.따라서, dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]) 이다. dp[n-1][j][k] 까지 구했을 때, 스티커는 원형이.. 2022. 9. 10.
[프로그래머스 lv3] 디스크 컨트롤러 풀이 해설평균 시간을 최소화 하기 위해서는 현재 시간 t 이전에 들어온 작업 중 가장 소요시간이 작은 작업을 선택해야 한다. 우선순위 큐에 (소요시간, 요청시간)을 넣어놓으면  소요시간이 가장 작은 순으로 원소를 pop 할 수 있다.이때, 현재 시간 t보다 요청 시간이 작거나 같은 작업만 선택할 수 있으므로 처음으로 요청시간이 t보다 작거나 같은 작업을 찾는다.해당 작업을 찾았을 때 처리시간(현재시간 t - 요청 시간 + 소요시간)을 총합에 기록해둔 뒤 작업 크기로 나누어 리턴하면 정답이다.  코드#include #include #include #include #include #include #include #include #include #include #include #include #include usi.. 2022. 9. 9.
[프로그래머스 lv3] 기지국 설치 풀이 해설n의 최대 범위가 200000000 이므로 배열을 만들어 일일이 5G 영역을 체크하기엔 시간복잡도가 크다.해서, 배열을 사용하지 않는 방법을 강구해야 하는데, 일단 주어진 stations 를 이용하여 이미 5G의 영향 아래에 있는 영역을 구해보자. 1) 5G 영향 아래 있는 영역 구하기stations을 순환하며 5G 영역의 (시작, 끝)을 구하고 이를 벡터에 저장하자.기지국이 x 좌표에 설치되어있을 때, 영역의 시작은 max(0, x-w) 이고 영역의 끝은 min(n, x+w)가 된다.이때, 시작 좌표가 (이전 영역의 끝+1) 보다 작거나 같다면 이전 영역과 겹친다는 이야기 이므로 이전영역에 합쳐서 끝 영역에 대한 정보만 변경시켜준다. 만약 시작 좌표가 (이전 영역의 끝+1)보다 크다면 겹치지 않는다.. 2022. 9. 9.
[프로그래머스 lv3] 등굣길 풀이 해설오른쪽과 아래쪽으로 이동하고, 특정 지점을 향하는 문제는 dp의 전형적인 유형이다. dfs(int x, int y) 를 (x, y)에서 (n, m)까지 이동하는 경우의 수라고 정의할 때 이동할 수 있는 방법은 두 가지가 있다.1) 오른쪽 방향: (x, y+1)에서 (n, m)으로 이동하는 방법2) 아래쪽 방향: (x+1, y)에서 (n, m)으로 이동하는 방법따라서, dfs(x, y)는 dfs(x, y+1) + dfs(x+1, y) 로 정의할 수 있다. 이때, 메모이제이션 없이 dfs를 돌려버리면 TLE가 발생할 가능성이 높으므로 이미 구한 값을 저장해놓고 해당 결과가 필요할 때마다 찾아 쓰는 동적프로그래밍 방법을 사용하자.dfs(int x, int y)가 실행되었을 때, 그 결과가 이미 memo[x.. 2022. 9. 8.
[프로그래머스 lv3] 정수 삼각형 풀이 해설지나갈 수 있는 모든 경로를 재귀로 해결하면 O(2^n)으로 TLE가 발생한다.dp 방법을 이용하여 O(n^2)에 해결해보자. dp[i][j]를 triangle[i][j]에 도달할때까지의 최대 합이라고 설정하면,  dp[i][j]까지 도달하는 방법은 두가지가 있다.1) (i-1, j-1)에서 오른쪽으로 내려오는 방법2) (i-1, j)에서 왼쪽으로 내려오는 방법 따라서, dp[i][j]의 값은 dp[i-1][j-1]과 dp[i-1][j] 중 더 큰 값에 triangle[i][j] 를 더한 값이다.점화식을 세워보면, dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] 가 된다. 모든 행에 대하여 dp 값을 구한 후, triangle.size()-1 행.. 2022. 9. 8.
[프로그래머스 lv3] 이중우선순위큐 풀이 해설최대힙과 최소힙을 따로 만들어놓자.D -1 명령어의 경우 최소힙에서, D 1 명령어의 경우 최대힙에서 원소를 삭제하면 된다.단, 변수 cnt에 총 원소 개수를 기록해놓고 cnt가 0이 되는 순간 최소힙과 최대힙을 깨끗하게 초기화시켜주어야 한다. 문제에서 남은 원소들의 [최댓값, 최솟값]을 리턴하라고 했으므로, cnt가 0이 아닐 때 {최대힙.top(), 최소힙.top()}을 리턴하면 정답이다.  코드#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;using i.. 2022. 9. 7.
[프로그래머스 lv3] 징검다리 건너기 풀이 해설해당 문제는 2019 카카오 개발자 겨울 인턴십 출제 문제로 공식 해설이 있습니다.2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설 다양한 풀이가 있겠지만, 이분탐색 풀이를 선택해보자.가능한 니니즈수에 대하여 이분탐색을 진행하면 징검다리를 건널 수 있는 최대 니니즈수를 log(m) 에 탐색할 수 있다. (m=200000000) 이때, 특정 니니즈 수 x에 대하여 최대 칸수 k내에서 징검다리를 모두 건널 수 있는지 확인해야 한다.x-1명까지 건넜을 때 디딤돌 배열 상태는 stones[i]를 min(0, stones[i]-(x-1))로 변경하여 구할 수 있는데, 배열에서 연속적으로 등장하는 0의 개수가 모두 k보다 작거나 같으면 모두 징검다리를 건널 수 있다는 뜻이다. 특정 니니즈 수를 탐색할 .. 2022. 9. 7.
[프로그래머스 lv3] 단속카메라 풀이 해설routes를 탈출지점을 기준으로 오름차순으로 정렬한다.가장 첫번째 카메라의 위치를 routes[0][1]로 두고, 사용한 카메라의 개수를 1 증가시킨다.routes를 1번 인덱스 부터 순회하면서 해당차량의 진입 지점과 마지막 카메라 위치를 비교한다. 1) 진입 지점이 마지막 카메라 위치보다 작거나 같으면, 마지막으로 설치한 카메라를 만나게 되므로 패스한다.2) 진입 지점보다 마지막 카메라 위치보다 크면 이전에 있는 카메라로는 단속할 수 없으므로 새로운 카메라를 설치해야 한다. 카메라 설치 위치는 현재 차량의 탈출 지점이 가장 유리하므로 routes[i][1]을 마지막 카메라 위치로 설정한다. 이때, 사용한 카메라 개수를 1 증가시킨다. 마지막 routes[i]까지 순환한 후 사용한 카메라 개수를 리.. 2022. 9. 6.
[프로그래머스 lv3] 가장 긴 팰린드롬 풀이 해설팰린드롬의 길이가 짝수일 때, 홀수일 때를 나누어 구현할 수도 있지만 복잡한 게 싫어서 dp로 처리했다.인덱스 i 부터 j까지의 팰린드롬 여부를 dp[i][j] (단, i  1) i == j 이면 한 글자이고, 무조건 팰린드롬이므로 dp[i][j] = true가 된다.2) i+1 == j 이면 두 글자이고, s[i] == s[j] 일 때 팰린드롬이 된다.3) 나머지 경우들은 세 글자 이상인데, i+1 부터 j-1까지 팰린드롬이고 s[i] == s[j]이면 팰린드롬이 된다. 위의 세가지 사항을 고려하여 dp[i][j]를 채우면 된다.주의할 것은 3) 번에서 dp[i][j]를 구하기 위해 dp[i+1][j-1] 값을 참조해야 하는데, 그 말인즉슨, i+1행을 i행 보다 먼저 구해놓아야 한다는 뜻이다. 따.. 2022. 9. 6.
[프로그래머스 lv3] 금과 은 운반하기 풀이 해설금 a kg, 은 b kg를 모으기 위한 최단 시간을 구하는 문제이다. "최단 시간"에 포인트를 맞추어 시간 기준으로 문제를 생각해보자.시간을 기준으로 이분탐색을 진행하고, 탐색하는 시간 내에 금 a, b를 모을 수 있는지 확인하면 된다. using l = long long;l binarySearch() { l first = 0; l last = 4*1e14+1e5; l ret = last; while (first  금 a, b 를 모을 수 있는 시간의 범위에서 first는 0이 된다. 1) 그렇다면, last는 어떻게 구해야 할까? 문제에서 a, b 의 최대 범위는 10^9 이라고 주어져있다. 이때, 한 번에 옮길 수 있는 무게(w)가 1kg 이고, 편도로.. 2022. 9. 5.

티스토리툴바