본문 바로가기

삐삐리뽀/모르고리즘9

그리디 알고리즘 * 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은것만 고르는 방법 * 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제 됩니다. 거스름돈 문제 - 카운터에는 거스름돈으로 사용할 500, 100, 50, 10원 짜리 동전이 무한히 존재한다고 가정할때 손님에게 거슬러주어야할 동전의 최소 갯수구하시오. 거슬러주어야할돈 N , N은 항상 10의 배수 1. 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐단위부터 거슬러준다. n = 1260 count = 0 array = [500, 100, 50, 10] for coin in array : count += n // coin#나누기 n = n%coin#나머지 print(count.. 2021. 10. 28.
[같은 수 찾기] 1512. Number of Good Pairs Given an array of integers nums, return the number of good pairs. A pair (i, j) is called good if nums[i] == nums[j] and i int: res = 0 for i in range(len(nums)) : for j in range(i, len(nums)) : if i != j : if nums[i] == nums[j] : res += 1 return res O(n2) 시간복잡도 최악ㅋ 고인물의 솔루션 더보기 def numIdenticalPairs(self, A): return sum(k * (k - 1) / 2 for k in collections.Counter(A).values()) def numIdenticalP.. 2021. 10. 26.
1689. Partitioning Into Minimum Number Of Deci-Binary Numbers 십진수 n이 주어지면 1,0으로 이루어진 deci-binary로 구성할수있는 최소 갯수를 리턴 A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not. Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n. 예 1 ) Input: n = .. 2021. 10. 26.
1470. Shuffle the Array 배열섞기 leedcode Easy 1470. Shuffle the Array Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn]. Return the array in the form [x1,y1,x2,y2,...,xn,yn]. 더보기 def shuffle(self, nums: List[int], n: int) -> List[int]: numlen = len(nums) -1 res = [] for i in range(n) : res.append(nums[i]) res.append(nums[numlen-(n-i-1)]) return res def shuffle(self, nums: List[int], n: int).. 2021. 10. 26.

티스토리툴바