본문 바로가기

알고리즘 문제/Leetcode283

[Leetcode][931] Minimum Falling Path Sum 문제 : https://leetcode.com/problems/minimum-falling-path-sum/ DP로 풀었다.떨어지는 경로의 배열 합이므로 현재 위치에서 갈 수 있는 배열은 왼쪽 아래, 아래, 오른쪽 아래이다.따라서 점화식은 아래와 같이 만들 수 있다. d[i][j] = A[i][j] + min(d[i-1][j-1], d[i-1][j], d[i-1][j+1])cs 배열을 모두 돌며 배열 d를 채웠을 때 마지막 행에서 가장 작은 값이 정답이 된다. 시간복잡도는 A배열이 NxN이라 했을 때, O(N^2). 소스코드 : https://gist.github.com/fpdjsns/18f4d32c49ac294a4175065fc8cfca90 2018. 12. 18.
[Leetcode][958] Check Completeness of a Binary Tree 문제 : https://leetcode.com/problems/check-completeness-of-a-binary-tree/ 위 그림에서 보면 완전이진트리라면 배열에 저장될 때 현재 노드 인덱스(n) 기준으로 왼쪽 자식 노드는 2n 인덱스에, 오른쪽 자식 노드는 2n+1 인덱스에 저장된다.이를 이용하여 루트부터 자식노드들을 탐색하면서 노드가 저장되는 인덱스 중 최대 값을 구하고 총 노드 수를 구한다.만약 완전이진트리라면 인덱스의 최대값과 노드 수는 같을 것이고 완전이진트리가 아니라면 인덱스의 최대값이 노드 수보다 클 것이다. 시간 복잡도는 노드 수를 N이라 할 때 O(N). 소스코드 : https://gist.github.com/fpdjsns/f32430b2e112b79a5647bfdd7b7d30d7 2018. 12. 17.
[Leetcode][955] Delete Columns to Make Sorted II 문제 : https://leetcode.com/problems/delete-columns-to-make-sorted-ii/ ["ax", "ay", "ba", "bb"]를 입력값으로 예를 들어보면 1, 2행 "ax", "ay" 는 첫번째 열 a 가 같으므로 두 번째 열 x, y는 정렬이 되어야 한다.2, 3행 "ay", "ba" 는 첫번째 열 a, b 가 같지 않고 사전순정렬이 되어있기 때문에 두 번째 열 y, a는 정렬이 될 필요가 없다.(정렬되지 않아도 사전 순 정렬이 되기 때문에)위 개념으로 알고리즘을 생각해본다. A 요소 개수를 N, A[i]의 길이를 M이라 하자.N크기만큼의 bool형 배열(ordered)을 하나 만든다.ordered[i] = A[i-1], A[i] 는 사전순 정렬이 되어있는가.를.. 2018. 12. 16.
[Leetcode][124] Binary Tree Maximum Path Sum 문제 : https://leetcode.com/problems/binary-tree-maximum-path-sum/ 서브트리의 루트 노드를 기준으로 만들 수 있는 sequence들은 다음과 같다.1. 현재 루트노드, 루트노드의 왼쪽, 오른쪽 노드를 sequence로 가지는 경우. 2. 왼쪽 노드와 부모노드를 sequence로 가지는 경우왼쪽 자식노드 value가 오른쪽 자식노드보다 크고 root와의 합이 0이거나 양수인 경우이다. 3. 오른쪽 노드와 부모 노드를 sequence로 가지는 경우오른쪽 자식 노드가 왼쪽 자식노드보다 크고 오른쪽 자식 노드와 root노드의 value를 합한 값이 양수인 경우이다. 4. root노드만을 sequence에 포함시키는 경우이 경우는 왼쪽 자식 노드와 오른쪽 자식 노드.. 2018. 12. 10.
[Leetcode][948] Bag of Tokens 문제 : https://leetcode.com/problems/bag-of-tokens/ tokens 배열을 오름차순 정렬한다.tokens 배열의 앞에서부터 토큰을 power로 얻으면서 탐색해나간다. (앞으로 탐색중인 인덱스는 i, 토큰 배열 요소 값은 tokens[i]라 하자.)만약 탐색중에 남은 power로 tokens[i]를 얻을 수 없다면 토큰을 하나 돌려주고 가장 비싼 토큰(인덱스 r이라 하자. r의 초기값은 tokens 배열의 마지막 인덱스와 같다.)의 power부터 가져온다. (낮은 power로 큰 power를 얻은 것과 같다.)power를 가져온 뒤는 반드시 tokens[i]를 얻을 수 있다. 왜냐하면 인덱스는 i < r인데 오름차순 정렬했기 때문에 tokens[i] 2018. 12. 4.
[leetcode][945] Minimum Increment to Make Array Unique 문제 : https://leetcode.com/problems/minimum-increment-to-make-array-unique/ A 배열을 오름차순 정렬한다.그리고 unique한 값을 저장하는 변수를 하나 만든다.unique한 값의 초기값은 A배열에서 가장 작은 값과 같고A배열을 탐색해갈수록 1씩 커진다.A배열을 앞에서부터 탐색할 때,unique 값이 A[i]값보다 같거나 작다면 unique 값은 A[i]로 갱신시켜준다. (오름차순 정렬을 했고 조건이 1을 더하는 것이므로 1을 더해서 이후에 유니크한 값을 만드려면 현재 탐색 중인 값보다는 반드시 커야한다.)unique 값이 A[i] 값보다 크다면 A[i]는 unique값이 되기위해 값을 더해야 한다. 이 값이 정답에 더해진다. (ex. unique.. 2018. 11. 27.

티스토리툴바