728x90 반응형 파이썬 알고리즘 코딩25 주식을 사고팔기 가장 좋은 시점 문제 prices 에는 주식의 매일 종가 가격이 있다고 해보자. 가장 이윤을 많이 남기는 발톱 끝에서 사서 정수리에서 파는 경우에 수익이 얼마나 되는지를 찾는 문제이다. 예제 1번이 그 예를 나타낸다. 1일 때 사서 6일 때 파니까 5라는 가장 큰 이윤이 남았다. 예제 2번에는 수익이 전혀 나지 않는 하락장이다. 직관적으로 그리디한 브루트 포스 방식으로 생각해보자. [7,1,5,3,6,4] 가 있을 때, 어떤게 오른쪽으로 가면서 가장 이윤을 볼까를 생각해보면, 가능한한 최저점을 찾고 오른쪽으로 가면서 가능한한 최고점을 찾는 방식으로 의식이 흐름이 진행된다. 그리디 하게 생각해보면 계산복잡도 $O(n^{2})$ 으로 풀어볼 수 있다. 두 쌍의 차이가 가장 큰 값을 출력하면 된다. 바로 아래와 같이 for 문을 .. 2021. 4. 11. 자신을 제외한 배열의 곱 문제 이 문제는 자신의 배열위치 인덱스가 자신을 제외한 원소들의 곱으로 이뤄진 것으로 바꾸는 문제이다. 예제 1번의 인덱스 0 에 1은 자기자신을 제외한 나머지의 곱인 2*3*4=24 로 바꾸는 것이다. 이는 모든 원소들의 곱을 구하고 각 인덱스의 값으로 나눈 값을 취하면 바로 구할 수 있다. 하지만 예제 2번과 같이 만약에 0이 존재한다면, 0으로 나눠야하는 zero division error 가 발생한다. 아래의 코드는 그리디하게 구현한 것이다. 문제의 설명대로 인덱스 값을 제외한 나머지 원소들의 곱을 해당 인덱스의 값으로 바꿔주는데 충실한 것이다. sp 라는 함수에서는 리스트내의 원소들의 곱을 리턴하는 함수 값이다. 그래서 아래의 for 문을 활용해서 처음 주어진 nums 의 원소들의 인덱스를 하나씩 뺀.. 2021. 4. 11. 배열 파티션 I 문제 n 개의 페어를 이용한 min(a, b) 합으로 만들 수 있는 가장 큰 수를 출력하라. 이 문제는 2 개 이상의 짝수로 주어지는 숫자들을 2 개씩 쌍을 지어서 쌍의 최솟값 즉, min 값을 더해서 결과적으로 가장 최대가 되는 값은 얼마인지를 묻는다. 먼저 두 쌍의 min 값을 다 더해서 최대가 되게 하려면, 오름차순으로 정렬해서 앞에서부터 두개씩 쌍을 지어서 min 값을 다 더하면 가장 큰 값을 낼 수 있다는 것을 알 수 있다. def arrayPairSum(self, nums: List[int]) -> int: nums.sort() result = 0 while nums: one = nums.pop(0) two = nums.pop(0) result += min(one, two) return result.. 2021. 4. 11. 세 수의 합 문제 배열을 입력 받아서 합으로 0을 만들 수 있는 3개의 원소를 출력하라. 세 수의 합이 0 이 되는 원소를 찾아 풀이 1) 브루트 포스 for 문을 3개 중첩하여 모든 가능한 3 원소 쌍을 만들어서 0이 되는지 비교한다. 실제 리트코드에서는 타임 아웃 된다. for 문 사이에 if 문이 의미하는 것은 이미 i, j, k 조합이 중복됨을 방지하기 위함이다. 앞에서 이미 한 것이면 생략하는 것이다.! 중복을 쉽게 피하기 위해서 nums.sort() 로 정렬을 미리 해주었다. def threeSum(self, nums: List[int]) -> List[List[int]]: results = [] nums.sort() for i in range(len(nums) - 2): if i > 0 and nums[i] .. 2021. 4. 4. 빗물 트래킹 문제 height 라는 높이가 주어질 떄, 아래의 그림의 까만색 막대에 해당된다. 비가 온 후에 저렇게 물이 고일 때 쌓인 물의 면적의 합을 구하는 문제이다. 풀이 1) 투 포인터를 최대로 이동 가장 높이가 높은 막대를 살펴보자... 높이가 3인 것을 알 수 있다. 막대는 높고 낮음에 무관하게, 전체 부피에 영향을 끼치지 않으면서 그저 왼쪽과 오른쪽을 가르는 장벽 역할을 한다.. 좌우 기둥 최대높이 left_max, right_max 라할 떄 이게 현재 높이와의 차이만큼 물 높이를 volume 에 더해준다. volume += left_max - height[left] 가 의미하는 것은 왼쪽 가장 높은 기둥에서 현재 기둥 높이를 뺀 값이다. left_max 가 2이고 height[left] 가 2이면 0으로 현.. 2021. 4. 4. 두 수의 합 문제 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. target 을 보고 nums 라는 리스트에 들어있는 원소 중 두 개를 더하여 target 이 될 수 있는 인덱스를 리턴하는 문제이다. 풀이 1) 브루트 포스로 계산. 브루트 포스(Brute-Force) 방식은 이 배열을 2번 반복하면서 즉, for 문을 두 번 돌려서 모든 가능한 두 쌍을 꾸리는 단순한 방식이다. 아래처럼 두번의 for 문 반복으로 인덱스를 출력할 수 있게 쉽게 작성할 수 있다. def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(0,len(nums)-1): for j in range(i+1,len(nums)): ans = nums[i] .. 2021. 4. 4. 이전 1 2 3 4 5 다음 728x90 반응형
