배열
크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형
크기가 고정되어 있으며, 한번 생성한 배열은 크기를 변경하는 것이 불가.
크기를 지정하지 않고 자동으로 리사이징하는 배열인 동적 배열 = 파이썬에서는 리스트
파이썬은 정적 배열은 따로 제공하지 않으며 동적배열인 리스트만 제공
동적 배열의 원리
미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면, 늘려주고 모두 복사하는 식.
대개는 더블링이라 하여 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
'📓기록 > 📚books' 카테고리의 다른 글
파이썬 알고리즘 인터뷰 | 6장. 문자열 (0) | 2023.04.02 |
---|---|
파이썬 알고리즘 인터뷰 | 5장. 리스트, 딕셔너리 (0) | 2023.04.02 |
파이썬 알고리즘 인터뷰 | 4장. 빅오(Big O) (0) | 2023.04.02 |