알고리즘 문제/Leetcode283 [Leetcode] 1306. Jump Game III 문제 : https://leetcode.com/problems/jump-game-iii/ 음이 아닌 정수 arr 배열과 시작 인덱스 start가 주어진다. 인덱스 i에 있을 때 i+arr[i], i-arr[i] 인덱스로 점프할 수 있다고 할 때 값이 0인 인덱스에 도달할 수 있는지를 구하라. i번째 인덱스를 방문한 적이 있는지를 저장하는 배열을 하나 만들고 시작 인덱스 start부터 i+arr[i], i-arr[i] 인덱스 위치로 탐색하며 이미 방문한 적이 있다면 더 이상 탐색하지 않고 탐색한적이 없으면 방문여부를 true로 갱신한 다음 해당 값이 0이면 true를 반환한다. 해당 값이 0이 아닌 경우 i+arr[i], i-arr[i]가 배열 arr 범위 내부이며 방문한 적 없는 인덱스인 경우 탐색을 이.. 2021. 12. 9. [Leetcode] 563. Binary Tree Tilt 문제 : https://leetcode.com/problems/binary-tree-tilt/ 이진 트리 루트가 주어지면 모든 트리 노드의 기울기 합을 구하라. 트리 노드의 기울기는 모든 왼쪽 하위트리 노드들의 합, 모든 오른쪽 하위 트리 노드들의 합들 차이의 절대값이다. 만일 하위트리가 없으면 합을 0으로 본다. 정답 전역변수를 하나 두고 왼쪽, 오른쪽 하위트리를 탐색하며 합들을 구한 뒤, 왼쪽 오른쪽 노드들의 합 차이의 절대값을 정답 변수에 더해나간다. 그리고 왼쪽, 오른쪽 자식 노드들의 합 + 현재 노드의 val을 더한 값을 반환한다. 정답 = 0 func getSum(node) { if(node == NULL) return 0 left = getSum(node->left) right = getSu.. 2021. 12. 8. [Leetcode] 1290. Convert Binary Number in a Linked List to Integer 문제 : https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/ 0 혹은 1 값을 가지는 노드로 이루어진 linked list가 주어진다. 이를 10진수 값으로 반환하라. 초기값이 0인 정답 변수를 두고 head 노드에서 링크드리스트를 모두 탐색하면서 (2 x 정답 + 탐색노드.val) 로 정답 변수를 갱신해나간다. 시간복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1290.%20Convert%20Binary%20Number%20in%20a%20Linked%20List%20to%20Integer.cpp 2021. 12. 7. [Leetcode] 1217. Minimum Cost to Move Chips to The Same Position 문제 : https://leetcode.com/problems/minimum-cost-to-move-chips-to-the-same-position/ n의 크기인 position 1차원 배열이 있다. position[i]는 i 번째 칩의 위치를 의미한다. 한 번에 i 번째 칩의 위치를 왼쪽이나 오른쪽으로 두 칸 움직이는 비용은 0이고, 한 칸 움직일 때는 1의 비용이 든다. 모든 칩을 동일한 위치로 옮기려고 할 때 필요한 최소 비용을 구하라. 2만큼 움직이는건 비용이 들지 않으므로 짝수번 움직이는건 비용이 들지 않는 것과 같다. 따라서 0 비용으로 짝수번째 위치에 있는 칩들은 2번으로, 홀수번째 위치에 있는 칩들은 1번으로 먼저 옮긴다. 그리고 짝수, 홀수에 있는 칩들 개수 중 더 작은 개수의 칩들을 반.. 2021. 12. 7. [Leetcode] 337. House Robber III 문제 : https://leetcode.com/problems/house-robber-iii/ 이진 트리로 구성된 집들의 구조가 있다. 도둑은 집들에 침입해 도둑질을 하려고 하는데 연결된 집을 동시에 털면 경찰에 연락이 간다. 경찰에 연락이 가지 않게 집들을 도둑질하려고 할 때, 훔칠수 있는 최대 금액을 구해라. memoization을 위해 TreeNode*을 키 값으로 하고 해당 노드를 헤드노드로 한 서브트리에서 조건을 만족하며 훔칠 수 있는 최대 금액을 저장한다. 탐색 중인 노드를 훔쳤다면 왼쪽, 오른쪽 자식 노드들은 훔치면 안되므로 왼쪽 자식 노드의 자식 노드들, 오른쪽 자식 노드의 자식 노드들을 다시 헤드 트리로 하여 훔칠 수 있는 최대 금액들의 합이 정답이 될 수 있다. 또한 탐색 중인 노드를 .. 2021. 12. 5. [Leetcode] 1032. Stream of Characters 문제 : https://leetcode.com/problems/stream-of-characters/ 문자열 리스트 words가 입력으로 주어지고 추가될 알파벳 소문자가 한 글자씩 입력으로 들어온다. 추가될 알파벳들은 초기 빈문자열에서 뒤에 하나씩 추가된다. 알파벳이 하나씩 추가되어 만들어진 문자열의 접미사가 words 배열에 존재하는지 판단해라. 트라이(Trie)를 만들어야 한다. words 문자열들을 뒤에서 부터 탐색하면서 트라이를 만들어간다. 예를 들어, words = ["abc", "bc", "dc"] 인 경우 [그림 1]과 같은 트라이가 만들어진다. 1번 노드가 트라이의 헤드 노드이며 빨간색 체크한 부분이 문자열의 끝을 의미한다. 알파벳들을 하나씩 받으며 만들어진 문자열을 마찬가지로 뒤에서부터 .. 2021. 12. 4. 이전 1 ··· 9 10 11 12 13 14 15 ··· 48 다음
