분류 전체보기209 [프로그래머스 lv3] 길 찾기 게임 풀이 해당 문제는 2019 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.2019 카카오 신입 공채 1차 코딩 테스트 문제 해설 해설traverse(int cur, vector vchild) 는 cur을 루트노드로 자식노드 vchild 를 순회하는 함수이다.자식 노드들 중에서 cur 노드의 x좌표보다 x좌표가 작은 노드들은 왼쪽서브트리, x좌표가 큰 노드들은 오른쪽서브트리에 위치하게 된다.cur을 기준으로 왼쪽서브트리와 오른쪽서브트리에 해당하는 배열들을 구성한 뒤, 각각의 배열에서 루트노드를 찾는다.이때, 트리의 루트 노드는 y좌표가 가장 큰 노드가 된다. 전위 순회의 경우, 현재 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리후위 순회의 경우, 왼쪽 서브트리 -> 오른쪽 서브트리.. 2022. 9. 14. [프로그래머스 lv3] 양과 늑대 풀이 해당 문제는 2022 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설 해설주어진 노드 개수 범위가 크지 않기 때문에 모든 루트를 완전탐색하여 해결할 수 있다. func(int cur, int nlamb, int nwolf, vector vnext) (cur: 현재노드, nlamb: 현재노드까지 양의 수, nwolf: 현재노드까지 늑대의 수, vnext: 다음으로 이동할 수 있는 노드 후보) 라 할 때, 1) nlamb 2) 잡아먹히지 않았다면, nlamb의 최댓값을 기록한다.3) 이제 vnext에 들어있는 노드 중 하나를 선택하여 다음 노드로 넘어가야 하는데, 다음 노드로 넘어가.. 2022. 9. 13. [프로그래머스 lv3] 기둥과 보 설치 풀이 해당 문제는 2020 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설 해설시뮬레이션 문제로 문제에서 주어진 사항대로 구현하면 된다.핵심 로직은 기둥과 보를 특정 위치에 추가하거나 삭제하는 것이 가능한지 확인하는 부분이다. (x, y)에 기둥이 있는지 여부를 pil[x][y], 보가 있는지 여부를 pan[x][y]로 저장할 떄, 1. 기둥이 (x, y)에 존재할 수 있으려면,1) 기둥이 바닥에 있거나: x == 02) 보 위에 있거나: pan[x][y-1] || pan[x][y]3) 다른 기둥 위에 있어야 한다: pil[x-1][y] 2. 보가 (x, y)에 존재할 수 있으려면,1) 밑에 기둥이 있거나: pil.. 2022. 9. 13. [프로그래머스 lv3] 파괴되지 않은 건물 풀이 해설skill로 주어진 구역을 degree 만큼 회복/공격하여 최종 값이 1 이상인 칸수를 구하는 문제이다. 가장 쉽게 떠오르는 풀이는 skill 의 정보가 하나씩 주어질 때마다 (r1, c1)부터 (r2, c2)까지의 구역을 순회하며 degree만큼 빼거나 더하는 방법이다. 하지만 이렇게 구현하면, 시간 복잡도는 O(skill.size() x N x M) 이 되어 TLE 가 발생한다. 따라서 다른 방법을 찾아야 하는데 이 문제는 누적합을 이용하면 쉽게 해결할 수 있다. 예를 들어, (0, 0)부터 (2, 2)까지 영역에 n만큼을 더하려면 다음과 같은 배열을 만들면 된다. n 0 0 -n0 0 0 00 0 0 0-n 0 0 n 위 같은 배열을 만들어 놓은 뒤, 왼쪽에서 오른쪽으로 누적합을 구하고 다시 .. 2022. 9. 12. [프로그래머스 lv3] 자물쇠와 열쇠 해설key를 회전해서 lock의 특정 위치에 꽂을 때 lock의 모든 홈이 채워지는지 확인하는 문제이다.문제를 처음 본 순간 확인해야 하는 것은 m과 n의 범위이다.m과 n의 범위가 크지 않으므로 key를 회전시키고 특정 위치에 꽂는 모든 경우를 확인할 수 있겠다는 생각이 든다. 모든 경우를 확인하기 위한 단계를 다음과 같다. 1) 먼저, key를 90도로 4번 회전시킨다. 2) key를 회전시킨 각각의 경우에 대하여 lock 위에 key를 꽂을 수 있는 모든 위치를 탐색한다. key의 한변의 길이를 m, lock의 한변의 길이를 n이라 할 때, 키가 포개지는 시작점은 (m-1, m-1) 부터 (n-1+m-1, n-1, m-1) 까지 가능하다. 해당 위치를 시작점으로 키를 포갰을 때 n x n의 loc.. 2022. 9. 12. [프로그래머스 lv3] 경주로 건설 풀이 해당 문제는 2020 카카오 인턴십 출제 문제로 공식 해설이 있습니다.2020 카카오 인턴십 for Tech developers 문제해설 해설dist[dir][x][y]를 dir 방향으로 (x, y)에 도달했을 때 최소 비용이라고 정의한다.bfs로 좌표들을 탐색하면서 현재 위치에서 다음 위치로 도달할 때의 비용이 dist[dir][x][y]에 저장되어있는 값보다 작으면 갱신한다.우리가 구하고 싶은 것은 (n-1, n-1)까지 도달하는데 최소 비용이므로, 상/하/좌/우 방향으로 도달한 dist[dir][x][y] 값 중에서 최솟값을 리턴하면 정답이다. 코드#include #include #include #include #include #include #include #include #include #inc.. 2022. 9. 11. [프로그래머스 lv3] 섬 연결하기 풀이 해설MST(최소 신장 트리)를 구하는 문제이다.최소 신장 트리를 구하는 문제는 크루스칼 알고리즘이나 프림 알고리즘을 이용하여 해결할 수 있는데, 그 중 크루스칼 알고리즘으로 해결하였다. 먼저, 정점을 잇는 간선을 길이가 짧은 순으로 나열한다.간선을 탐색하면서 두 정점이 다른 그룹이면 두 정점을 하나의 그룹으로 합치고 해당 간선을 선택한다. 이미 두 정점이 같은 그룹에 있으면 패스한다.크루스칼 알고리즘에 대한 자세한 설명은 최소신장트리(Minimal Spanning Tree)_크루스칼(Kruscal) 알고리즘를 참조하면 좋다. 코드#include #include #include #include #include #include #include #include #include #include #include.. 2022. 9. 10. [프로그래머스 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. 이전 1 2 3 4 5 6 7 ··· 21 다음