한 번의 거래로 낼 수 있는 최대 이익을 산출하라. 구하는 방법은 간단하다. 저점에 사서 고점에 파는 것이다. 가장 쉽게 구하는 방법은 현재 시점에서 가장 높게 팔 수 있는 가격과의 차이를 구하여 비교하는 방법인데 이 방법은 n의 제곱으로 매우 오래 걸린다. 이를 O(n)에 해결하기 위해 저점을 구한 후, 가격차이 값을 갱신해 가며 max 값을 구하는 방식으로 해결한다. 먼저, 저점과 이익의 값을 초기화 한다. min_price = sys.maxsize profit = 0 그 다음 price 값을 살펴보며, 저점을 설정하고 저점과 현재 가격의 차이를 비교하여 최대 이익을 갱신한다. for price in prices: min_price = min(min_price, price) profit = max(p..

배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라. - 주의 : 나눗셈을 하지 않고 O(n)에 풀이하라. 이 문제를 보고 맨처음 든 생각은 전체곱에서 나누는 것이다. 그런데 나눗셈을 하면 안된다고 적혀있으니 다음 방법은 본인을 제외한 모든 수를 곱하는 것인데 이 또한 n 제곱의 시간이 걸리므로 불가능 하다. 보통 이러할 때 쓸 수 있는 방법은 시간 대신 메모리를 쓰는 것이다. 본인의 왼쪽까지의 순차적으로 누적 곱을 저장한 배열과 본인의 오른쪽 까지의 순차적으로 누적 곱을 저장한 값을 활용하여 문제를 풀이한다. 예를들어, [1,2,3,4] 라는 배열이 있다고 가정하자. 먼저 자신의 왼쪽 까지의 순차적 곱을 정리한 배열은 [1, 1, 2, 6]이 될 것이다. ..

n 개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수를 출력하라. 보면 이해가 안가는 문구이지만, 예제를 보고 이해하였다. 2n 개의 원소가 주어지는데 이를 n개의 min(a,b) 페어로 만든 후 그 페어들의 합이 가장 큰 경우를 출력하라는 뜻이다. 이를 해결하는 방법은 아주 간단하다. 배열을 작은 수 부터 정렬하는 것이다. 그렇게 하면 앞에서 부터 2개씩 끊었을 때, 최소 값이 더 작아지는 것을 막을 수 있다. 전체 코드는 다음과 같다. class Solution: def arrayPairSum(self, nums: List[int]) -> int: nums.sort() answer = 0 for i in range(0, len(nums), 2): answer += nums[i] ..

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라. 이 또한 모든 경우의 수를 계산하면 n의 3승으로 매우 오래 걸린다. 그래서 이 문제도 투포인터로 해결한다. 먼저 배열을 정렬한다. nums.sort() 그 다음, 각 원소마다 for문을 돌며 3수의 합을 찾는다. for i in range(len(nums)-2): if i > 0 and nums[i] == nums[i-1]: continue i 가 i-1과 같다면 같은 결과가 나올 것이기에 이는 넘어가주는 조건문을 작성한다. left, right = i+1, len(nums)-1 while left < right: sum = nums[i] + nums[left] + nums[right] if sum == 0: result = [nu..

높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 이 문제는 투 포인터를 사용하여 해결한다. 투 포인터는 2개의 포인터를 가지고 리스트에 접근하는 알고리즘이다. 보통 조건에 따라 좌/우 포인터를 조작하고 그 행위를 좌측 포인터가 우측 포인터를 넘어갈 때 종료하는 식으로 접근하였던 것 같다. 이 문제 또한 이러한 매커니즘으로 접근해본다. 먼저 설정하는 조건은 다음과 같다. 왼쪽에서 설정한 left_max 값이 오른쪽에서 설정한 right_max 값 보다 낮으면 right를 가운데로 당겨오고, 그렇지 않으면 left를 가운데로 당겨가는 식이다. 먼저, left/right 포인터와 초기 left_max/right_max 값을 설정한다. volume = 0 left, right = 0, l..

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. 처음 이 문제를 접하게 되면, 모든 경우의 수에 대한 조사를 할 것이다. 나 또한 그렇게 해결하였지만 이는 n의 제곱의 경우의 수로 매우 비효율 적이다. 그래서 파이썬으로 이러한 최적화 문제를 풀 때 가장 유용한 것은 딕셔너리를 이용하는 것이다. 예를들어 [2,3,7] 에서 3이라는 값이나 인덱스를 찾으려면 in이나 index 함수를 사용하여야 하는데 이는 O(n)이다. 하지만 이를 딕셔너리로 변환하여 'Dict[값] = 인덱스' 형태로 저장하면 해당 값의 인덱스를 찾거나, 해당 값이 있는지 확인하는데 걸리는 시간은 O(1)이 된다. 이를 활용하여 이 문제를 해결해보자. 먼저, 딕셔너리 형태로 배열을 정리한다. num_dict = {} ..