본문 바로가기

Computer Science

 (26)
[파이썬 알고리즘] 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. 전체 코드
[파이썬 알고리즘 인터뷰] 19. 가장 긴 동일 값의 경로 1. 문제 LeetCode 687. Longest Univalue Path 이진트리 root 가 주어지면 같은 값으로 이어진 경로 중 가장 긴 경로의 길이를 리턴하여라. 2. 풀이 dfs 방식을 이용해서 풀었다. 함수가 노드를 인자로 받으면 현재 노드부터 아래로 이어지는 같은 값을 가진 노드 경로 길이를 state에 저장해 리턴한다. 또한 클래스 변수 longest를 만들고, 경로를 탐색하는 중 가장 긴 경로가 새롭게 등장하면 longest의 값을 업데이트했다. 우선 리프노드가 state가 0을 가지게 하기 위해서 현재 노드가 존재하지 않는다면 -1을 리턴한다. 그리고 왼쪽/오른쪽 자식 노드에 대해 재귀호출을 실행하고, 그 결과로 return된 state 값을 right, left 변수에 저장한다. 모든..
[파이썬 알고리즘] 18. 순열 1. 문제 leetcode 46. Permutations 서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라. 2. DFS를 이용한 풀이 이 문제는 재귀 dfs로 그래프를 탐색하여 풀 수 있다. 그래프는 []을 루트 노드로, [1,2,3], [2,1,3] 등 각 순열을 리프 노드로 삼고, 중간의 노드는 각 순열이 만들어지는 과정([1,2] 등)으로 가진다. DFS 함수의 인자로는 지금까지 만들어진 순열을 넣는 path, path에 아직 순열에 추가되지 않은 candidates를 준다. 주어진 수를 모두 순열에 사용해서 candidates가 남아있지 않다면, 지금까지 만든 순열인 path를 결과에 추가한다. 만약 순열 path에 추가할 candidates가 남아 있다면 남아있는 숫자를 모두 넣어서 DF..
[파이썬 알고리즘 인터뷰] 17. 전화번호 문자 조합 1. 문제 leetcode 17. letter combinations of a phone number 2에서 9까지 숫자가 주어졌을 때 전화번호로 조합 가능한 모든 문자를 출력하라. 숫자와 문자의 관계는 다음과 같다. 2. DFS를 이용한 해결 방법 이 문제는 하나의 경로로 탐색을 시작하면 해당 경로로 탐색을 마쳐야 한다. 따라서 DFS(깊이 우선 탐색)를 사용해야 한다. def letterCombinations(self, digits: str) -> List[str]: def dfs(index, path): # 끝까지 탐색하면 백트래킹 if len(path) == len(digits): result.append(path) return # 입력값 자릿수 단위 반복 for i in range(index, ..

티스토리툴바