개발자로 더욱 성장하기위해 이전년도에 포기했던 알고리즘을 다시 잡고 공부하는 한주였다.
작년에 어려웠던것 개념 중 하나가 링크드 리스트와 어레이의 차이였는데 이번 WIL에선 이들과 이번 알고리즘 공부를 시작하며 새로 알게된 동적계획법을 짧게 리뷰하고 넘어가고자한다.
1. 클래스
- 클래스란 분류, 집합과 같이 같은 속성과 기능을 가진 객체를 총칭한다.
예를 들자면 원숭이,물고기,다람쥐가 동물인 것처럼.
# 클래스
# 파이썬 생성자에 대해 자세히 알아보자
class Person(): #파이썬 클래스는 자기자신을 원래 알아서 넘겨준다
def __init__(self,param_name):
print(self)
# 자기자신안에 변수를 만들어서 저장해두겠다
self.name = param_name
def talk(self): # 클래스 내부함수는 메소드
print("제 이름은",self.name)
person_1 = Person("긍긍")
print(person_1.name)
person_1.talk()여기서 생성자를 생성하면 변수를 집어넣을때 그안의 주소를 리턴해준다. 이를 가지고 어레이와 링크드리스트를 구현할 수 있다. 학부에서 배웠던 자료구조에서 헷갈렸던 점은 그래서 파이썬에서 사용하는 건 리스트인데 이건 링크드리스트와는 다른개념인지 리스트를 출력하면 배열(Array)라고도 나오는데 이는 왜그런건지 몰랐는데,
파이썬에서 list는 array로 구현이 되어있던 것이다.(아이러니하게도) 그러나 새로운 배열생성에 동적배열이라는걸 사용해서 길이가 늘어나도 O(1)의 시간복잡도가 걸리게 설계했다.
즉, 파이썬의 배열은 링크드리스트로 쓸수도있고 배열로도 쓸수있게만든 효율적인 자료구조인셈!
2. Array & Linked List
- 모든 컴퓨터에서 변수를 옮길때 변수는 한번에 하나씩 옮길 수 있다.
Array
- 배열은 각 원소에 즉시 접근이 가능하다 ( O(1)내에 접근 가능하다)
- 배열을 바꾸는 경우: 최악의 경우일시 O(N)의 시간복잡도가 걸린다
- 한번 정해진 배열은 늘리는 것이 불가능하기에 새로운 공간을 할당하고 안에있는 변수들을 전부 옮겨야하기에 데이터를 삽입/삭제하기에 비효율적인 자료구조이다.
- Array는 파이썬으로 구현할 필요가 없기에 예시코드는 생략한다.
Linked List
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]링크드리스트는 이런식으로 이어져있다. 노드+포인터+노드+포인터의 구조인셈
- 리스트는 크기가 정해지지 않는 데이터의 공간, 얼마든 늘어날수있다
- 특정원소에 접근하려면 탐색을 해야하기에 O(N)이 걸린다
- 리스트는 포인터만 변경해주면 원소 삽입/삭제가 O(1)시간내에 가능하다
- LinkedList의 구현 파이썬 코드이다. 설명은 주석을 달아놨다.
class Node:
def __init__(self,data):
self.data = data
self.next = None
# 노드를 연결
node1 = Node(5)
node2 = Node(11)
# 포인터를 지목
node1.next = node2
class Linkedlist:
def __init__(self,data):
# Node라는 다른클래스를 들고와서 적용하기
self.head = Node(data)
def append(self,data):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(data)
print(cur.data)
def print_all(self):
cur = self.head # 헤드노드부터 선언시작
while cur is not None:
print(cur.data) # cur이면 생성자 주소가 찍히고 cur.data여야 주소안의 데이터가 찍힘
cur = cur.next
# head node만 가지고있음
# 다음노드를 보려면 각 노드의 next를 조회해서 찾아갸아햄
linked_list = Linkedlist(3)
# linked_list.append(4)
# linked_list.append(5)
linked_list.print_all() # 3 4 3 4 5
############ 원소찾기 추가버전
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
# 여기다가 node.data를 취해서 바로 데이터값을 주려했는데
# 그럴시에 get_node함수를 다른곳에서 쓰면 위치를 못가져옴
# 이또한 위치를 기준으로 모든 연산자를 생각함
# 5 > 12 > 8 사이에 6을 삽입한다고 가정한다면
def add_node(self, index, value): # 몇번값에 뭐를 추가할건지
new_node = Node(value) #[6]
if index ==0 :
new_node.next = self.head #이렇게 미리 정해놔야됨.
# [6] > [5]
self.head = new_node # 이것만 넣었다면 이전에 받은 노드들이 전부 사라져버림
# 지정하고나서야 head > [6] > [5] > ..
return
### 주의할점은 이런식으로 인덱시-1처리를 할때는 꼭 0이란 예외상황을 고려해야함
node = self.get_node(index - 1) #[5]
#클래스내에있는 다른함수를 호출
next_node = node.next #[12]
node.next = new_node #[5] > [6]
new_node.next = next_node #[6] > [12]
def delete_node(self, index):
if index ==0: # 헤드노드를 바꾸고싶다면 이렇게
self.head = self.head.next
node = self.get_node(index-1)
node.next = node.next.next # node의 다음을 그냥 그 다음이라고 알려주기만하면끝
return "index 번째 Node를 제거해주세요!"
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(2)
linked_list.append(3)
# print(linked_list.get_node(1)) # -> 5를 들고 있는 노드를 반환해야 합니다!
linked_list.add_node(1,6)
linked_list.print_all() # 5 6 12 2 3
즉, 데이터 조회가 많으면 Array 삽입삭제가 많으면 LinkedList를 사용해야한다는 결론이 나온다.
3. 동적계획법
실제 코딩테스트에선 재귀함수를 이용해 문제를 풀어나가야하는 경우가 많다. 그러나 재귀함수는 자기자신을 반복하기때문에 이미 결과값을 아는 연산을 또하고 또하는.. 말그대로 재귀적인 문제가 생긴다. 그래서 나타난 것이 동적계획법이다. 재귀함수를 차용하되 반복되는 하위연산들의 값을 메모이제이션에 기록해 쓸데없는 연산횟수를 줄여 시간복잡도를 줄이는 것.
피보나치 수열을 예로 들겠다.
input = 20
def fibo_recursion(n):
if n==1 or n==2:
return 1
return fibo_recursion(n-1) + fibo_recursion(n-2)
print(fibo_recursion(input)) # 6765
# 재귀함수는 연산이 오~래 걸림
# 이미 결과는 아는 작업을 너무 오래함이건 우리가 흔히 볼 수 있는 피보나치 수열이다. 그러나 이대로 백준알고리즘에 제출한다면 시간초과로 몇번을 제출해도 틀렸다고 나올 것이다.
## 동적 계획법
# 하위문제를 풀고 결과를 기록하고 이용함
# 메모이제이션 = 결과를 기록
# 겹치는 부분 문제
# 이 방식은 top > down방식
input = 50
# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
1: 1,
2: 1
}
def fibo_dynamic_programming(n, fibo_memo):
if n in fibo_memo:
return fibo_memo[n]
nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
fibo_memo[n] = nth_fibo
return nth_fibo
print(fibo_dynamic_programming(input, memo))그러나 위에 input값 이후 memo값에 딕셔너리 형태로 키값과 벨류값을 저장한 것을 볼 수 있다. 이리하여 함수를 부를때도 만약 memo 딕셔너리안에 값이 있으면 굳이 연산을 반복하지 않고 다음계산으로 넘어가라고 명령이 가능하다.
그리고 마주한 또다른 백준 알고리즘문제가
9184번: 신나는 함수 실행
입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.
www.acmicpc.net
이것인데
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)간단하게 말하자면 값 a,b,c를 받아서 위와 같은 규칙으로 여러번 재귀하라는 문제이다.
그래서
# 세개 값 받아주고
# 풀이보면 3차원으로 받아줬던데 그냥 딕셔너리안에 함수값넣는걸로 메모이제이션 활용
a,b,c= map(int,input().split())
memo = {
w(1,1,1):2,
w(20,20,20):1048576
}
def w(a,b,c):
if a<=0 or b<=0 or c<=0:
return 1
elif a>20 or b>20 or c>20:
return memo[w(20,20,20)]
if memo[w(a,b,c)]:
return memo[w(a,b,c)]
if a<b<c:
memo[w(a,b,c)]= w(a,b,c-1) + w(a, b-1, c-1) - w(a, b-1, c)
return memo[w(a,b,c)]
memo[w(a,b,c)] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
return memo[w(a,b,c)]
print(w(a,b,c))동적계획법을 배운 나는 메모이제이션을 활용하려고했다. 딕셔너리안에 함수값이 저장이된다는 것을 알았기에 이를 활용해 메모안에 이미 계산된 값을 넣고 불러오려고 했으나 재귀를 너무 많이해서 결과를 낼 수 없다는 에러가 났다.
그래서 다른 사람의 코드를 참고했더니 대부분
MAX = 21
dp = [[[0]*MAX for _ in range(MAX)] for __ in range(MAX)]
이런식으로 다차원배열을 만들고 a,b,c각각 20까지의 값만 저장하면되니 MAX를 21로 선언해준 듯 한데, 여전히 내가 하려던 딕셔너리 다변수함수저장방식이 왜 안되는지는 의문으로 남아있다.(추후 해결할 예정)
아무튼 이번주도 알고리즘을 푸느라 굉장히 정신없이 지나갔다. 그러나 저번주에 비해 낮잠을 자기도하고 스스로에게 조금 느긋하게 굴은 감이 있어서.. 이전처럼 돌아가는게 아닐까 걱정이 되기도 한다. 아!!!! 인터렉티브웹스터디도하고 모쪼록 다시 WIL를 작성하기시작했던 주로 돌아가보려고한다 아자!
댓글