티스토리

경아카이브

검색하기

블로그 홈

경아카이브

maramarathon.tistory.com/m

경아ㅏ 님의 블로그입니다.

구독자: 7

방명록 방문하기

주요 글 목록

[프로그래머스 lv3] 선입 선출 스케줄링 풀이 해설 문제를 보자마자 오 이거 우선순위 큐 쓰면 되겠다 하고 빠르게 풀었다.n개의 작업을 처리할 때마다 가장 작업을 빨리 시작할 수 있는 코어를 찾고, 해당 코어의 다음 시작 지점을 수정하는 방법이다.시간복잡도도 O(NlogN)으로 여유롭다고 생각했는데... 이런! 효율성 통과가 안된다. int solution(int n, vector cores) { priority_queue, greater> pq; for (int i=0; i 다른 방법이 있을까 싶어서 시간대별 작업 현황을 그림으로 그려보았다.그랬더니, 일단 이분탐색을 이용하면 n개의 작업을 모두 처리할 수 있는 최소 시간을 구할 수 있겠다는 생각이 들었다. 1) 시간의 탐색 범위 시작을 first, 탐색 범위 끝을 las.. 공감수 0 댓글수 0 2022. 9. 22.
[프로그래머스 lv3] 아이템 줍기 풀이 해설캐릭터 위치부터 아이템 위치까지 최단 거리를 구하는 bfs 문제이다.캐릭터 위치를 출발지로 하여 테두리에 해당하는 좌표들로 이동한다. 출발지로부터 각 좌표까지의 거리를 dist[x][y] 배열에 저장해 나가고, dist[아이템X][아이템Y]를 리턴하면 된다. 그럼, 테두리에 해당하는지 여부는 어떻게 표시할 수 있을까?전체 직사각형의 영역을 먼저 표시한 후 사각형 내부만 다시 0으로 변경하면 된다. //x: 세로좌표, y: 가로좌표로 처리//직사각형 부분을 1로 채우기for (int i=0; i 그런데, 위와 같이 구현하면 이동방향이 명확히 표현되지 않는 경우가 발생한다.예를 들어, 문제에서 제시한 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 의 테두리를 표시해보자.하늘.. 공감수 0 댓글수 0 2022. 9. 21.
[프로그래머스 lv3] 매칭 점수 풀이 해설웬만한 문제는 c++로 푸는 것을 선호하지만, 문자열 + 정규표현식을 사용하면 편할 것 같아 파이썬을 사용했다. 1. page를 순회하면서 url과 link 뽑기, word 개수 세기 1) url과 links 뽑기url의 경우 https://careers.kakao.com/index" /> 형식이라고 했으므로, 다음과 같은 정규표현식을 사용한다. ()는 정규표현식에서 필요한 부분만 캡처하는 기능으로 .group(1)을 통해 해당 부분만 추출할 수 있다. 예를 들어, ...https://a.com ... 문자열에서 ()가 씌워진 a.com만 추출하는 것이다. url = re.search('', page).group(1) link의 경우 " target="_blank" rel="noopener">htt.. 공감수 0 댓글수 0 2022. 9. 20.
[프로그래머스 lv3] 모두 0으로 만들기 풀이 해설주어지는 그래프는 트리이다. 트리는 모두 연결되어있기 때문에 모든 정점의 합이 0이 되기만 한다면 규칙을 여러번 사용할지언정 모든 정점을 0으로 만들 수 있다.따라서, 모든 정점의 합(sum)을 구하고 합이 0이 아닐 경우 -1을 리턴한다. 모든 정점의 합이 0이라면 이제는 최소의 규칙을 적용하여 모든 정점을 0으로 만들 방법을 찾아야 한다. 1) func(int cur)은 현재의 지점(cur)을 루트 노드로 하는 트리에 대하여, 자식 노드들의 숫자를 모두 상쇄시키고 남은 것을 a[cur]에 옮기는 함수이다. 말단에 있는 트리들 부터 0으로 만든 뒤, 남은 숫자들을 처리하여 루트 노드로 올린다. 밑에서 처리할 수 있는 것들은 미리미리 0으로 만들어야 최소한의 규칙을 사용할 수 있다. 2) 위의 사항을.. 공감수 0 댓글수 0 2022. 9. 20.
[프로그래머스 lv3] 블록 이동하기 풀이 해당 문제는 2020 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설 해설(1, 1) 에서 (N, N)까지 도달하는 최단 경로를 구하는 문제로, bfs를 이용하여 해결할 수 있다. 1) bfs를 이용하여 최단 시간(거리)을 구할 때, 특정 좌표까지의 거리를 기록하는 dist 배열을 만들어야 한다. 그런데, 이 문제에서는 로봇이 두 칸에 걸쳐 이동하고 심지어 방향까지 가지고 있다. 따라서, 특정 좌표를 방문했는지 그리고 해당 좌표까지의 거리가 얼마인지 기록하는 배열은 3차원이 되어야 한다. dist[x][y][d]는 (x, y)에 d 방향으로 도달했을 때 (d = 0이면 오른쪽으로, d = 1이면 아래쪽으로) 해.. 공감수 0 댓글수 0 2022. 9. 19.
[프로그래머스 lv3] 광고 삽입 풀이 해당 문제는 2021 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설 해설1) 가장 많은 줄이 겹치는 지점이나 구간을 구할 때 떠올리면 좋은 스킬이 있다.바로, 모든 로그의 시작점과 끝점에 대하여 (시작, +1), (끝, -1)을 저장한 배열을 만들고 해당 배열을 정렬하여 특정 포인트에 몇개의 +1과 -1이 추가 되는지 검사하는 것이다. 시간 t 지점에 겹치는 재생 목록이 n개인데 새로 시작되는 재생목록이 plus개, 끝나는 재생목록이 minus개라면 t+1 지점에는 겹치는 재생목록이 n+plus-minus 개가 된다. log 배열을 이용하여 시간 t에 도달했을 때 추가되는 재생목록.. 공감수 0 댓글수 0 2022. 9. 19.
[프로그래머스 lv3] 스타 수열 풀이 해설스타 수열을 만들기 위한 조건은 다음과 같다.> 스타 수열의 원소들을 2개씩 나누었을 때 각 집합이 포함하는 공통된 원소가 있을 것 따라서, a에 등장하는 각 원소를 공통 원소로 하는 최대 스타 수열을 찾고 이 중에서도 가장 긴 수열의 길이를 리턴하면 된다. 1) a에는 0부터 a.size() 미만의 원소가 포함되어있다. a를 순회하면서 각 원소들의 등장 횟수를 cnt 배열에 저장하자. 2) a에 등장한 각 수 i를 순회하면서 i를 공통 원소로 하는 최대 스타 수열의 길이를 구해보자. - 이때, cnt[i]가 0이라면 i를 공통 원소로 하는 스타 수열을 만들 수 없다.- cnt[i]가 현재까지의 최대 스타 수열 길이 ans보다 작거나 같다면, i를 공통 원소로 하는 최대 스타 수열을 만들어도 그 길이.. 공감수 0 댓글수 0 2022. 9. 18.
[프로그래머스 lv3] N으로 표현 풀이 해설숫자 number을 N과 사칙연산으로 표현할 때 N 사용 횟수의 최솟값을 구하는 문제이다.최솟값이 8보다 크면 -1을 리턴하라고 했으므로, 우리는 1개부터 8개까지의 N을 사용했을 때 각각 만들 수 있는 수 목록을 찾으면 된다. 1) 1개의 N을 사용해서 만들 수 있는 수는 N 하나이다. 2) 2개의 N을 사용해서 만들 수 있는 수는- N을 두개 이어 붙인 NN- (1개의 N의 사용해서 만들 수 있는 수)와 (1개의 N의 사용해서 만들 수 있는 수)를 사칙연산한 결과이다. 3) 3개의 N을 사용해서 만들 수 있는 수는- N을 세개 이어 붙인 NNN- (1개의 N을 사용해서 만들 수 있는 수)와 (2개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과- (2개의 N을 사용해서 만들 수 있는 수)와 .. 공감수 0 댓글수 0 2022. 9. 18.
[프로그래머스 lv3] 거스름돈 풀이 해설dp[K]를 주어진 동전을 사용해 K를 만드는 모든 경우의 수 라고 정의하자.예를 들어, K = 5 이고 주어진 동전 money = [1, 2, 5] 라면, 가능한 경우는 dp{K] = 4이다. 1+1+1+1+11+1+1+2 1+2+25 주의할 점은 1+1+1+2와 1+2+1+1, 1+1+2+1 등은 모두 같은 것이므로 중복해서 세면 안된다는 것이다.따라서, dp[K]를 구할 때 중복이 발생하지 않도록 사용할 수 있는 동전과 금액을 차차 늘려가야 한다. 우선, 0을 만드는 방법은 아무것도 사용하지 않는 방법 1가지 이므로 dp[0] = 1로 설정한다.이후, 각 동전을 끝에 추가하여 만들 수 있는 수를 확인하자. money[i]를 끝에 추가할 때 만들 수 있는 수 j는 money[i] ~ n까지의 수이.. 공감수 0 댓글수 0 2022. 9. 18.
[프로그래머스 lv3] 풍선 터트리기 풀이 해설a의 풍선들 중에서 주어진 규칙으로 풍선을 터뜨렸을 때 최종적으로 남을 수 있는 풍선의 수를 구하는 문제이다.a의 i번째 풍선이 최종적으로 남을 수 있는지 어떻게 확인할 수 있을까? 1) 문제에서 인접한 풍선들끼리만 비교하여 터뜨릴 수 있다고 했으므로, a[i]의 오른쪽에 있는 풍선들을 비교하여 터뜨린다면 a[i]의 오른쪽에는 가장 작은 풍선만 남는다. 마찬가지로, a[i]의 왼쪽에 있는 풍선들을 비교하여 터뜨리면 a[i]의 왼쪽에는 가장 작은 풍선만 남는다. 2) 풍선들을 터뜨릴 때 작은 풍선을 터뜨릴 수 있는 기회는 최대 한번뿐이다. 따라서, a[i]의 왼쪽에 있는 풍선들 중 가장 작은 풍선, a[i]의 오른쪽에 있는 풍선 중 가장 작은 풍선 중에서 a[i]보다 작은 것의 개수가 2개 미만이라면.. 공감수 1 댓글수 0 2022. 9. 17.
[프로그래머스 lv3] 외벽 점검 풀이 해설그리디와 완전탐색을 이용하는 문제이다. 1) dist 원소의 개수는 8 이하이므로 1명, 2명,... , dist.size()명을 보냈을 경우에 대해 각각 완전탐색을 수행할 수 있다. 이때, i명을 보낸다면 dist[i]가 가장 큰 i명을 보내는 것이 유리하고, 따라서 dist를 내림차순으로 정렬하여 0부터 i-1번 까지의 친구(거리)를 사용하면 된다. 2) 보내는 친구 수를 결정한 이후, 각 친구를 어떠한 순서로 외벽에 맵핑할 것인지 결정한다. 친구들의 거리가 담긴 order 배열을 오름차순으로 정렬한 후 next_permutation()을 사용하면 선택한 거리에 대한 모든 순서를 탐색할 수 있다. 3) 점검을 보내는 친구 수와 각 친구들의 맵핑 순서가 정해졌을 때, 어떠한 취약점을 시작으로 맵핑할.. 공감수 0 댓글수 0 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) 결국 스택에는 아무것도 남지 않는다. 문자열의 각 자리수를 스택.. 공감수 0 댓글수 0 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) 이면 해당 방향으로.. 공감수 0 댓글수 0 2022. 9. 14.
[프로그래머스 lv3] 길 찾기 게임 풀이 해당 문제는 2019 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.2019 카카오 신입 공채 1차 코딩 테스트 문제 해설 해설traverse(int cur, vector vchild) 는 cur을 루트노드로 자식노드 vchild 를 순회하는 함수이다.자식 노드들 중에서 cur 노드의 x좌표보다 x좌표가 작은 노드들은 왼쪽서브트리, x좌표가 큰 노드들은 오른쪽서브트리에 위치하게 된다.cur을 기준으로 왼쪽서브트리와 오른쪽서브트리에 해당하는 배열들을 구성한 뒤, 각각의 배열에서 루트노드를 찾는다.이때, 트리의 루트 노드는 y좌표가 가장 큰 노드가 된다. 전위 순회의 경우, 현재 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리후위 순회의 경우, 왼쪽 서브트리 -> 오른쪽 서브트리.. 공감수 0 댓글수 0 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에 들어있는 노드 중 하나를 선택하여 다음 노드로 넘어가야 하는데, 다음 노드로 넘어가.. 공감수 0 댓글수 0 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.. 공감수 1 댓글수 0 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 위 같은 배열을 만들어 놓은 뒤, 왼쪽에서 오른쪽으로 누적합을 구하고 다시 .. 공감수 0 댓글수 0 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.. 공감수 0 댓글수 0 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.. 공감수 0 댓글수 0 2022. 9. 11.
[프로그래머스 lv3] 섬 연결하기 풀이 해설MST(최소 신장 트리)를 구하는 문제이다.최소 신장 트리를 구하는 문제는 크루스칼 알고리즘이나 프림 알고리즘을 이용하여 해결할 수 있는데, 그 중 크루스칼 알고리즘으로 해결하였다. 먼저, 정점을 잇는 간선을 길이가 짧은 순으로 나열한다.간선을 탐색하면서 두 정점이 다른 그룹이면 두 정점을 하나의 그룹으로 합치고 해당 간선을 선택한다. 이미 두 정점이 같은 그룹에 있으면 패스한다.크루스칼 알고리즘에 대한 자세한 설명은 최소신장트리(Minimal Spanning Tree)_크루스칼(Kruscal) 알고리즘를 참조하면 좋다. 코드#include #include #include #include #include #include #include #include #include #include #include.. 공감수 0 댓글수 0 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] 까지 구했을 때, 스티커는 원형이.. 공감수 0 댓글수 0 2022. 9. 10.
[프로그래머스 lv3] 디스크 컨트롤러 풀이 해설평균 시간을 최소화 하기 위해서는 현재 시간 t 이전에 들어온 작업 중 가장 소요시간이 작은 작업을 선택해야 한다. 우선순위 큐에 (소요시간, 요청시간)을 넣어놓으면 소요시간이 가장 작은 순으로 원소를 pop 할 수 있다.이때, 현재 시간 t보다 요청 시간이 작거나 같은 작업만 선택할 수 있으므로 처음으로 요청시간이 t보다 작거나 같은 작업을 찾는다.해당 작업을 찾았을 때 처리시간(현재시간 t - 요청 시간 + 소요시간)을 총합에 기록해둔 뒤 작업 크기로 나누어 리턴하면 정답이다. 코드#include #include #include #include #include #include #include #include #include #include #include #include #include usi.. 공감수 0 댓글수 0 2022. 9. 9.
[프로그래머스 lv3] 기지국 설치 풀이 해설n의 최대 범위가 200000000 이므로 배열을 만들어 일일이 5G 영역을 체크하기엔 시간복잡도가 크다.해서, 배열을 사용하지 않는 방법을 강구해야 하는데, 일단 주어진 stations 를 이용하여 이미 5G의 영향 아래에 있는 영역을 구해보자. 1) 5G 영향 아래 있는 영역 구하기stations을 순환하며 5G 영역의 (시작, 끝)을 구하고 이를 벡터에 저장하자.기지국이 x 좌표에 설치되어있을 때, 영역의 시작은 max(0, x-w) 이고 영역의 끝은 min(n, x+w)가 된다.이때, 시작 좌표가 (이전 영역의 끝+1) 보다 작거나 같다면 이전 영역과 겹친다는 이야기 이므로 이전영역에 합쳐서 끝 영역에 대한 정보만 변경시켜준다. 만약 시작 좌표가 (이전 영역의 끝+1)보다 크다면 겹치지 않는다.. 공감수 0 댓글수 0 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.. 공감수 1 댓글수 0 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 행.. 공감수 1 댓글수 0 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.. 공감수 0 댓글수 0 2022. 9. 7.
[프로그래머스 lv3] 징검다리 건너기 풀이 해설해당 문제는 2019 카카오 개발자 겨울 인턴십 출제 문제로 공식 해설이 있습니다.2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설 다양한 풀이가 있겠지만, 이분탐색 풀이를 선택해보자.가능한 니니즈수에 대하여 이분탐색을 진행하면 징검다리를 건널 수 있는 최대 니니즈수를 log(m) 에 탐색할 수 있다. (m=200000000) 이때, 특정 니니즈 수 x에 대하여 최대 칸수 k내에서 징검다리를 모두 건널 수 있는지 확인해야 한다.x-1명까지 건넜을 때 디딤돌 배열 상태는 stones[i]를 min(0, stones[i]-(x-1))로 변경하여 구할 수 있는데, 배열에서 연속적으로 등장하는 0의 개수가 모두 k보다 작거나 같으면 모두 징검다리를 건널 수 있다는 뜻이다. 특정 니니즈 수를 탐색할 .. 공감수 0 댓글수 0 2022. 9. 7.
[프로그래머스 lv3] 단속카메라 풀이 해설routes를 탈출지점을 기준으로 오름차순으로 정렬한다.가장 첫번째 카메라의 위치를 routes[0][1]로 두고, 사용한 카메라의 개수를 1 증가시킨다.routes를 1번 인덱스 부터 순회하면서 해당차량의 진입 지점과 마지막 카메라 위치를 비교한다. 1) 진입 지점이 마지막 카메라 위치보다 작거나 같으면, 마지막으로 설치한 카메라를 만나게 되므로 패스한다.2) 진입 지점보다 마지막 카메라 위치보다 크면 이전에 있는 카메라로는 단속할 수 없으므로 새로운 카메라를 설치해야 한다. 카메라 설치 위치는 현재 차량의 탈출 지점이 가장 유리하므로 routes[i][1]을 마지막 카메라 위치로 설정한다. 이때, 사용한 카메라 개수를 1 증가시킨다. 마지막 routes[i]까지 순환한 후 사용한 카메라 개수를 리.. 공감수 0 댓글수 0 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행 보다 먼저 구해놓아야 한다는 뜻이다. 따.. 공감수 0 댓글수 0 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 이고, 편도로.. 공감수 0 댓글수 0 2022. 9. 5.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.