[강의 정리/Python] List

 

 

 

Static Array(정적 배열)

 

배열의 특성

1. 고정된 저장 공간(fixed size) -> 고정된 사이즈를 갖기 때문에 Static Array라고 함.

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

3. 시간복잡도

 

• 배열변수는 자신이 할당받은 메모리의 첫번째 주소 값을 가리킴.
• 배열은 연속/순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index로든 direct하게 접근이 가능함. (direct access = random access)
• int arr[5] = {2, 5, 3, 1, 3} 배열을 선언했을 경우, n번째 데이터는 0x6AF923 + 4*(n-1)에 저장되있을 것임.  ex) int는 4byte
• 시간복잡도 :  O(1)의 시간복잡도를 가짐. (한번의 연산으로 원하는 데이터에 바로 접근 가능)

 

 

Dynamic Array(동적 배열)

 

• 선언 시에 정한 size보다 더 많은 데이터를 저장해야 하는 경우, 공간이 남아있지 않아 문제가 발생할 가능성이 있음. 이런 문제점을 해결할 수 있는 것이 Dynamic Array
• 배열의 크기를 변경할 수 있는 배열. (Static Array의 한계를 보완하기 위해 고안됨)
• 선언 시에 배열의 크기를 정하지 않아도 됨
• python에서 list 자료형을 통해 dynamic array 선언 가능
• Resizing(삽입, 삭제) 시 O(n)의 시간복잡도를 가짐
• 정렬이 안된 list를 정렬을 할 때 걸리는 시간 복잡도는 O(nLogn)이다. 

 

배열 안의 두 원소를 합한 값이 target과 같은지 체크하는 코드

# Sort와 TwoPointer를 사용한 예제
# 양 쪽 끝 포인터를 잡고 둘의 원소를 더한 값이 target보다 크면 r에서 한칸 뒤로 이동, target보다 작으면 l에서 한칸 앞으로 이동하면서 target과 같은 값을 찾는 과정
# l == r이 되는 순간

def twoSum(nums, target):
    # 정렬 시 O(nLogn)의 시간 복잡도가 걸림
    nums.sort() # 비교하기 전 먼저 오름차순 정렬

    l, r = 0, len(nums)-1 # 해당 인덱스에서 시작하게끔 선언 (배열 제일 왼쪽과 오른쪽을 가리킴)
    # O(n)
    while l<r: # l<r 인 동안에는 계속 반복문이 돌아야함.
        if nums[l] + nums[r] > target:
            r -= 1
        elif nums[l] + nums[r] < target:
            l += 1
        elif nums[l] + nums[r] == target:
            return True
    return False # l과 r이 같은 곳을 가리키는 경우, 둘의 원소를 합쳐서 target이 되는 경우가 없음.


# print(twoSum(nums=[2,1,5,7], target=4)) # False
print(twoSum(nums=[4,1,9,7,5], target=14)) # True

 

 

 

 

Linked List

• node라는 구조체가 연결되는 방식으로 데이터를 저장
• node는 데이터값과 next node의 주소를 저장
• Linked List는 메모리상에서는 비연속적으로 저장이 되어있지만, 각각의 node가 next node의 메모리 주소값을 가리킴으로써 논리적인 연속성을 가짐 (물리적 비연속적, 논리적으로는 연속적)
• 각 node들은 데이터 정보(value) 뿐만 아니라 next node의 address 정보도 가지고 있기 때문에 논리적으로 연속성을 유지하며 연결할 수 있음.
• Linked List의 첫번째 노드는 Head가 가리키고 있어야함 (head가 None일 때에만 새로운 new node가 들어오면 head가 new node를 가리키게 해야함)

 

 

Design Browser History 예제

https://leetcode.com/problems/design-browser-history/

 

인터넷 브라우저에서 방문기록과 동일한 작동을 하는 BrowserHistory Class를 구현할 것이다. 구현할 브라우저는 homepage에서 시작하고, 이후에는 다른 url에 방문할 수 있다. 추가로 "뒤로가기"와 "앞으로가기"가 작동하도록 구현하라.

 

• BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
• void visit(string url) Visits url from the current page. It clears up all the forward history.
• string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps. ("뒤로가기"를 할 수 있는 page 개수가 x이고 step > x 라면 x번 만큼만 "뒤로가기"를 한다. "뒤로가기"가 완료되면 현재 url을 리턴한다.)
• string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps. ("앞으로가기"를 할 수 있는 page 개수가 x이고 step > x 라면 x번 만큼만 "앞으로가기"를 한다. "앞으로가기"가 완료되면 현재 url을 리턴한다)

 

 

제약조건

• 1 <= homepage.length <= 20
• 1 <= url.length <= 20
• 1 <= step <= 100
• homepage와 url은 '.'를 포함한 lower case 영어문자로 되어있다.
• visit, back, forward는 최대 5000번의 호출이 있을 수 있다.

 

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]

Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

 

강의자님의 코드이나 다른 분들의 예시도 직접 확인해보는 것이 이해에 더 도움이 될 것 같다.

 

class ListNode(object):
    
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

class BrowserHistory(object):

# 초기화할때 homepage를 입력받으면 node를 생성하고 head,current,tail 등이 있다면 type:homepage를 가리키도록 하는 코드 작성해야함
    def __init__(self, homepage): 

        # head가 없어도 되지만 형식상 써줌
        self.head = self.current = ListNode(val=homepage)

    def visit(self, url):
        self.current.next = ListNode(val=url, prev=self.current)
        self.current = self.current.next
        return None

    def back(self, steps):
        while steps > 0 and self.current.prev != None:
            steps -= 1
            self.current = self.current.prev
        return self.current.val

    def forward(self, steps):
        while steps > 0 and self.current.next != None:
            steps -= 1
            self.current = self.current.next
        return self.current.val

 

 

 

 

 

back과 forward 함수는 while이 아닌 for 문으로 구현 가능합니다. (Doubling Linked List)

class ListNode(object):
    
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

# Linked List
class BrowserHistory(object):

    def __init__(self, homepage): 
        new_node = ListNode(homepage) # 새 노드 생성 헤드와 current에 저장
        self.head = self.current = new_node

    def visit(self, url): 
        new_node = ListNode(val=url, prev=self.current) # prev 파라미터에 현재의 current를 저장
        self.current.next = new_node # current의 next에 새 url을 가진 node를 추가(해당 노드의 next는 None이므로 forward 초기화)
        self.current = self.current.next # 현재 Linked List에 next node 연결

    def back(self, steps):
        for _ in range(steps):
            if (self.current.prev):
                self.current = self.current.prev
            else:
                break
        return self.current.val
    
    def forward(self, steps):
        for _ in range(steps):
            if (self.current.next):
                self.current = self.current.next
            else:
                break
        return self.current.val

ll = BrowserHistory("leetcode.com")
ll.visit("google.com")
ll.visit("facebook.com")
ll.visit("youtube.com")
ll.back(1)
ll.back(1)
ll.forward(1)
ll.visit("linkedin.com")
ll.forward(2)
ll.back(2)
ll.back(7)