시간 복잡도
점근선을 통해 알고리즘의 효율성을 평가하는 방법 중 하나이다. 알고리즘이란 건 대부분 최적의 상황보다는 평균, 혹은 최악의 상황을 가정하는 것이 맞기 때문에 보통 상한선을 점근선으로 둔 빅-오 표기법(Big-O)을 많이 쓴다.
- 빅-오메가(Big-Ω) : 하한 점근(최적의 상황) - 거의 쓰지 않는다
- 빅-세타(Big-θ) : 빅-오와 빅-오메가의 평균
연결리스트
나는 c언어로 연결리스트를 구현해본 적이 있다. 그때는 구조체에 값, 다음 노드를 가리킬 포인터 변수를 추가해서 노드를 만들었는데 포인터라는 개념을 다루지 않는 파이썬에서 어떻게 연결리스트를 구현할지 궁금했다.
답은 객체였다. 객체로 노드와 연결리스트를 만들어준 뒤 노드의 속성으로 val과 next인자를 만들어주는 것이었다.
class ListNode:
def __init__(self, val, next): # 갖고 있는 값, 가리키고 있는 노드
self.val = val
self.next = next
class LinkedList():
# 초기화
def __init__(self):
self.head = None
# 삽입
def append(self, val):
if not self.head:
self.head = ListNode(val, None)
return
node = self.head # head 에서 노드 시작
while node.next: # 다음 노드가 있을 동안 계속 다음 노드로 넘어감
node = node.next
node.next = ListNode(val, None) # 노드 끝에 새로운 노드 추가
lst = [1]
l1 = LinkedList()
for e in lst:
l1.append(e)
print(l1)
pycharm으로 디버깅을 해보면 next가 각각 뒤에 따라오는 값을 가리키는 것을 볼 수 있다.
연결리스트 응용 - 회문
https://leetcode.com/problems/palindrome-linked-list/submissions/1029384887/
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def __init__(self):
self.head = None
def isPalindrome(self, head: Optional[ListNode]) -> bool:
cnt = 0
li = []
if not self.head:
self.head = head
node = self.head
while node.next:
cnt += 1
node = node.next
if cnt == 0:
return True
elif cnt%2 == 0:
node = self.head
for i in range(cnt//2):
li.append(node.val)
node = node.next
li.reverse()
print(li)
same = 0
node = node.next
for i in range(cnt//2):
if(li[i] == node.val):
print(f"{li[i]} {node.val}")
same += 1
node = node.next
if same == cnt//2:
return True
else:
node = self.head
for i in range(cnt//2 + 1):
li.append(node.val)
node = node.next
li.reverse()
print(li)
same = 0
for i in range(cnt//2 + 1):
if(li[i] == node.val):
print(f"{li[i]} {node.val}")
same += 1
node = node.next
if same == cnt//2 + 1:
return True라고 당장 생각나는 로직으로 코드를 짜긴 했는데, 너무 지저분한 방법이라 조금 더 깔끔한 로직을 생각해보았다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def __init__(self):
self.head = None
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if not self.head:
self.head = head
cnt = 0
node = self.head
while node.next:
cnt += 1
node = node.next
# 회문을 저장해둘 리스트
li = []
if cnt == 0:
return True
# 짝수 회문
node = self.head
if cnt%2==1:
llen = cnt//2+1
#절반 올 때까지 리스트에 저장
for i in range(llen):
li.append(node.val)
node = node.next
for i in range(len(li)-1,-1,-1):
#문자가 하나라도 같지 않으면
if li[i] != node.val:
return False
node = node.next
return True
# 홀수 회문
if cnt%2==0:
llen = cnt//2
#절반 올 때까지 리스트에 저장
for i in range(llen):
li.append(node.val)
node = node.next
# 가운데 노드 건너뛰기
node = node.next
for i in range(len(li)-1,-1,-1):
#문자가 하나라도 같지 않으면
if li[i] != node.val:
return False
node = node.next
return True런타임이 조금 더 빨라졌지만 메모리 면에서 손해를 보았다. 때에 따라 알맞은 알고리즘을 써야지!
- 추가로 풀어볼 문제
https://www.acmicpc.net/problem/17609
스택
넣은 순서의 역순으로 빼내는 자료구조이다. 최근에 넣은 순으로 빼낼 수 있다. 그래서 그런지 빼내는 함수도 delete가 아니라 pop이다.
def test_node():
assert Node(1, None).item == 1
def test_stack():
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
assert stack.pop() == 5
assert stack.pop() == 4
assert stack.pop() == 3
assert stack.pop() == 2
assert stack.pop() == 1
assert stack.pop() is None
assert stack.is_empty()class Node:
def __init__(self, item, next):
self.item = item
self.next = next
class Stack:
def __init__(self):
self.top = None
def push(self, value):
self.top = Node(value, self.top)
def pop(self):
if self.top is None:
return None
node = self.top
self.top = self.top.next
return node.item
def is_empty(self):
return self.top is None이런 자료구조를 늦게 넣은 순대로 밖으로 빼낸다고 해서 Last In First Out(LIFO)라고 부른다.
스택 응용 - 알맞은 괄호
https://leetcode.com/problems/valid-parentheses/
class Node:
def __init__(self, item, next):
self.item = item
self.next = next
class Stack:
def __init__(self):
self.top = None
def push(self, item):
self.top = Node(item, self.top)
def pop(self):
if not self.top:
return None
pop_item = self.top.item
self.top = self.top.next
return pop_item
class Solution:
def isValid(self, s: str) -> bool:
stack = Stack()
for i in s:
if i == '(' or i == '{' or i == '[':
stack.push(i)
if i == ')' or i == '}' or i == ']':
par = stack.pop()
# 꺼낸 괄호가 짝에 맞지 않으면 바로 return false
if(i == ')' and par != '('):
return False
if(i == '}' and par != '{'):
return False
if(i == ']' and par != '['):
return False
# 스택에서 괄호를 모두 꺼냈고 s도 끝까지 갔으면 return true
if stack.top == None:
return True
공부 중