Data Structure

✅ Array(list)

여러 원소를 하나의 묶음으로 관리하고 각 원소 간에 순서가 존재해 인덱스를 통해 접근하는 리스트
파이썬에 내장된 리스트 관련 함수들을 구현해보면 다음과 같다.

li_x = ['Hong', 'kil', 'dong']
li_y = ['Kim', 'tae', jun']
# 리스트에 원소 1개 추가
li_x.append(li_x) > ['Hong', 'kil', 'dong',['Kim', 'tae', jun']]
# 리스트 끝에 가장 바깥쪽 iterable 모든 항목 넣기
li_x.extend(li_y) > ['Hong', 'kil', 'dong','Kim', 'tae', jun']
# 슬라이싱으로 위치 확인
li_x[:1] > ['Hong', 'kil']
즉, [원하는 위치:원하는 끝+1]을 의미
# 인덱스 확인
li_x.index('kil') > 1
# 리스트 정렬 (default: 오름차순, 역순 시 reverse=True) 추가 (리턴 값 X)
li_x.sort() > ['Hong', 'dong', 'kil']
# 변수 지정해 sorting 방법?
li_x = sorted(li_x) 
# 특정 위치에 원소 넣기
li_x.insert(위치, 원소) > ex) li_x.insert(1, 'Tae') > ['Hong', 'Tae', 'kil', 'dong']
# 특정 원소 삭제
li_x.remove('Tae') 
# 위치 기준 삭제
li_x.pop(1) > ['Hong', 'dong']
li_x.pop() > # 맨 끝값 뽑기

✅ Linked-List

기존 array는 인덱스를 통해 빠른 접근이 가능하지만, 크기를 지정해야 해 데이터 추가, 삭제가 힘들기에 이러한 단점을 개선하기 위해 생긴 자료구조. 파이썬은 기본적으로 지원하는 자료구조!

• 다른 추상 자료형을 구현할 때 기반이 되는 기초 선형 자료구조
• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장

📌 배열 vs 연결리스트

• 배열은 물리적인 메모리 주소가 연속적, 연결리스트는 물리 메모리 주소가 비연속적, 랜덤
• 배열은 삽입/삭제에 O(n), 동적으로 연결된 연결리스트는 O(1)
• 배열은 익덱스 접근 시 O(1), 연결리스트는 메모리 저장이 아니기에 모든 노드 거쳐 탐색 필요하므로 O(n)이 소요
  노드 구현은 다음과 같다

### 연결리스트 구현
class ListNode:
    def __init__(self, val = 0, next = None):
        self.val = val
        self.next = next
head = ListNode(0)
# 노드 추가
curr_node = head

new_node = ListNode(1)
curr_node.next = new_node
curr_node = curr_node.next

curr_node.next = ListNode(2)
curr_node = curr_node.next

curr_node.next = ListNode(3)
curr_node = curr_node.next

curr_node.next = ListNode(4)
curr_node = curr_node.next

# 전체 연결리스트 탐색
node = head
while node:
    print(node.val)
    node = node.next

# 탐색하며 삭제
node = head
while node.next:
    if node.next.val == 3:
        next_node = node.next.next
        node.next = next_node
        break
    node = node.next
node = head
while node:
    print(node.val)
    node = node.next

✅ stack & queue

📌 스택

• LIFO 구조로 한쪽 끝에서만 데이터를 넣거나 빼기 가능 (append(입력), pop(꺼내기))
• 제한적으로 접근가능한 자료구조로 의존관계가 있는 상태를 처리함
• 재귀함수에 주로 사용 (임시 데이터를 스택에 넣고 재귀함수를 빠져나와 퇴각 검색을 할 경우 스택에 넣어둔 임시 데이터를 뺀다)
• 콜스택(프로그램에서 현재 실행중인 함수(서브루틴)을 저장하는 역할
• 문자열 역순 출력 및 연산자 후위표기법에 사용

📌 큐

• FIFO 구조로 입/출구가 각 반대 쪽 끝에 존재하는 자료구조
• 스케줄링 (OS가 프로세스를 관리하는 기법, 작업을 병렬적으로 진행할 때, 작업 간 의존관계 없다면 큐에 저장하여 관리)
• 버퍼, BFS 탐색 등에 사용 됌

✍️ 지원 연산

• push : 큐에 값을 넣음
• pop : 큐에 존재하는 데이터 빼기
• front : 큐의 가장 앞에 자료 반환 (dequeue 할 위치 기억)
• rear : enqueue 할 위치 기억
• back : 큐의 가장 뒤에 자료 반환
• empty : 큐가 비어있는지 여부 반환

✅ Heap

: 우선 순위의 개념을 큐에 도입하여 우선 순위 높은 데이터 먼저 나가는 자료구조 (우선순위 큐)

• 배열, 연결리스트, 힙으로 구현 삽입/삭제 시 O(n) 소요
• 완전 이진 트리의 일종

heapq (오름차순 정렬된 트리 형태 구조) - 최소힙, 최대힙 존재
heapify(list) : 리스트 > 힙 자료구조 변환 가능
heappop(heap) : 힙 내 최솟값 리턴
heappush(heap, number) : 힙에 숫자 추가

• 최소힙의 경우 루트노드가 최솟값으로 시작
• 최대힙의 경우 루트노드가 최댓값으로 시작
  그러나 최대힙의 경우 부호 변경이 필수!!
• < 부호 변경 하는 방법 >
  heapq.heappush(heap, -number)
  -heapq.heappop(heap)
  위와 같은 방법을 통해 부호 변환하여 큰 숫자부터 출력 가능!

✅ Hash

데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것. (보안에 가장 자주 사용됨)

• 기본적으로 딕셔너리와 같은 형태
• 해시 함수를 구현해 데이터 값을 해시 값으로 매핑한다.
• 데이터가 많아지면 collision 현상 발생. (해시 값 끼리 충돌하는 경우)
• 시간 복잡도는 O(1)
• 충돌을 회피하기 위해서, 동일 키 값에 대해 링크드리스트로 연결되어 있어 노드가 추가된다.

❗ 충돌 문제 해결

1. 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식, 메모리 문제 발생할 수 있음.
2. Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터 저장 허용 (해당 키 값에 저장되어 있다면 다른 주소에 저장하는 방식)
3. 선형 탐사 : 정해진 고정 폭으로 옮겨 해시 값 중복 회피
4. 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시 값 중복 회피