easy67 [Leetcode] 67. Add Binary 문제 : https://leetcode.com/problems/add-binary/ carry 플래그를 하나두고 a, b 문자열의 가장 뒤에서부터 수를 더해간다. (a + b + carry) / 2 나머지를 정답 문자열에 추가하고 (a + b + carry) / 2 몫을 carry에 저장한다. 이를 a, b 문자열들 중 하나의 문자열이 모두 탐색할때까지 반복한다. 이 후 a, b 문자열들 중 아직 탐색하지 않은 문자들이 남았다면 탐색이 끝날때까지 위와 같이 (남은 숫자 문자 + carry) / 2 나머지를 정답에 추가해나간다. 시간복잡도는 O(N). N = a, b 문자열들 중 최장 길이 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/.. 2021. 11. 4. [leetcode] 1137. N-th Tribonacci Number 문제 : https://leetcode.com/problems/n-th-tribonacci-number/ T(0) = 0, T(1) = 1, T(2) = 1, T(n) = T(n-1) + T(n-2) + T(n-3) n이 주어질 때, T(n) 값을 구해라. n크기의 배열을 만들어서 문제에서 주어진 점화식으로 구할 수 있다. 이 경우, 시간/공간 복잡도는 모두 O(n)이 된다. 점화식을 보면 결국 필요한 값들은 최신 값 3개 이므로 크기가 3인 배열(let, arr)을 만들고 arr[n%3] = arr[0] + arr[1] + arr[2] 위 식으로 arr을 채워나간 뒤 n번째까지 모두 채우면 arr[n%3] 가 정답이 된다. 이 경우 시간복잡도는 동일하게 O(n)이지만 공간복잡도는 O(1)이 된다. 소스.. 2021. 9. 25. [leetcode] 415. Add Strings 문제 : https://leetcode.com/problems/add-strings/ 가산기 구현 문제. 학창시절에 배운적이 있는데 그때의 기억을 되살려서.. carry 변수를 하나 둔다. 올림되는 수가 있다면 1, 아니면 0일 것이다. 입력 문자열 num1, num2의 인덱스 변수를 ind1, ind2로 두고 해당 변수들은 입력문자열의 가장 뒤의 인덱스를 초기화 값으로 가진다. 덧셈뺄셈을 할 때, 같은 자리수에 있는 수들을 더해야 하기 때문이다. num1[ind1], num2[ind2]를 각각 변수 a, b라 하자. 만일 ind1, ind2가 문자열 num1, num2의 인덱스 범위를 넘어선다면(0 미만) 0으로 본다. 탐색 후 ind1, ind2를 1씩 감소시킨다. a + b + carry 를 나누기.. 2021. 8. 11. [leetcode] 108. Convert Sorted Array to Binary Search Tree 문제 : https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/ 오름차순 정렬된 nums 배열이 주어질 때, height-balanced BST로 변형하라. height-balanced BST는 모든 노드들의 두 하위 트리깊이가 1이상 차이가 나지 않는 이진 트리이다. height-balanced BST가 뭔가 했더니 이런식으로 불균형적인 트리를 만들지말란 의미였다. [그림 1]에서 왼쪽 하위트리의 높이는 1, 오른쪽 하위트리의 높이는 3 이므로 1 이상 차이가 나서 높이 균형 BST가 아니다. 결국 노드들을 왼쪽 오른쪽 균등하게 분배하면서 bst를 만들라는 뜻이다. 정렬된 nums 배열의 중간 값을 현재 노드로 만들고 중간 값.. 2021. 7. 27. [leetcode]1047. Remove All Adjacent Duplicates In String 문제 : https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/ 문자열을 탐색하면서 정답 문자열을 만든다. 만약 탐색중인 문자가 정답 문자열의 마지막 문자와 같다면 문자를 추가하지 않고 정답 문자열의 마지막 문자를 삭제한다. 정답문자열이 비어있거나 탐색중인 문자와 정답 문자열의 마지막 문자와 다르다면 정답문자열에 탐색중인 문자를 추가한다. 시간복잡도는 O(N). N = |입력 문자열| 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1047.%20Remove%20All%20Adjacent%20Duplicates%20In%20String.cpp 2021. 6. 28. [leetcode][118] Pascal's Triangle 문제 : https://leetcode.com/problems/pascals-triangle/ numRows가 주어질 때, numRows 크기의 파스칼의 삼각형을 구하여라. 파스칼의 삼각형의 원소는 바로 위에 있는 두 원소의 합이다. answer[i][j] = answer[i-1][j-1] + answer[i-1][j] 위 연산을 모든 원소에 적용하면 답을 수할 수 있다. 시간복잡도는 1+2+ ... + numRows = 대략 O(numRows^2 /2). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/118.%20Pascal's%20Triangle.cpp 2021. 6. 22. 이전 1 2 3 4 5 6 7 ··· 12 다음
