📚 알고리즘
📕 알고리즘 강의 2주차
📌 링크드리스트 (Linked - List)
-
원소의 삽입 삭제를 O(1)의 시간복잡도 안에 할 수 있다.
-
모든 공간이 다 찼어도 맨 뒤에 노드만 동적으로 추가 가능
-
삽입과 삭제가 빈번할 경우에는 링크드리스트를 사용하는 것이 효율적
❗ 특정 원소 조회에는 리스트 , 중간에 삽입삭제에는 링크드리스트 ❗
📌 링크드리스트 구현
-
class Node
-
class LinkedList
: 가장 맨 앞 노드만 들고 있음 , 다음 노드의 접근은 next를 통해 해야함 -
📌 링크드리스트 구현코드 (생성,삽입,삭제,조회)
class Node:
def __init__(self,data):
self.data=data
self.next=None #클래스내부에 저장되는 변수 , 포인터는 아무것도 가리키지 않음
class LinkedList:
def __init__(self,data):
self.head=Node(data) #node를 하나 생성하여 head로 저장
def append(self,data):
#연결리스트에 아무 노드도 없을 때
if self.head is None:
self.head=Node(data)
return
cur=self.head
while cur.next is not None:
cur=cur.next
cur.next=Node(data)
def print_all(self):
cur=self.head
while cur is not None:
print(cur.data)
cur=cur.next
def get_node(self,index):
node=self.head
count=0
while count<index:
node=node.next
count+=1
return node
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
def get_node(self, index):
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
def add_node(self, index, value):
#중간에 원소삽입
new_node = Node(value)
if index==0:
#head 에 넣어야할 상황
new_node.next=self.head
self.head=new_node
node=self.get_node(index-1) #index 번째에 넣기 위해서는 전의 노드인 index-1 노드를 가져와야함
next_node=node.next # 이전 노드의 다음 노드를 변수에 저장
node.next=new_node #이전꺼의 링크를 새노드의 앞링크와 연결
new_node.next= next_node # 새노드를 이전노드의 다음노드와 연결
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
def get_node(self, index):
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
def add_node(self, index, value):
new_node = Node(value)
if index == 0:
new_node.next = self.head
self.head = new_node
return
node = self.get_node(index - 1)
next_node = node.next
node.next = new_node
new_node.next = next_node
def delete_node(self, index):
#처음 노드 삭제
if index==0:
self.head=self.head.next
return # 처리 완료햇으므로 return
node = self.get_node(index-1) # 삭제할 노드으 이전노드 가져옴
node.next=node.next.next
📌 이진탐색
- 정렬되어 있는 리스트에서 사용 가능
- 시간복잡도 O(logN)
📌 오늘의 문제
✔ 백준 4673
- source code
#알고리즘 - 함수
#백준 4673 셀프넘버
not_result={}
for a in range(1,10001):
str_a=list(str(a))
str_a=[int(a) for a in str_a]
sum_a=sum(str_a)
not_result[sum_a+a]=1
for a in range(1,10001):
if a not in not_result:
print(a)
나는 백준을 꾸준히 푼건 아니지만 그래도 못푸던 문제를 풀고 시간이 굉장히 단축되는 내 코드를 보고 그래도 옛날보단 내 코딩실력이 늘었구나 생각했다.
오늘 옛날에 풀었던 문제를 풀어봤는데 시간이 굉장히 단축된 것 같아 뿌듯했다
✔ 백준 18258
- source code
# 큐,덱 알고리즘
# 백준18258
#단어공부
import sys
from collections import deque
input=sys.stdin.readline
N=int(input())
queue=deque()
def command(str):
if str.rsplit(' ')[0]=='push':
queue.append(int(str.split(' ')[1].rstrip()))
elif str.rstrip()=='pop':
if len(queue) == 0:
print(-1)
else:
num=queue.popleft()
print(num)
elif str.rstrip() == 'size':
print(len(queue))
elif str.rstrip() == 'empty':
if len(queue)==0:
print(1)
else:
print(0)
elif str.rstrip() == 'front':
if len(queue)==0:
print(-1)
else:
num=queue.popleft()
print(num)
queue.appendleft(num)
elif str.rstrip() == 'back':
if len(queue)==0:
print(-1)
else:
num = queue.pop()
print(num)
queue.append(num)
for i in range(N):
command(input())
- solution ❓ deque
선입선출 방식으로 작동하는 양방향 큐가 있는데 그것이 바로 데크(deque)다.
즉 , 앞 뒤 방향에서 원소들을 삽입하거나 제거할 수 있다.
컨테이너(container)의 앞 위 원소 에 접근하여 삽입 또는 제거를 할 경우, 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 데크(deque)는 O(1)로 접근 가능하다.
하지만 deque는 list처럼 [i]와 같이 index에 따른 접근이 불가하기 때문에, 중간에 있는 값에 접근하려면 list를 사용하는 것이 훨씬 효율적이다 . Stack으로 쓰이는 경우에는 별 차이 없습니다.
Hongik Univ 💻