[자료구조] 배열(Array)

❗️ 계속해서 업데이트 될 예정...

잘못된 부분이 있다면 알려주세요 🙏

배열

배열이란

배열은 자료구조에서 선형 구조의 가장 기본이 되는 자료형이다. 어느 위치에서나 O(1)에 조회가 가능하다. 왜냐하면 배열은 연속적으로 메모리에 올라가기 때문에 3번째 값을 얻고 싶으면 int를 기준으로 해당 배열의 메모리 시작 주소에서 (3-1)*4 만큼 이동하면 되기 때문이다.

# int 형은 4바이트, 4 bytes * 8 = 32 bit
a = [1,2,3,4]

print(id(a))
print(id(a[0]))		# 140725541174336
print(id(a[1]))		# 140725541174368
print(id(a[2]))		# 140725541174400
print(id(a[3]))		# 140725541174432

동적 배열

배열은 고정된 크기만큼 연속된 메모리에 할당한다. 만약 데이터의 크기를 가늠할 수 없는 경우 너무 작은 영역을 할당하여 부족하거나, 너무 많은 영역을 할당하여 낭비될 수 있다. 그렇기에 미리 크기를 지정하지 않고 자동으로 크기를 조정해주는 배열이 동적 배열이다.
Python은 정적 배열 자체가 없고 오직 동적 배열만 존재하는데 바로 list이다.

파이썬에서의 배열

list 동작 방식

처음에는 메모리를 작게 할당하여 리스트를 생성한다. 그리고 데이터를 추가하다 다 채워지면 새로운 공간에 더 큰 크기의 배열을 할당하고 기존 데이터를 복사하는 작업이 필요하다. 그렇기에 O(n)의 비용이 발생된다. 하지만 이는 최악의 경우로 자주 일어나는 일이 아니므로 O(1)이라고 생각해도 무관하다.

투 포인터(Two Pointers)

대게 시작과 끝, 왼쪽과 오른쪽 포인터를 기준으로 문제를 푸는 전략을 말한다. 범위를 좁히기 위해서 일반적으로 정렬되어 있는 배열에 사용할 때 좀 더 효율적이다.

슬라이딩 윈도우

투 포인터와 비슷하지만 고정된 사이즈의 윈도우를 이용하는 것이 차이점이다. 또한 보통 정렬된 대상으로 하는 투 포인터와 달리 정렬 여부와 상관없이 활용된다.

배열 문제풀이

---

문제 3273

✏️ 내가 작성한 코드

left, right = 0, int(input()) - 1
arr = sorted(list(map(int, input().split())))
x = int(input())
cnt = 0
while left != right:
    if arr[left] + arr[right] > x:
        right -= 1
    elif arr[left] + arr[right] == x:
        cnt += 1
        if arr[left] == arr[left+1]:
            left += 1
        else:
            right -= 1
    elif arr[left] + arr[right] < x:
        left += 1
print(cnt)

투 포인터를 이용한 풀이. left는 인덱스를 +1하고 right는 인덱스를 -1하면 조건을 만족할 경우 cnt를 +1한다.

left, right = 0, int(input()) - 1
arr = sorted(list(map(int, input().split())))
x = int(input())
cnt = 0
while left != right:
    if arr[left] + arr[right] > x:
        right -= 1
    elif arr[left] + arr[right] == x:
        cnt += 1
        right -= 1
    elif arr[left] + arr[right] < x:
        left += 1
print(cnt)

문제에서 서로 다른 수로 배열이 구성되어 있다고 했으니, 굳이 배열에서 서로 같은 값이 있는 지 확인할 if문은 필요 없다.

n = input()
arr = set(map(int, input().split()))
x = int(input())
cnt = 0
for i in arr:
    if x - i in arr:
        cnt += 1
print(cnt//2)

투 포인터 방식이 아니여도 in을 이용한 탐색으로 풀 수 있다. 문제에서 동일한 값이 없다고 했기때문에 set을 이용해 정렬해준다.

---

문제 2003

✏️ 내가 작성한 코드

N, M = map(int, input().split())
arr = list(map(int, input().split()))
start, end = 0, 1
cnt = 0

while start <= N and end <= N:
    if sum(arr[start:end]) == M:
        cnt += 1
        start += 1
        end += 1
    elif sum(arr[start:end]) > M:
        start += 1
    else:
        end += 1

print(cnt)   

투 포인터를 이용한 풀이.

---

문제 1806

✏️ 내가 작성한 코드

N, S = map(int, input().split())
arr = list(map(int, input().split()))

sum_arr = [0] * (N+1)
for i in range(1, N+1):
    sum_arr[i] = sum_arr[i-1] + arr[i-1]
    
start, end = 0, 1
answer = 100001

while start < N and end <= N:
    if sum_arr[end] - sum_arr[start] >= S:
        answer = min(answer, end-start)
        start += 1
    else:
        end += 1
        
if answer == 100001:
    print(0)
else:
    print(answer)   

투 포인터로 푼 문제. 가장 먼저 모든 배열의 합을 리스트로 만들어 놓는다. 문제에서 S 이상이 되는 것 중 가장 짧은 길이의 배열을 찾으라고 했는데 처음에 문제를 제대로 읽지 않아 S 인것만 찾는 코드를 짰다. 그래서 되게 쉬운 문제인데 오래걸렸다.😭