[코딩테스트] 섹션2 - List

리스트(List)

리스트(List)는 일반적으로 Set과 비교됩니다.

Set에서는 (1, 2, 3), (3, 1, 2), (2, 3, 1)은 모두 동일한 집합을 나타내는 것으로 간주됩니다.

하지만 리스트에서는 [1, 2, 3]과 [3, 1, 2]는 서로 다른 요소의 순서를 가지므로 다른 리스트로 취급됩니다.

 

즉, 리스트에서는 요소의 순서가 중요하게 다뤄집니다.

Array list: array를 기반으로 구현된 리스트입니다. 이는 연속적으로 메모리에 저장되어 있는 데이터를 활용하여 리스트를 구성합니다.

Linked list: 메모리상에서 비연속적으로 저장되어 있는 노드들을 연결하여 리스트를 저장하는 방식입니다.

 

List로 분류되는 자료구조는 Python에서 Array list로 구현할 수 있으며, Linked list로도 구현할 수 있습니다.

Python에서 이미 Array list를 구현한 자료구조가 있으며, 그 이름은 list입니다.

이 Array list는 실제로 Array나 Dynamic array로 구현될 수 있는데, Python에서는 Dynamic array로 구현되어 있습니다. Dynamic array도 사실은 Array로 구현된 것입니다. 따라서, Array와 Dynamic array를 이해한다면 list 자료구조를 이해할 수 있습니다.

---

배열(Array)

배열의 특성

1. 고정된 저장 공간(fixed-size)

2. 순차적인 데이터 저장(order)

 

배열은 선언시에 size를 정하여 해당 size만큼의 연속된 메모리를 할당 받아 data를 연속적/순차적으로 저장하는 자료구조 입니다.

int arr[5] = {3,7,4,2,6}

위의 예시에서는 배열의 size를 5로 정했기 때문에 int형 데이터 4byte 5개를 저장할 메모리 공간인 20 Byte를 미리 할당을 받습니다.

이처럼 고정된 size를 갖게 되기 때문에 static array라고 부르기도 합니다.

 

4byte(int형 데이터) * 5(size) = 20byte

 

또한 배열의 데이터를 연속적이고 순차적으로 메모리에 저장합니다.

 

메모리에 저장된 데이터에 접근하려면 주소값을 알아야 한다.

배열변수 (arr)는 자신이 할당받은 메모리의 첫 번째 주소값(0x4AF57)을 가리킨다.

배열은 연속적/순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능하다.

이를 direct access 또는 random access라고 부른다.

 

만약 첫 번째 데이터가 저장된 주소값이 (0x4AF57)라면 2번째 데이터는 (0x4AF57 + 4 * 1)에, 3번째 데이터는 (0x4AF57 + 4 * 2), n번째 데이터는 (0x4AF57 + 4 * n)에 저장되어 있다. 아무리 긴 배열이라고 한 번의 연산으로 원하는 데이터에 바로 접근이 가능하다. 즉 O(1)의 시간복잡도를 갖는다.

 

Linked list는 메모리상에서 연속적/순차적으로 저장되어 있지 않기 때문에 random access는 불가능하다.

n번째 데이터에 접근하기 위해서 array는 1번의 연산만 해도 되지만 O(1),

linked list는 n번의 연산을 해야 하기 때문에 시간복잡도는 O(n)이다.

---

static array의 한계

데이터의 갯수가 정해져 있는 경우에는 static array를 사용하는 것이 매우 효율적이다.

하지만 선언 시에 정한 size 보다 더 많은 데이터를 저장해야 하는 경우 공간이 남아있지 않아서 문제가 발생할 수 있다.

그렇다고 매번 크기가 엄청 큰 배열을 선언하면 메모리 비효율이 발생한다.

그래서 이런 문제점을 해결할 수 있는 것이 dynamic array이다.

---

동적배열(Dynamic array)

선언 이후 size를 변경할 수 없는 정적배열과 다르게 동적배열은 size를 늘릴 수 있다. fixed-size 인 static array의 한계점을 보안하고자 만들었다.

동적배열(dynamic array)은 배열의 크기(size)를 변경(resizeing)할 수 있는 배열입니다.

fixed-size인 static array를 보안하고자 고안되었습니다. 

동적 배열에 데이터를 계속 추가하다가 기존에 할당된 size를 초과하게 되면, size를 늘린 배열을 새로 선언하고 그곳으로 모든 데이터를 옮긴다. 그리고 기존의 배열은 삭제 한다. 이 과정을 resize라고 한다.

resize를 한 칸씩 늘린다면 비효율적이므로 일반적이므로 2배 큰  크기로 resize 합니다. 이를 더블링이라고 합니다.

