알고리즘 기초 1
목차
1. 연결리스트
2.스택
3.큐
4.해시테이블
5.힙(다음 글)
1. 연결리스트(LINKED-LIST): 노드(값과 노드로 이루어진 데이터)와 노드를 연결해서 저장하는 방식. 주소를 통해 다음 값의 주소를 가리킴.
- 어레이: 파이썬의 리스트. 접근 쉬움, 삽입 어려움. (파이썬의 리스트)
- 연결리스트: 직접 구현. 접근 어려움, 삽입 쉬움.
연결리스트 구현
#노드
class ListNode:
def __init__(self, val=0, next=None):
#값
self.val = val
#주소
self.next = next
#연결리스트
class LinkedList:
#head는 제일 처음 넣은 노드를 가리킴
def __init__(self):
self.head = None
#리스트에 노드 추가
def append(self, val):
#리스트에 아무것도 없으면 노드 삽입
if not self.head:
self.head = ListNode(val, None)
return
#리스트에 노드들이 있으면 node라는 변수를 만들어 처음 노드를 node에 저장함
node = self.head
#node 안의 next값이 없을때까지(마지막) 다음 노드로 찾아감
while node.next:
node = node.next
#node에는 마지막 노드가 있기 때문에 이 뒤에 삽입하려는 노드를 붙여 주소를 None이 아닌 삽입하는 주소를 넣음
node.next = ListNode(val, None)
2.스택: LIFO(Last in First Out)자료 구조, 데이터가 순서대로 쌓이면 찾을때는 늦게 쌓인 순서대로 데이터 접근.
스택이 사용되는 예: 컴퓨터의 되돌리기 기능(Ctrl + Z)
스택 구현
#스택에 쌓을 데이터(노드)
class Node:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
class Stack:
#top은 제일 위에 뭐가 있는지 가리키는 변수
def __init__(self):
self.top = None
#스택에 데이터를 넣는 함수
def push(self, val):
#노드를 하나 생성 후
node = Node(val, None)
#노드의 next를 제일 꼭대기였던 노드를 가리킴
node.next = self.top
#self.top을 생성한 노드로 바꾸면 쌓은것처럼 됨
self.top = node
#한줄로는 self.top = Node(val, self.top)
def pop(self):
#스택에 아무것도 없으면
if not self.top:
return None
#빈 노드 만들어서 제일 위에꺼 저장
node = self.top
#스택의 탑을 맨 위의 노드 바로 다음꺼로 바꿈
self.top = node.next
#원래 탑이었던 노드의 값을 반환
return node.val
3.큐: FIFO(First In First Out)자료구조, 데이터가 쌓이고 찾을 때 처음 들어간 데이터부터 나옴.
큐가 사용되는 예: 주문이 들어왔을 때 먼저 들어온 순서대로 처리해야 할 때
큐 구현
class Node:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
class Queue:
#front는 항상 앞에있는 노드를 뜻함(스택의 top과 정반대)
def __init__(self):
self.front = None
#스택에 노드를 추가하는 함수
def push(self, val):
#스택에 아무것도 없으면 그대로 넣기
if not self.front:
self.front = Node(val)
return
#스택에 뭔가 있다면 node라는 빈 변수에 제일 앞에걸 넣고 node에 마지막 노드를 넣을때까지 다음거를 넣음
node = self.front
while node.next:
node = node.next
#마지막에 도달하면 넣기
node.next = Node(val)
def pop(self):
#비어있으면 꺼낼게 없음
if not self.front:
return None
#빈노드 node에 처음꺼를 넣고 그 다음꺼를 front에 넣은 후 node값 출력
node = self.front
self.front = node.next
return node.val
def is_empty(self):
return self.front is None
4. 해시테이블: 해시함수를 이용해 키를 값에 매핑하는 자료구조
- 해시 함수: 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수, 임의의 값을 넣어도 예상 크기 내에서 결과가 나오는 함수(딕셔너리와 유사)
해시함수 예: 나머지를 반환하는 함수
def modThree(n):
return n % 3
print(modThree(0)) # 0
print(modThree(1)) # 1
print(modThree(2)) # 2
print(modThree(0)) # 0위의 함수에서 n이 1일 때나 4일 때, 둘의 반환 값은 똑같이 1이고, 만약 이 반환 값을 키로 쓴다면 1일때나 4일때 구분을 못한다. 이것을 충돌이라고 한다.
이를 위해 체이닝(Chaining) 혹은 오픈 어드레싱(Open Addressing)을 이용해 충돌을 없앤다.
-체이닝(Chaining): 충돌 발생 시 ‘연결’해가는 것. 연결리스트를 사용
- 오픈 어드레싱(Open Addressing): 충돌 발생 시
- 오픈 어드레싱은 값이 뭉치는 클러스터링이 발생할 수 있고, 체이닝은 메모리 오버헤드가 길어질 경우 탐색이 느려진다는 단점이 있음.
- 각 언어 별로 해시테이블의 구현 방식: C++, Java, Go: 체이닝 / Python, Ruby: 오픈 어드레싱
해시테이블 구현(modular(10))
"""체이닝 방식의 해시테이블"""
class HashNode:
#딕셔너리처럼 key와 value가 있고, 다음노드를 담을수 있는 next가 있음
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.next = None
#modular연산(나머지 연산) 10으로 나눈 나머지만 해싱함.
class HashTable:
def __init__(self):
#10으로 나눈 나머지만 저장하기 때문에 크기는 10이면 됨
self.size = 10
#해시테이블에 10개만큼 빈 공간을 만듬
self.table = [None] * self.size
#key값을 받으면 10으로 나누어 나머지 반환하는 함수
def _hash_function(self, key):
return key % self.size
#해시테이블에 해시노드 추가하는 함수
def put(self, key, value):
#idx는 해시테이블에 인덱스를 담음
idx = self._hash_function(key)
#만약 해시테이블 안에서 idx번째의 공간에 아직 데이터가 없다면 그자리에 넣고 아니면 연결리스트처럼 진행함
#연결리스트는 위에 참고
if self.table[idx] is None:
self.table[idx] = HashNode(key, value)
else:
node = self.table[idx]
while node.next:
node = node.next
node.next = HashNode(key,value)
#key로 값 찾기
def get(self, key):
#해시테이블의 몇번째가 idx에 담김
idx = self._hash_function(key)
#node라는 빈 변수에 idx번째의 맨처음 값을 넣음
node = self.table[idx]
#노드의 값이 None일 때까지
while node is not None:
#node의 키랑 찾으려는 key랑 같다면 그 노드의 value를 반환
#첫번째값이 key값이랑 같을수 있기 때문에 아래 if문이 node = node.next문보다 위에 있어야함.
if node.key == key:
return node.value
node = node.next
#다 뒤져봤는데도 없다면 -1 반환
return -1
#해시테이블에서 key값을 찾아 그 노드를 제거하는 함수
#제거하는 방법은 제거하려는 노드의 앞뒤로 연결해 고립시키면 제거된것처럼 됨
def remove(self,key):
#해시테이블의 몇번째가 idx에 담김
idx = self._hash_function(key)
#node라는 빈 변수에 idx번째의 맨처음 값을 넣음(제거하려는 노드가 될 변수)
node = self.table[idx]
#제거하려는 노드 앞의 노드
prev_node = None
while node:
if node.key == key:
#이전 노드가 존재하면
if prev_node:
prev_node.next = node.next
#이전 노드가 존재하지 않는다면(제거하려는 노드가 처음에 넣은 노드라면)
else:
self.table[idx] = node.next
return
prev_node = node
node = node.next
----------------------------------------------------------
나만의 필수암기노트
파이썬 deque: Queue랑 Stack이 둘다 되게끔 지원해주는 라이브러리. deque([리스트])로 구현함.
deque 사용 예제
def test_problem_queue(num):
#deque(리스트)형식으로 만듦
deq = deque([i for i in range(1, num + 1)])
while len(deq) > 1:
deq.popleft()
deq.append(deq.popleft())
return deq.popleft()'알고리즘' 카테고리의 다른 글
| 알고리즘 2 (BFS, 백 트래킹, 이진탐색) (1) | 2024.06.17 |
|---|---|
| 알고리즘 1 (그래프, DFS) (0) | 2024.06.14 |
| DFS 문제(섬의 개수 구하기) (2) | 2024.06.14 |
| 자료구조 종류2 (트리, 힙) (4) | 2024.06.13 |
| O(n)에서 O(n^2)인 약수의 개수 구하기 예 (0) | 2024.06.12 |