알고리즘 문제/Leetcode283 [Leetcode] 77. Combinations 문제 : https://leetcode.com/problems/combinations/ 백트래킹 문제. for(i = 현재 탐색중인 인덱스 ~ n){ arr 배열 뒤에 i 추가 재귀함수(i+1, arr); // 인덱스를 i+1부터 다시 탐색 arr 배열 뒤에 i 제거 } 위와 같은 재귀함수를 만들어서 arr 배열 크기가 k라면 정답 배열에 arr을 추가한다. 시간복잡도는 K크기의 배열을 만들므로 대충 O(N! / (N-K)!) 이 정도 나올듯. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/77.%20Combinations.cpp 2021. 11. 10. [Leetcode] 43. Multiply Strings 문제 : https://leetcode.com/problems/multiply-strings/ 음이 아닌 정수 num1, num2가 문자열로 주어질 때, num1, num2의 곱을 구하라. index 0 1 2 1 2 3 x 4 5 6(v) ----------- 1 8 1 2 6 ind 0 1 2 1 2 3 x 4 5(v) 6 ----------- 1 5 1 0 5 ind 0 1 2 1 2 3 x 4(v) 5 6 ----------- 1 2 8 4 index 0 1 2 3 4 5 1 8 1 2 6 1 5 1 0 5 1 2 8 +. 4 -------------------- 0 5 5 8 8 8 123 * 456 을 예로 들어보자. 한자리 수 씩 곱하는 경우 최소 한자리 최대 두자리가 나온다. (최대 : 9.. 2021. 11. 8. [Leetcode] 94. Binary Tree Inorder Traversal 문제 : https://leetcode.com/problems/binary-tree-inorder-traversal/ 이진 트리의 루트가 입력값으로 주어지면 중위 순회한 결과를 반환해라. 재귀함수를 하나만들고 왼쪽 자식 노드로 탐색. 현재 노드의 값을 정답 배열에 저장. 오른쪽 자식 노드로 탐색. 만일 현재 탐색하는 노드가 null 이면 재귀함수를 종료한다. 시간복잡도는 O(N). N = 이진트리 노드 수 소스코드 : 2021. 11. 5. [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]11. Container With Most Water 문제 : https://leetcode.com/problems/container-with-most-water/ 수직선 높이를 나타내는 배열이 주어진다. 두 개의 수직선을 선택해서 그 사이에 물을 넣는다고 할 때 가능한 최대 용량은 얼마인가. 투포인터로 푼다. 왼쪽부터 시작하는 left 포인터, 오른쪽부터 시작하는 right 포인터가 있다. left, right 수직선을 선택했을 때의 용량을 구하고 이들 중 최대 값이 정답이 된다. 용량을 구한뒤 left가 right보다 낮다면 left를 +1 하고, right가 left보다 낮다면 right를 -1 해준다. 시간복잡도는 O(N). N = 배열의 크기 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/lee.. 2021. 11. 3. [Leetcode] 980. Unique Paths III 문제 : https://leetcode.com/problems/unique-paths-iii/ m x n 정수형 배열 grid가 주어진다. 1 : 시작 지점. (1개 존재) 2 : 종료 지점. (1개 존재) 0 : 걸을 수 있는 곳 -1 : 장애물 상하좌우 4방향으로 이동가능할 때, 시작지점에서 종료지점으로 갈 수 있는 방법의 수를 구하라. 백트래킹. 시작지점부터 장애물이 아닌 곳으로 이동하면서 이동횟수를 저장하면서 상하좌우 방향으로 탐색한다. 탐색하면서 지나간 자리는 다시 못 지나가게 별도의 플래그 배열에 탐색한 위치는 표시를 해둔다. 종료지점에 도달했을 때, 걸음의 수가 grid 배열의 0, 2 cell의 수와 같다면 정답이 가능하므로 정답 방법의 수에 1을 더한다. 시간복잡도는..? 소스코드 : h.. 2021. 11. 2. 이전 1 ··· 13 14 15 16 17 18 19 ··· 48 다음