resize 덕분에 데이터를 추가 저장할 수 있게 됩니다.

---

Dynamic Array 사용법

선언시에 배열의 크기를 정하지 않아도 되기 때문에 코딩테스트에서 dynamic array를 자주 사용하게 됩니다.

python 에서는 list 자료형을 통해 dynamic array을 이미 잘 구현해 두었기 때문에 직접 구현할 필요 없이 사용할 수 있습니다.

즉 문제에서 배열을 사용해야 하는 경우에는 list를 선언하여 사용하면 됩니다. 

우리가 익혀야 할 것은 list의 연산들과 시간복잡도 입니다.

 

Array list를 static array로 구현하는 시간복잡도 | Array list를 Dynamic array로 구현하는 시간복잡도

	Static array	Dynamic array
access / update	O(1)	O(1)
insert_back	O(1)	amortized O(1)
delete_back	O(1)	O(1)
insert_at	O(n)	O(n)
delete_at	O(n)	O(n)

access / update : 접근 / 업데이트

insert_back : 맨 뒤에 값 추가

delete_back : 맨 뒤의 값 삭제 

insert_at : 중간 데이터 삽입

delete_at : 중간 데이터 삭제 

 

선언 및 초기화 : O(n) -> n개의 데이터를 선언하기 때문에 

데이터 추가 : O(1) BUT Resizing : O(n)

마지막 데이터 추가: O(1) -> 메모리 크기를 이미 알고 있기 때문에 

마지막 데이터 삭제 :O(1)

중간에 데이터 추가 : O(n)

중간에 데이터 삭제 :O(n)

---

[코테 적용] 반복문

코딩테스트 적용 방법

 

배열의 다양한 활용

1. 반복문

2. Sort & Two Pointer

 

step 1 : 문제 이해하기

Two sum 문제

----------[문제]------------------
정수가 저장된 배열 nums이 주어졌을 때, 
nums의 원소중 두 숫자를 더해서 target이 될 수 있으면 True 불가능하면 False를 반환하세요.
같은 원소를 두 번 사용할 수 없습니다.

input: nums = {4, 1, 9, 7, 5, 3, 16}, target : 14
input: nums = {2, 1, 5, 7},           target : 4

----------[제약조건]----------------
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

step 2 : 접근 방법

직관적으로 생각하기

• 보통 완전탐색으로 시작(일일이 다 더해보기)
• 문제 상황을 단순화 하여 생각하기
• 문제 상황을 극한화 하여 생각하기

자료구조와 알고리즘 활용

• (1) 문제이해에서 파악한 내용을 토대로 어떤 자료구조를 사용하는게 가장 적합한지 결정
• 문제에서 대놓고 특정 자료구조와 알고리즘을 묻는 문제도 많음
• 자료구조에 따라 선택할 수 있는 알고리즘을 문제에 적용

메모리 사용

• 시간복잡도를 줄이기 위해 메모리를 사용하는 방법
• 대표적으로 해시테이블

step 3 : 코드 설계

step 4 : 코드 구현

def TwoSum(nums,target):
    for i in range(len(nums)-1): # 012345
        for j in range(i+1,len(nums)): #123456
            if nums[i] + nums[j] == target:
                return True
    else:
        return False

nums = [4,1,9,7,5,3,16]
target = 14

TwoSum(nums,target)

---

[코테 적용] Two pointer

[1,3,5,2] 와 같은 정렬이 안된 list를 정렬을 할 때 걸리는 시간복잡도는 O(nlogn) 이다.

 

배열의 다양한 활용

1. 반복문

2. Sort & Two Pointer : 말 그대로 두 개의 pointer를 가지고 왔다갔다 함. 보통 Two pointer는 정렬이 된 상황에서 사용함

 

step 3 : 코드 설계

step 4 : 코드 구현

def twoSum(nums, target):
    l = 0
    r = len(nums)-1
    nums.sort()

    while l<r:
        if nums[l] + nums[r] > target:
            r = r-1
        elif nums[l] + nums[r] < target:
            l = l+1
        elif nums[l] + nums[r] == target:
            return True
    return False

print(twoSum(nums=[4,1,9,7,5,3], target=14))

---

연결리스트(Linked list)-1

Linked list는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조입니다.

Node는 데이터 값과 next node 의 주소값을 저장합니다.

Linked List는 메모리상에서는 비연속적으로 저장이 되어 있지만, 각각의 Node가 next node의 메모리 주소값을 가리킴으로써 논리적인 연속성을 갖게 됩니다.

 

 

 

 

---

연결리스트(Linked list)-2