본문 바로가기

대딩192

[프로그래머스 lv3] 외벽 점검 풀이 해설그리디와 완전탐색을 이용하는 문제이다. 1) dist 원소의 개수는 8 이하이므로 1명, 2명,... , dist.size()명을 보냈을 경우에 대해 각각 완전탐색을 수행할 수 있다. 이때, i명을 보낸다면 dist[i]가 가장 큰 i명을 보내는 것이 유리하고, 따라서 dist를 내림차순으로 정렬하여 0부터 i-1번 까지의 친구(거리)를 사용하면 된다. 2) 보내는 친구 수를 결정한 이후, 각 친구를 어떠한 순서로 외벽에 맵핑할 것인지 결정한다. 친구들의 거리가 담긴 order 배열을 오름차순으로 정렬한 후 next_permutation()을 사용하면 선택한 거리에 대한 모든 순서를 탐색할 수 있다. 3) 점검을 보내는 친구 수와 각 친구들의 맵핑 순서가 정해졌을 때, 어떠한 취약점을 시작으로 맵핑할.. 2022. 9. 17.
[프로그래머스 lv3] 110 옮기기 풀이 해설문자열 x가 주어질 때, 문자열에서 110을 뽑아내자. 이때, 문자열을 한번만 훑는 것이 아니라, 스택을 활용하여 110을 제거하고 합쳐진 문자열에서의 110도 같이 제거한다. 예를 들어 문자열이 111100... 이고 스택에 네번째 원소까지 들어있다고 가정해보자.1) 현재 스택에는 1111이 들어있고 이제 0을 스택에 넣을 차례이다. 스택에서 가장 최근 두 수를 뽑으면 모두 1인데, 11은 0과 만나 110이 되므로 이를 스택에서 제거한다.2) 스택에는 11이 남아있게 된다. 이제 새로운 또 다른 0을 스택에 넣을 차례이다. 스택에서 가장 최근 두 수를 뽑으면 모두 1인데, 11은 0과 만나 110이 되므로 이를 스택에서 제거한다.3) 결국 스택에는 아무것도 남지 않는다. 문자열의 각 자리수를 스택.. 2022. 9. 15.
[프로그래머스 lv3] 보행자 천국 풀이 해설(x, y)에 d 방향으로 들어왔을 때 (m-1, n-1)까지 도달하는 경우의 수를 dfs(d, x, y)로 설정한다.리턴값은 다음과 같다. 1)  x == m-1 && y == n-1 일 때: 자기 자신에서 자기 자신으로 가는 경우의 수는 1이므로 1을 리턴한다. 2) (x, y)에서 이동할 수 있는 방향 k는 오른쪽(0)과 아래쪽(1)이다. 이때, 해당 방향으로 이동이 가능하려면,- 이동한 좌표가 city_map 내부 범위에 있어야 하고- city_map[x][y]가 0으로 자유롭게 이동이 가능하거나, city_map[x][y]가 2이면서 d와 이동 방향 k가 같아야 한다.- 즉, city_map[x][y] == 0 || (city_map[x][y] == 2 && d == k) 이면 해당 방향으로.. 2022. 9. 14.
[프로그래머스 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.

티스토리툴바