본문 바로가기

전체 글657

[Leetcode][923] 3Sum With Multiplicity 문제 : leetcode.com/problems/3sum-with-multiplicity/ 0이상 100이하의 정수를 가지는 배열 arr이 주어진다. 서로다른 원소 3개를 더한 값이 target이 되는 조합의 개수를 구하라. 배낭문제로 구할 수 있다. dp[target][cnt] = cnt 개의 원소들을 합해서 target 을 만들 수 있는 경우의 수. i 번째 원소(num)를 기준으로 dp 배열을 갱신해나간다. num + x = target 이라 가정하면 num에 x를 더하면 target을 만들 수 있으므로, x의 경우의 수로 target 인덱스를 갱신할 수 있다. 위의 식에서 num을 우항으로 옮기면 x = target - num이 되므로 dp[target][cnt+1] += dp[target-num.. 2021. 3. 23.
[Leetcode][823] Binary Trees With Factors 문제 : leetcode.com/problems/binary-trees-with-factors/ 2이상의 정수 배열 arr이 주어진다. arr 배열의 수들을 노드로 가지는 이진트리를 만들고자 한다. 정수들은 중복으로 사용할 수 있고 각 노드들의 값은 자식노드들의 곱과 같다. 조건을 만족하며 만들 수 있는 이진트리의 개수를 구하라. num으로 만들수 있는 서브트리의 수를 메모이제이션으로 캐싱한다. dp[num] = num을 루트로 하는 이진트리의 갯수. dp[num] = dp[num1] x dp[num2] // num1 x num2 = num 점화식은 위와 같다. 따라서, 곱해서 num이 나오는 num1, num2의 세트 배열을 구해야 된다. 2중 for문을 돌려서 arr배열의 요소들을 곱해서 num이 나.. 2021. 3. 14.
[programmers][2021카카오공채] 순위 검색 문제 : https://programmers.co.kr/learn/courses/30/lessons/72412 query가 100,000 infos가 50,000. query 문자열에 맞게 infos에 맞는 조건을 찾아서 정답을 구하기엔 시간이 부족하다. 개발언어가 3개. 직군 2개. 경력 2개. 소울푸드 2개. 3x2x2x2 = 24개의 조합에 맞는 score들을 저장해두면 시간을 확 줄일 수있다. scores[개발언어][직군][경력][소울푸드] = 점수들 배열. 만약 query에 개발언어가 상관없다면 scores[0~3][직군][경력][소울푸드]의 scores 조건에 맞는 점수들의 수를 정답에 포함시킨다. query에 개발언어가 java라면 scores[java 인덱스][직군][경력][소울푸드]의 s.. 2021. 3. 6.
[programmers][2021카카오공채] 합승 택시 요금 문제 : programmers.co.kr/learn/courses/30/lessons/72413 그래프이고 간선에 가중치가 있다. 최단거리알고리즘을 생각해본다. 정점 개수 n의 크기가 200으로 작은 편이므로 플로이드 워셜알고리즘으로 각 정점에서 다른 정점까지 이동할 때 최소 비용을 구해둔다. pays[u][v] = u->v로 택시를 타고 이동할 때 드는 최소 비용 합승종료지점 m 이라 하자. 이 때, 택시 비용은 출발지점에서 m 위치로 이동하는 비용 + m에서 각자의 집으로 이동하는 비용이 된다. pays 배열로 표현하면 pays[s][m] + pays[m][a] + pays[m][b] 과 같다. 따라서 m을 0~n으로 두고 위 수식에 적용하여 구한 택시비용들 중 최소 비용이 정답이 된다. 시간복잡도는.. 2021. 3. 4.
[Leetcode][160] Intersection of Two Linked Lists 문제 : leetcode.com/problems/intersection-of-two-linked-lists/ 2개의 연결리스트가 주어질 때, 교차점이 시작되는 노드를 찾아라. 교차점이 시작되는 노드 이후의 노드들은 두 개의 연결리스트에서 모두 같다. 예시로 나온 listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]로 살펴보자. listA-listB listB-listA 를 순서대로 연결한뒤 앞에서부터 하나씩 비교하다보면 교차점이 시작되는 노드를 찾을 수 있다. [4,1,8,4,5-5,6,1,8,4,5] [5,6,1,8,4,5-4,1,8,4,5] 위와같이 연결해서 앞에서부터 하나씩 비교하면 언젠가는 교차점이 되는 8을 찾을 수 있다. 만일 탐색이 끝날때까지 같아지는 노드를 찾을 수 .. 2021. 3. 4.
[leetcode][329] Longest Increasing Path in a Matrix 문제 : leetcode.com/problems/longest-increasing-path-in-a-matrix/ N*M 정수 배열이 주어질 때, 각 셸에서 상하좌우에 위치한 셸이며 현재 셸의 수보다 높은 수를 가지는 셸로 이동가능하다. 가장 긴 경로 길이를 구하라. DFS + DP 로 풀었다. i번째 셀에서 상하좌우로 이동가능한 곳으로 이동하면서 이동 가능한 경로의 최장 길이를 저장하는 배열(let, dp)을 만든다. dp[i] = min(dp[상하좌우 중 이동가능한 곳]) 위 점화식을 적용하며 dp배열을 dfs로 탐색하면서 세팅한다. dp 배열이 이미 갱신된적 있다면 새로 값을 구하지 않고 해당 값을 사용하여 시간을 줄일 수 있다. 시간복잡도, 공간복잡도 모두 O(NM). 소스코드 : github.c.. 2021. 3. 4.

티스토리툴바