Dp

출처 프로그래머스 GPS(2017 카카오코드 본선) 접근 문제 분석 오류가 발생한 택시의 경로를 최소한으로 수정하여 정확한 이동 경로를 구하는 문제입니다. 우선, 택시의 이동을 표현하기 위한 그래프 구조가 필요합니다. 문제에서 최소한으로 이동하는 경로를 찾기 위해서는 갈 수 있는 모든 경로에 대해 완전탐색을 수행해야 합니다. 시간복잡도 분석 완전탐색 전체 경우의 수를 BFS 또는 DFS를 활용해서 제한시간 내 목적지까지 갈 수 있는 모든 경로를 찾아서 주어진 경로와의 차이를 비교하는 방법이 있습니다. 이러한 경우, 한 거점에서 다음 거점으로 이동하는 경우의 수는 정점과 연결된 간선(m)만큼 곱해지게 됩니다. 정점(n = 200)과 간선(m = 10,000)이 균일하게 연결된 그래프로 가정하면 한 정점에 연결된 간선의 수가 50개이기 때문에, 전체 경우의 수는 정점 1개에 50개씩 증가하여 O(N) = 50 ^ 200이 됩니다. ...

출처 2024 KAKAO WINTER INTERNSHIP 산 모양 타일링 접근 시간복잡도 구하기 n <= 100,000 이므로 전체 타일의 개수는 최대 사다리꼴의 윗변의 모든 자리에 삼각형을 넣을 수 있으므로 2n + 1 + n <= 300,001개 입니다. 이러한 삼각형의 배치를 완전탐색으로 구하는 것은 불가능하기 때문에, DP를 통한 최적화가 필요합니다. 규칙성 찾기 예제의 타일을 1칸씩 세면서 경우의 수를 세면 규칙성을 확인할 수 있습니다. 다음과 같이 (1 ~ 9) 순으로 예제타일의 규칙성을 구해보겠습니다. ...

출처 해커 랭크 : Lego Blocks 문제 설명 영문 사이트이므로 문제를 간단히 설명하겠습니다. 다음과 같은 총 네 가지 종류의 레고 블럭이 무한히 있습니다. d h w 1 1 1 [] : 길이가 1이고, 높이가 1인 레고 블럭 1 1 2 [ ] : 길이가 2이고, 높이가 1인 레고 블럭 1 1 3 [ ] : 길이가 3이고, 높이가 1인 레고 블럭 1 1 4 [ ] : 길이가 4이고, 높이가 1인 레고 블럭 문제에서 주어지는 높이와 길이만큼 레고 블럭을 쌓으려고 합니다. ...