Computer Science/자료구조 (7) 썸네일형 리스트형 [파이썬 알고리즘] 25. 부분 집합 1. 문제 Leetcode 78. subsets 정수형 배열 nums가 주어지면, 부분 집합을 모두 리턴하여라. 2. 풀이 DFS를 이용해서 탐색을 진행한다. 먼저 중복되지 않는 부분집합을 만들기 위해서는 한번 고른 원소 뒤에 있는 원소만 고른다는 규칙을 설정해주어야 한다. 이를 확인하기 위해, index라는 변수에 지금까지 탐색한 원소 중 가장 뒤에 있는 원소의 index를 저장한다. 탐색은 index 이후의 원소에 대해서만 진행한다. 그리고 변수 path에는 현재 탐색 중인 부분집합을 저장한다. path에 index 이후의 원소를 하나씩 추가하고, 다시 dfs 함수를 호출하는 방식으로 탐색을 진행한다. 또한 모든 부분 집합을 리턴해야 함으로 dfs 함수가 실행될 때마다 path를 result에 추가하.. [파이썬 알고리즘] 24. 이진 트리 합의 범위 1. 문제 Leetcode 938. 938. Range Sum of BST 이진 탐색 트리가 주어졌을 때 low 이상, high 이하의 값을 가진 노드의 합을 구하여라. 2. 재귀 구조 DFS를 이용한 풀이 이진 탐색 트리의 정의는 지난 글에서 정리했고, 간단히 말하면 정렬된 트리라고 할 수 있다. https://baechu-story.tistory.com/41 [파이썬 알고리즘] 23. 이진 탐색 트리(BST)를 더 큰 수 합계 트리로 1. 문제 leetcode 1038. Binary Search Tree to Greater Sum Tree 이진 탐색 트리(BST)의 루트가 주어지면, 해당 트리의 값을 트리에서 자기 자신보다 큰 수의 합 + 자기 자신의 값으로 바꾸어라. 2. 풀이 과정.. baechu.. [파이썬 알고리즘] 23. 이진 탐색 트리(BST)를 더 큰 수 합계 트리로 1. 문제 leetcode 1038. Binary Search Tree to Greater Sum Tree 이진 탐색 트리(BST)의 루트가 주어지면, 해당 트리의 값을 트리에서 자기 자신보다 큰 수의 합 + 자기 자신의 값으로 바꾸어라. 2. 풀이 과정 먼저 이진 탐색 트리는 다음과 같은 특성을 가지고 있다. 1. 왼쪽의 서브트리에 노드 값이 자신 이하이다. 2. 오른쪽의 서브트리에 노드 값이 자신 이상이다. 3. 왼쪽과 오른쪽의 서브트리가 모두 이진 탐색 트리이다. 이처럼 이진 탐색 트리는 정렬된 트리라고 할 수 있고, 탐색 시 시간 복잡도가 O(logn)에 불과하다. 주어진 문제에서는 트리를 큰 값부터 차례대로 탐색해야 한다. 따라서 재귀함수를 이용해 오른쪽 노드를 먼저 탐색하고, 자기 자신, 왼쪽.. [파이썬 알고리즘 인터뷰] 22. 배열의 이진 탐색 트리 변환 1. 문제 leetcode 108. Convert Sorted Array to Binary Search Tree 주어진 정렬된 배열을 모든 서브트리의 높이 차이가 2 이상 나지 않는 이진 탐색 트리로 바꾸어라. 2. 해결 방법 재귀 방식의 dfs로 문제를 풀었다. 함수는 인자로 자신과 자식노드들의 값이 될 배열의 값을 전달받고, 노드를 만들어 리턴한다. 먼저 배열의 가운데 위치한 값을 루트노드의 값으로 지정한다. 가운데 값은 몫을 계산하는 // 연산자를 이용해 계산한다. 그리고 그 값 기준으로 왼쪽에 있는 값들의 리스트는 왼쪽노드를 생성할 재귀함수의 인자로, 오른쪽에 있는 값들의 리스트는 오른쪽 노드를 생성할 재귀함수의 인자로 전달한다. 각 함수의 실행이 끝나면 node.left, node.right에 .. [파이썬 알고리즘] 21. 균형 이진 트리 1. 문제 leetcode 110. Balanced Binary Tree 이진 트리가 높이 균형인지 판단하라. 높이 균형은 모든 노드의 서브 트리 높이 차이가 1이하인 것을 말한다. 2. 내 풀이 재귀 방식의 dfs를 이용했다. dfs 함수가 자기자신부터 시작하는 트리의 높이를 리턴하도록 했다. 리프노드에 도달하면 1을 리턴하고, 노드가 존재하지 않으면 0을 리턴했다. 리프노드를 제외한 다른 노드에서는 자식 노드의 값 중 큰 값에 1을 더해서 리턴했다. 두 자식 노드에서 리턴한 값 차이가 2 이상이 나면 class 변수 answer을 False로 바꿨다. 탐색이 종료되면 answer를 리턴한다. 3. 전체 코드 재귀함수를 이용해서 행렬의 곱 구하기 #include #include void matrix_mul(int** matrix_A, int** matrix_B, int** matrix_C, int len, int i, int j, int k) { /* 행렬의 길이가 2일때 행렬곱 계산하고 종료하기 */ if (len == 2) { matrix_C[i][k] += matrix_A[i][j]* matrix_B[j][k] + matrix_A[i][j + 1]* matrix_B[j + 1][k]; matrix_C[i][k + 1] += matrix_A[i][j]* matrix_B[j][k + 1] + matrix_A[i][j + 1]* matrix_B[j + 1][k + 1]; matrix_C[i + 1][k] += matrix_A[i + 1][j]* .. [C] 시간복잡도가 O(n)인 재귀함수로 피보나치 수열 구하기 앞으로 2학년 때 들었던 자료구조 수업의 내용들을 복습해보려고 한다. 그 학기에 배웠던 여러 과목 중에 가장 어려웠고, 그만큼 중요한 수업이기 때문이다. 오늘은 그 첫 번째로 C언어를 이용해 시간복잡도가 O(n)인 재귀 구조의 피보나치수열을 만들었던 것을 살펴보려고 한다. 1. 시간복잡도가 O(n^2)인 경우 피보나치 수열을 구현하는 방법은 재귀 함수, 반복문 두 가지가 있다. 그중 재귀함수를 이용해 피보나치수열을 구하면 일반적으로 O(n^2)의 시간복잡도를 가진다. long long fib(int n) { if ( n T(n-2) 임으로, 2 이상의 n에 대하여 다음이 성립한다. T(n) = T(n-1) + T(n-2) + 1 > 2 x T(n-2) > 2^2 x T(n -4).... > 2^n/2 x.. 이전 1 다음
