[알고리즘] 1. 자료구조

1. 배열 Array

1. 삽입/삭제: O(N)
2. 탐색: O(1)
   → 삽입/삭제: 삽입이나 삭제시 나머지 배열 요소의 위치를 바꾸어주어야 한다.
   → 탐색: 임의 접근방식으로 한번에 원하는 위치에 접근할 수 있다.
   ※ 시간 복잡도는 최악의 경우를 기준으로 계산한다.
   ※ 임의 접근 방식은 배열의 시작 주소에서 원하는 위치까지 자료형의 크기를 더하는 방식이다.

   ### 예시
   arr = [1, 2, 3, 4, 5]
   arr[1] = 2

2. 벡터 Vector

1. 삽입/삭제: O(N)
2. 탐색: O(1)
   ※ C++기준 사이즈를 조절할 수 있는 동적배열로 파이썬의 리스트와 동일하다.
   ※ 파이썬 기준 튜플+리스트를 사용하여 두 개의 쌍을 이루는 데이터를 다룰 때 사용

    ### 예시
    v = []
    v.append((1, 2))
    v.append((3, 4))
    print('size:', len(v))
    for p in v:
   		print(p) # 2, 2

3. 연결 리스트 Linked List

1. 삽입/삭제: O(1)
2. 탐색: O(N)
   → 삽입/삭제: 모든 노드에 접근하여 위치를 변경할 필요없이 이전, 이후 노드의 주소값만 수정하면 된다.
   → 탐색: 임의 접근이 불가능하여 처음부터 접근하여 다음주소로 차근차근 이동해야한다.
   → 배열처럼 연속적으로 저장되어 있지않고, 메모리상에 랜덤으로 노드가 저장되어 있다. (임의 접근불가)
   → 각 노드별로 다음 노드의 메모리 주소를 알고 있다.
   ※ 다른 자료구조들을 구현할 때 많이 쓰인다.

4. 스택 Stack

1. 삽입/삭제: O(1)
   → 삽입/삭제: 삽입, 삭제시 최상단에서 한번만 작업이 일어난다.
   → FILO: First In Last Out, LIFO: Last In First Out
   → 가장 마지막에 들어온 데이터는 스택의 "HEAD"이다.
   ※ 페이지 뒤로가기 기능과 같은 곳에서 해당 알고리즘이 사용됨.

	### 예시
	s = []
    s.append(1)
    s.append(2)
    s.append(3)
    print('size:', len(s))
    while len(s) > 0:
    	print(s[-1])
        s.pop(-1) # s.pop()도 가능, 리스트상 맨 뒤의 값을 제거
        		  # 3, 2, 1

5. 큐 Queue

1. 삽입/삭제: O(1)
   → 삽입/삭제: 삽입은 뒤, 삭제는 앞에서 한번만 작업이 일어난다.
   → 단, 리스트를 이용하여 구현할 경우 n개의 데이터에 접근하여 위치를 재조정해줘야하므로 O(N)이 된다.
   → FIFO: First In Last Out, LILO: Last In First Out

	### 예시
    ### deque: Double-ended Queue, 앞뒤로 데이터를 모두 빼고 넣고 할 수 있다.
	from collections import deque
    
    q = deque()
    q.append(1) # q.appendleft(1): 앞에 넣을 수 있다.
    q.append(2)
    q.append(3)
    print('size:', len(q))
    while len(q) > 0:
    	print(q.popleft()) # q.pop(): 뒤의 데이터가 빠질 수 있다.

※ Queue 모듈 사용가능하나 멀티스레드 환경에서 안정성을 위한 기능도 있어 deque보다 느리다.

	### 예시
	from queue import Queue
    
    q = Queue()
    q.put(1)
    q.put(2)
    q.put(3)
    while q:
    	print(q.get())

6. 우선순위 큐 Priority Queue (Heap)

1. 삽입/삭제: O(logN)
   → 이진트리 형태의 자료구조는 O(logN)이다.
   → root node가 자식노드보다 크면 max-heap(C++), 작으면 min-heap(python)
   → 삭제를 할 경우 root node가 나온다.

	### 예시
    import heapq as hq
    pq = []
    hq.heappush(pq, 4)
    hq.heappush(pq, -3)
    hq.heappush(pq, 8)
    hq.heappush(pq, 0)
    hq.heappush(pq, 11)
    hq.heappush(pq, -7)
	while len(pq) > 0:
    	print(pq[0]) # root node 값을 볼 수 있다.
    	hq.heappop(pq)

※ PriorityQueue 모듈 사용가능하나 멀티스레드 환경에서 안정성을 위한 기능도 있어 heapq보다 느리다.

	### 예시
	from queue import PriorityQueue
    
    pq = PriorityQueue()
    pq.put(-6)
    pq.put(7)
    pq.put(1)
    pq.put(4)
    pq.put(-2)
    pq.put(3)
    while not pq.empty():
    	print(pq.get()) # pop과 같은 역할을 한다. (빠진값이 먼지 반환까지 한다.)

7. 맵 Map (Dictionary)

1. 삽입/삭제: (C++, O(logN)), (python, O(1))
2. key, value
   → C++: red-black tree 형태, python: hash 형태로 구현되어 있다.

	### 예시    
    m = {}
    m['apple'] = 50
    m['banana'] = 120
    m['orange'] = 30
	print('size:', len(m))
    for k in m:
    	print(k, m[k])

8. 집합 set

1. 삽입/삭제: (C++, O(logN)), (python, O(1))
2. 중복 X

	### 예시    
    s = set()
    s.add(1)
    s.add(2)
    s.add(3)
    s.add(4)
    s.add(5)
    s.add(1)
	print('size:', len(s)) # 5
    for i in s:
		print(i)
	s.pop() # pop을 이용하여 삭제시 빠진 값은 랜덤이다.
    s.remove(1) # 특정 값을 뺄때는 remove를 사용한다.