- 자료구조는 크게 <메모리 공간 기반의 연속 방식>, <포인터 기반의 연결 방식> 으로 나뉜다.
- 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다.
- 그리고 배열은 데이터를 나열하고, 각 데이터를 인덱스로 접근할 수 있도록 구성한 데이터의 구조이다.
- 파이썬에서는 리스트 타입이 배열 기능 제공
- 배열 사용 이유
- 같은 종류의 데이터를 따로 따로 저장하는 것이 아니라 하나의 변수에 한꺼번에 저장하여 효율적으로 관리하기 위함
- 각 데이터의 접근이 쉽고 빨라진다. (데이터의 위치(인덱스값)를 이용해서 데이터에 접근하기 때문에
- 단점으로는 데이터의 추가나 삭제가 어렵다.(파이썬에서는 가능)
특히 c언어의 같은 경우에 미리 배열의 길이를 지정해야 한다.
- 파이썬에서 배열 사용
시퀀스 타입 : 리스트(list) [ ], 딕셔너리(dictionary) { }, 집합(set) { }, 튜플(tuple) ( )
2.1 파이썬에서 리스트, 딕셔너리, 튜플의 차이점
- 리스트([ ] 사용) : 특정 데이터들의 배열, 데이터들의 값을 추가하거나 삭제할 수 있다.
- 튜플(( ) 사용) : 특정 데이터들의 배열이지만 데이터들을 추가하거나 삭제할 수 없다.
- 딕셔너리({ } 사용) : 리스트와 튜플이 어떤 값을 담기만 했다면 딕셔너리는 키(key)와 값을 가지는 데이터구조로서 키와 값이 연결되어있다. 또한 리스트와 튜플은 순서가 있고 인덱스값으로 데이터 값에 접근할 수 있지만 딕셔너리는 순서가 없고 키를 통해서 키의 데이터값에 접근할 수 있다.
＊ 참고) 그럼 튜플을 굳이 왜 사용하나요 ?
보통 튜플은 요소가 절대 변경되지 않고 유지되어야 할 때 사용된다. 튜플을 만든 상태에서 요소를 변경하려면 에러가 발생하기 때문에 요소를 실수로 변경하는 경우를 방지해준다. 예를 들면, 사람들의 주민번호를 변경되지 않기 때문에 튜플로 저장할 수 있지만 핸드폰 번호는 변경되는 경우가 종종 있으므로 리스트로 저장하면 된다.
2.2. 리스트로 배열 사용
-
1차원 배열
-
2차원 배열
-
리스트에 데이터 추가하기 (append)
-
리스트 특정 인덱스에 데이터 추가하기 (insert)
-
리스트 정렬하기 (내림차순 : reverse)
-
리스트 정렬하기 (오름차순 : sort)
-
기존 리스트에 새로운 리스트 이어붙여서 추가하기 (extend)
-
리스트의 특정 데이터 개수 출력 (count)
-
특정 데이터의 인덱스값 출력하기 (index)
-
마지막 데이터값 제거하기 (pop)
-
특정 데이터값 제거하기 (첫 번째로 나오는 데이터 제거: remove)
정말 리스트를 포함한 시퀀스의 기능은 무수히 많기 때문에 리스트 기능 중 자주 쓰이는 것만 정리를 해봤다. 이제는 배열에 대한 문제를 풀어보도록 하자.
- 세 수의 합 (leetcode: 15. 3Sum)
: 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.
- 입력
nums = [-1, 0, 1, 2, -1, -4]- 출력
[ [ -1, 0, 1], [-1, -1, 2] ]
이 문제의 접근 방식은 브루트 포스와 투 포인터로 합계산을 얘기하고 싶다.
<브루트 포스로 계산>
def threeSum(self, nums: List[int]) -> List[List[int]]:
results = [] # 답을 담을 그릇
nums.sort() # 리스트를 정렬해 가장 낮은 순으로 정렬
# 브루트 포스 n^3 반복
for i in range(len(nums) -2):
# 중복된 값 건너뛰기
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums) - 1):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
for k in range(j + 1, len(nums)):
if k > j + 1 and nums[k] == nums[k - 1]:
continue
if nums[i] + nums[j] + nums[k] == 0:
results.append((nums[i], nums[j], nums[k]))
return results이 풀이는 리트코드에 제출하면 시간초과가 나온다. 확실히 과격한 방법이다. 다음으로는 투 포인터로 계산하는 방식이다.
< 투 포인터로 합 계산>
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] == 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 # 작은 순으로 정렬했기 때문에 left 값을 올린다.
elif sum > 0:
right -= 1 # right 값을 내린다.
else:
# sum = 0인 경우이므로 정답 및 스킵 처리
results.append((nums[i], nums[left], nums[right]))
# left, 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<브루트 포스> 풀이 방법보다 코드가 길지만 확실히 더 빠른 장점을 보여준다.
- 배열 파티션 (leetcode: 561. Array Partition )
: n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.
-입력
[1, 4, 3, 2]
-출력
4
이 문제는 오름차순 풀이, 짝수 번째 값 계산 풀이, 파이썬 다운 방식 풀이 3가지의 방식 풀이를 해보겠다.
< 오름차순 풀이>
from typing import List
def arrayPairSum(self, nums: List[int]) -> int:
sum = 0
pair = [] #
nums.sort() # 작은 순으로 정렬 ex) [1,2,3,4]
for n in nums:
# 앞에서부터 오름차순으로 페어를 만들어서 합 계산
pair.append(n)
if len(pair) == 2:
# ex) pair = [1, 2] -> min = 1
# ex) pair = [3, 4] -> min = 3
sum += min(pair)
# 물론 다 썻으면 pair를 비워줘야 한다.
pair = []
return sum< 짝수 번째 값 계산>
from typing import List
def arrayPairSum(self, nums: List[int]) -> int:
sum = 0
nums.sort() # ex) [1,3,2,4] -> [1,2,3,4]
# enumerate는 (i:인덱스 와 n:변수안의 값)으로 뽑아주는 함수이다.
for i, n in enumerate(nums):
# 짝수 번째 값의 합 계산
# 여기서부터 이해가 힘들진 모르지만, [1,2,3,4] 리스트를
# 인덱스 0번과 2번인 짝수만 더하면 답이 나오는 것을 볼 수 있다.
if i % 2 == 0:
sum += n
return sum< 파이썬 다운 방식 풀이>
from typing import List
def arrayPairSum(self, nums: List[int]) -> int:
return sum(sorted(nums)[::2])
# 참 어이가 없겠지만 sorted로 nums를 정렬해준 다음
# 슬라이싱으로 2칸씩 가면서 값을 더해주겠다는 코드이다.
# 이런걸 봤을 때 파이썬언어가 참 파격적인 언어인 것을 느낄 수 있다.