파이썬 알고리즘 인터뷰 | 7장. 배열

배열

크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형

크기가 고정되어 있으며, 한번 생성한 배열은 크기를 변경하는 것이 불가.

크기를 지정하지 않고 자동으로 리사이징하는 배열인 동적 배열 = 파이썬에서는 리스트

파이썬은 정적 배열은 따로 제공하지 않으며 동적배열인 리스트만 제공

동적 배열의 원리

미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면, 늘려주고 모두 복사하는 식.

대개는 더블링이라 하여 2배씩 늘려줌 언어마다 늘려가는 비율은 상이하다. 파이썬의 재할당 비율(그로스 팩터, 성장 인자)은 초반에는 2배씩 늘려가지만 전체적으로는 약 1.125배로 다른 언어에 비해 다소 조금만 늘려가는 형태로 구현되어 있음

 

문제 풀어보기

두 수의 합

- 딕셔너리 저장 후 조회

#딕셔너리로 저장
nums_map={} 
for i, num in enumerate(nums):
	if target - num in nums_map:
    	return [nums_map[target-num],i]
    nums_map[num] = i

 

빗물 트래핑

- 투포인터 풀이

if not height:
	return 0

volume = 0
left,right = 0, len(height)-1
left_max, right_max = height[left], height[right]

while left < right:
	left_max, right_max = max(height[left], left_max),
    max(height[right],right_max)
    
    #더 높은 쪽으로 투 포인터 이동
    if left_max <= right_max:
    	volume += left_max-height[left]
        left += 1
    else:
    	volume += right_max-height[right]
        right -= 1
return volume

세 수의 합

i를 고정값으로 두고 투포인터로 풀이한다.

중복값이 있을 수 있으므로 중복값이 있으면 건너뛴다.

results = []
    nums.sort()

    for i in range(len(nums) - 2):
        # 중복된 값 건너뛰기
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # 간격을 좁혀가며 합 sum 계산
        left, right = i + 1, len(nums) - 1
        while left < right:
            sum = nums[i] + nums[left] + nums[right]
            if sum < 0:
                left += 1
            elif sum > 0:
                right -= 1
            else:
                # sum = 0인 경우이므로 정답 및 스킵 처리
                results.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1

    return results

배열 파티션

배열은 n개의 페어를 이루기때문에 입력값은 항상 2n개일 것

1) 오름차순 풀이

sum = 0
pair = []
nums.sort() #오름차순으로 정렬

for n in nums:
	pair.append(n)
    if len(pair) == 2:
    	sum += min(pair)
        pair = []
return sum

2) 짝수번째 수의 합 풀이

정렬을 하면 짝수번째의 수가 pair에서 항상 min값이 된다

sum = 0
nums.sort() #오름차순으로 정렬

for i,n in enumerate(nums):
	if i%2==0:
    	sum += n
return sum

 

자신을 제외한 배열의 곱

모두 곱해서 자신으로 나누는 것은 안되므로 왼쪽 곱을 구한 후 오른쪽 값을 마지막 값부터 차례대로 곱해 나간다.

output =[]
p=1
# 왼쪽 곱셈
for i in range(0,len(nums)):
	output.append(p)
    p=p*nums[i]
    
p=1
# 오른쪽 곱셈
# 오른쪽 끝에서부터 0까지 -1씩 감소
for i in range(len(nums)-1, -1, -1):
	output[i] = output[i]*p
    	p = p*nums[i]
    
return output

 

주식을 사고팔기 제일 좋은 시점

최저점을 찾아서 profit을 최대로 만든다.

profit = 0
min_price = sys.maxsize

for price in prices:
	min_price = min(price,min_price)
    	profit = max(profit, price-min_price)
return profit