본문 바로가기

알고리즘 문제/Leetcode283

[leetcode][870] Advantage Shuffle 문제 : leetcode.com/problems/advantage-shuffle/ 길이가 같은 정수 배열 A, B이 주어질 때, A의 원소의 순서를 변경하여 A[i] > B[i]인 원소의 개수가 최대가 되는 수열 A를 구하여라. 기본 아이디어는 A[i] > B[i] (조건)를 만들 수 있는 A[i] 값은 A 원소가 클수록 조건을 만족할 가능성이 높으며 A 원소가 작을수록 조건을 만족할 가능성이 낮다. 즉, 큰 원소값이 조건을 만족할 수 없으면 이는 작은 원소값도 만족할 수 없다. 따라서 큰 원소값을 세팅할 수 있는 곳에 먼저 세팅하고, 큰 원소값을 사용할 수 없는 곳은 버리는 수로 작은 원소값으로 대체한다. A 배열을 오름차순 정렬하고, B 배열을 {원소값, 인덱스} 배열로 변경하여 이를 오름차순 정렬한.. 2021. 3. 26.
[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.
[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.
[leetcode][268] Missing Number 문제 : leetcode.com/problems/missing-number/ 고유한 숫자 배열 nums가 주어질 때, 0~n 까지 수 중 누락된 수를 구하라. 누락된 수는 0~n까지 수들의 합에서 nums배열의 합을 뺀 값과 같다. 0~n까지 수들의 합은 등차수열의 합 공식으로 n(n+1)/2로 구할 수 있고, nums배열의 합은 배열을 한 번 탐색하면서 구할 수 있다. 시간복잡도는 O(n), 공간복잡도는 O(1). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/268.%20Missing%20Number.cpp 2021. 3. 3.

티스토리툴바