00/algorithm (55) 썸네일형 리스트형 Greedy algorithm - An algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solution are best fit for Greedy. - Fractional Knapsack Problem, the local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads .. Union Find Find(x): get the identity of the group that the element x belongs to. Union(x, y): merge the two groups that the two elements belong to respectively. class DisjointSetUnion(object): def __init__(self, size) : self.parent = [i for i in range(size+1)] self.size = [1]*(size+1) def find(self, x): if self.parent[x] != x : self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self.. Trie Trie is an efficient information retrieval data structure. Every node of Trie consists of multiple branches. Each branch presents a possible character of keys. We need to mark the last node of every key as end of word node. class TrieNode: def __init__(self): self.children = [None]*26 self.isEndOfWord = False class Trie: def __init__(self): self.root = TrieNode() def _charToIndex(self, ch): retu.. 힙 정렬 Heap - 큰 키에 자주 액세스하거나 키(우선 순위) 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한 자료구조. - 한 노드가 최대 두 개의 자식노드를 가지면서, 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 완전 이진 트리를 기본으로 함. Heap 이 되기 위한 조건 1. 구조 조건 - 완전 이진 트리 2. 순서 조건 - Partial Order, 값의 순서가 직계 관계(부모-자식)에서만 성립. 이진 탐색 트리와의 비교 - 힙은 각 자식 < 부모. (최대 힙 트리라 가정.) - 이진 탐색트리는 왼쪽 자식 < 부모 < 오른쪽 자식. 따라서, 힙은 우선순위 정렬에, 이진 탐색 트리는 탐색에 강점을 지닌 자료구조. def heapify(unsorted, index, heap_size) : larg.. N-Queens The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively. 어떻게 풀면 좋을까? 일단 퀸은 오와 열, 대각선 방향으로 칸 수에 상관없이 움직일 수 있.. Coin Change (DP) You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. 이 문제는 자신이 카페 알바생이라고 생각하며 풀어보자. 당신은 손님들에게 거스름돈을 어떻게 남겨줄것인가?손님들은 되도록이면 잔돈의 수가 적기를 바랄 것이다.아마 보통 알바생들은 가장 큰 단위의 돈부터 집어들고 점점 더 작은 단위로 내려가면서 돌.. 중복 있는 순열 문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라. 문자는 중복되어 나타날 수 있지만, 나열된 순열은 서로 중복되면 안 된다. 이 문제에서는 중복된 순열을 어떻게 찾아낼 것인가에 대하여 생각해보아야 한다.단순히 모든 순열을 구한 후에 배열에 이 순열이 존재하지않으면 추가하는 방법으로 해결할 수 있다. 하지만 이 해결책은 최악의 경우 시간이 소요될 것이다. 그럼, 어떻게 접근해야할까? 먼저 작은 문제로 쪼개서 생각해보자.'abca'라는 문자열이 주어졌다. 이 문자열의 순열을 구하려면 어떻게 해야할까?중복 없는 순열을 풀때와 같이 문자열의 한 문자와 나머지 문자열의 순열을 구하고 이를 모두 합치면 된다.수식으로 표현해보자면 다음과 같다. 하지만, 중복이 있는 문자열의 경우라면 빨간색으로 표.. 중복 없는 순열 문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라. 단, 문자는 중복되어 나타날 수 없다. 다른 문제들과 마찬가지로, 작은 문제에서부터 확장하는 방식으로 생각해보자. (1) 길이가 1인 문자열 (2) 길이가 2인 문자열 그렇다면 길이가 3인 문자열은 어떻게 만들 수 있을까? 배열의 모든 요소를 첫번째로 놓고 나머지 요소들의 순열을 덧붙이면된다.문제가 훨씬 쉬워졌다! 그림으로 표현하자면 다음과 같다. 그럼 이제 코드로 표현을 해보자.재귀 함수를 쓰면 아주 간단하게 표현할 수 있다. 123456789101112131415161718class Solution: def permute(self, nums: List[int]) -> List[List[int]]: def backtrack(start.. 이전 1 2 3 4 ··· 7 다음
