우선 지난 시간 코드 리뷰
실습 1번
def solution(L, x):
if(L[-1] < x):
L.append(x)
return L
for idx, i in enumerate(L):
if(x < i):
L.insert(idx, x)
return L
하나의 for문에 조건을 한번만 걸어줘서 수정할 수 있도록. 인덱스로 접근해보자
def solution(L, x):
position = len(L)
for idx, num in enumerate(L):
if(x < num):
position = idx
break
L.insert(position, x)
return L
print(solution([20, 37, 58, 72, 91], 92))
실습 2번
ef solution(a):
A = 0
B = 1
for i in range(a):
if(i % 2 == 0):
A = A+B
else:
B = A+B
if A > B:
return B
else:
return A
return a
print(solution(6))
이걸 이렇게 바꿀 수 있다.
def solution(a):
if a <= 1:
return a
else:
i = 2
A = 0
B = 1
while(i <= a):
A, B = B, A+B
i += 1
return B
print(solution(5))
자료구조 & 알고리즘
목차
- 5강 재귀 알고리즘 응용
- 6강 알고리즘의 복잡도
- 7강 연결 리스트(1)
- 8강 연결 리스트(2)
- 9강 연결리스트 (3)
재귀 알고리즘 응용
문제 : n개의 서로 다른 원소에서 m개를 택하는 경우
-> 특정한 하나의 원소 입장에서 볼 때, 이 원소를 포함하는 경우와 그렇지 않은 경우를 따로 계산해서 더한다.
def combi(n,m):
return combi(n-1,m) + combi(n-1,m-1)
=> Trivial case를 고려하지 않은 실수!
따라서
def combi(n,m):
if n == m:
return 1
elif m == 0:
return 1
else:
return combi(n-1,m) + combi(n-1,m-1)
-> 효율성 측면에서 나빠. 왜? -> 유용성 : 사람이 생각하는 방식을 코드로 직접 옮길 수 있기 때문이다. ex) 하노이의 탑 문제 -> 반복문으로 구현하기 쉽지 않아. 또한 트리의 경우 재귀적으로 해결되는 경우가 많기에 재귀함수 유용하다.
연습문제
- 재귀적 이진탐색 `def binserach(L,x,lower,upper):
def solution(L, x, l, u):
if l > u:
return -1
mid = (l + u) // 2
if x == L[mid]:
return mid
elif x < L[mid]:
return solution(L, x, l, mid-1)
else:
return solution(L, x, mid+1, u)
- l>u의 조건을 알기까지 오래 걸렸다. l>=u를 생각했었는데, 질문하기에 올라온 다른 분들의 을 보면서
- 예외 조건 solution([1,2,3,],3 ,0,2)를 알 수 있었고, 직접 써가면서 공부하니 이해 되었다.
6강 알고리즘의 복잡도
- 시간 복잡도 : 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계
-
공간 복잡도 : 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계
- 평균 시간 복잡도 : 임의의 패턴을 가정했을 때 소요되는 시간의 평균
-
최악 시간 복잡도 : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간
-
Big-O Notation : 점근 표기법의 하나. 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현(알고리즘의 복잡도를 표현할 때 흔히 쓰임)
-
입력의 크기가 n일 때, 입력의 크기에 비례하여 O(log n), O(n) 등 시간 소요
-
선형 시간 알고리즘 - O(n)
- ex) n 개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 탐색 알고리즘을 적용
-
로그 시간 알고리즘 - O(log n)
- ex) n개의 크기 순으로 정렬된 수에서 특정 값을 찾기 위해 이진 탐색 알고리즘을 적용
-
이차 시간 알고리즘 - O(n^2)
- ex) 삽입 정렬 -> worst case O(n^2)
- 꽤나 복잡한 문제 : 배낭 문제 (서로 다른 무게와 값을 갖는. 어떻게 담아야 최대 값을 얻을까?)
- 다이나믹 프로그래밍 방법을 적용해서 풀 수 있는 문제이긴 함.
7강 연결 리스트
- 추상적 자료 구조 (Abstract Data Structures)
- Data (ex 정수, 문자열 레코드)
- A set of operations ( 삽입, 삭제, 순회, 정렬 , 탐색 etc)
기본적 연결 리스트
- Node
- Data (Node 내의 데이터는 다른 구조로 이루어질 수 있다. ex 문자열, 레코드 등)
- Line(next)
- 리스트의 맨 앞을 Head라고 한다.
- 리스트의 맨 끝 노드를 Tail이라고 한다.
- 연결 리스트 안에 노드가 몇 개 있는지 기록해두는 것 또한 좋을 것이다.
class Node:
def __init__(self,item):
self.data = item
self.next = None
class LinekedList:
def __init__(self):
self.nodeCount = 0
self.head = None
self.tail = None
-
연산 정의
- 특정 원소 참조 (k번째)
- 리스트 순회
- 길이 얻어내기
- 원소 삽입
- 원소 삭제
- 두 리스트 합치기
- 첫 번째 노드는 1부터 구현할 거야. 0은 따로 빼두고.
- 특정 원소 참조
def getAt(self,pos):
if pos <= 0 or pos> self.nodeCount:
return None
i = 1
curr = self.head
while i < pos:
curr = curr.next
i += 1
- 배열과 비교한 연결 리스트
- 저장공간 -> 배열 : 연속한 위치 / 연결 리스트 : 임의의 위치
- 특정 원소 지칭 -> 배열 : 매우 간편 / 연결 리스트 : 선형 탐색과 유사
- 연습문제 -> 리스트 순회
- 아래처럼 코드를 짜면 안된다
def traverse(self):
answer = []
i = 1
while i <= self.nodeCount:
answer.append(self.getAi(i))
return answer
- 헤드에서부터 다음 다음을 찾아가는 방식.
실습 문제 답안
class Node:
def __init__(self, item): # 생성자
self.data = item
self.next = None
class LinkedList:
def __init__(self): # 생성자
self.nodeCount = 0
self.head = None
self.tail = None
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount:
return None
i = 1
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def traverse(self):
curr = self.head
arr = []
while curr != None:
arr.append(curr.data)
curr = curr.next
return arr
# 이 solution 함수는 그대로 두어야 합니다.
def solution(x):
return 0
8강 연결리스트(2)
남아있는 3가지 -> 원소 삽입/ 원소 삭제/ 두 리 스트 합치기를 구현하겠다.
- 연결리스트 원소의 삽입
- def insertAt(self,pos,newNode):
- pos가 가리키는 위치에 (1 <= pos <= nodeCount+1)
- newNode를 삽입
- 성공 실패에 따라 True/False를 리턴
- L.insertAt(pos,newNode)
- 원소의 삽입 - 코드 구현
지난 시간에 활용했던 getAt(pos-1) 을 활용
def insertAt(self,pos,newNode):
prev = self.getAt(pos-1)
newNode.next = prev.next
prev.next = newNode
self.nodeCount+=1
- 코드 구현 주의 사항
- (1) 삽입하려는 위치가 맨 앞일 때, -
- prev 없음
- Head 조정 필요
- (2) 삽입하려는 우치가 리스트 맨 끝일 때
- Tail 조정 필요
- 빈 리스트에 삽입할 때 ? -> 위 두 조건을 잘 처리하면 된다.
def insertAt(self,pos,newNode):
if pos < 1 or pos > self.nodeCount +=1:
return False
if pos == 1:
newNode.next = self.head
self.head = newNode
else:
if pos == self.nodeCount+1:
prev = self.tail
else:
prev = self.getAt(pos-1)
newNode.next = prev.next
prev.next = newNode
if pos == self.nodeCount+1:
self.tail = newNode
self.nodeCount+=1
return True
- Q) 삽입하려는 위치가 리스트 맨 끝일떄? 즉 pos == nodeCount +1인 경우
- tail을 가리키고 있던 이유는 리스트이 맨 끝에 삽입을 쉽게 하려고 했던 거니까.
- tail을 내 앞에 있을 노드는, tail이 가리키고 있는 노드구나 라고 생각이 가능할거야.
- 즉 맨 앞에서부터 찾아갈 필요가 없다.
수업시간 내용을 위한 코드
class Node:
def __init__(self, item):
self.data = item
self.next = None
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = None
self.tail = None
def __repr__(self):
if self.nodeCount == 0:
return 'LinkedList: empty'
s = ''
curr = self.head
while curr is not None:
s += repr(curr.data)
if curr.next is not None:
s += ' -> '
curr = curr.next
return s
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount:
return None
i = 1
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
if pos == 1:
newNode.next = self.head
self.head = newNode
else:
if pos == self.nodeCount + 1:
prev = self.tail
else:
prev = self.getAt(pos - 1)
newNode.next = prev.next
prev.next = newNode
if pos == self.nodeCount + 1:
self.tail = newNode
self.nodeCount += 1
return True
def getLength(self):
return self.nodeCount
def traverse(self):
result = []
curr = self.head
while curr is not None:
result.append(curr.data)
curr = curr.next
return result
def concat(self, L):
self.tail.next = L.head
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount
연결 리스트 원소 삽입의 복잡도
- 맨 앞에 삽입하는 경우 : O(1)
- 중간에 삽입하는 경우 : O(n)
- 맨 끝에 삽입하는 경우 : O(1)
연결리스트의 연산 - 원소의 삭제
def popAt(self,pos):- pos가 가리키는 위치의(1 <= pos <= nodeCount)
- node를 삭제하고
-
그 node의 데이터를 리턴
- 코드 구현 주의 사항
- (1) 삭제하려는 node가 맨 앞의 것일 때, -> prev없음, head 조정 필요
- (2) 리스트 맨 끝의 node를 삭제할 떄 -> Tail 조정 필요
-
유일한 노드를 삭제할 떄 ? 이 두 조건에 의해 처리가 되는가 ?
- 그런데, tail을 가지고 있었으니까, 삽입과 마찬가지로 맨 끝의 노드를 삭제하는 것.
- 즉 pos==nodeCount인 경우 삭제 가능 ?
- 한번에 처리할 수 없다. prev를 찾을 방법이 없으므로,
-
따라서 맨 앞에서 삭제하는 경우만 O(1)
- 이런걸 피하기 위해서 이중 연결 리스트를 적용한다. 일반적으로 많이 사용
연결 리스트 연산 - 두 리스트의 연결
def concat(self,L):- 두 개의 리스트를 이어 붙인다는 거야.
- self.tail.next = L2.head
- self.tail = L2.tail
def concat(self,L):
self.tail.next=L.head
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount
- 만약 뒤에 비어있는 리스트라면 ?
- 그러면 tail이 None이 되어버려서 문제가 발생
- 따라서 L.tail이 유효한 경우에만 사용 가능
try/except문 사용 예시
text = '100%'
try :
number = int(text) # 에러가 발생할 가능성이 있는 코드
except ValueError: # 에러 종류 ex) IndexError
print('{}는 숫자가 아닙니다.'.format(text))
8강 실습 내용 - 연결리스트 노드 삭제 구현하기
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
elif self.nodeCount == 1 and pos == 1:
data = self.head.data
self.head = None
self.tail = None
else:
prev = self.getAt(pos-1)
data = prev.next.data
if pos == self.nodeCount:
self.tail = prev
prev.next = None
else:
prev.next = prev.next.next
self.nodeCount -= 1
return data
9장. 연결리스트 (3)
연결리스트가 힘을 발휘할 때, 순서지어서 확인할 때, 예를 들어 핸드폰에서 중간에 뭘 띄워놓고, 삭제할 때. (창을 여러개 띄웠다고 가정)
- 삽입과 삭제가 유연하다는 것이 큰 장점이다.
- 그런데 ? 우리가 해놨던 것이 과연 ?
- self.getAt(pos-1)을 이용해서 매번 찾아가잖아.
- 그래서 생각하게 된게, 삽입과 삭제가 유연하다는 장점을 살리기 위해
insertAfter(prev,newNode)-> 맨 앞에서는 어떻게 ?popAfter(prev)-> 맨 앞에서 삭제하려고 하면?- 이렇게 노드 앞 뒤 자리에 삽입 삭제를 하려고 한다.
- 동일한 메소드를 일반적으로 적용하고 싶어서. 맨 앞에 더미노드를 추가한 형태이다.
- head가 더미노드를 가리키고 그 뒤로 -> 쭉 가다가 마지막에 tail이 가리키며 끝난다.
- 그래서 지난 시간에 1번으로 인덱스를 붙여갔던 거다.
조금 변형된 연결 리스트
- 맨 앞에 dummy node를 추가한 형태
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = Node(None)
self.tail = None
self.head.next = self.tail
따라서 기존의 연산들도 수정이 되어야 한다.
- 길이 얻어내기
- 리스트 순회
- 특정 원소 참조 (k번째)
- 원소 삽입
- 원소 삭제
- 두 리스트 합치기
리스트 순회
def traverse(self):
result = []
curr = self.head
while curr.next:
curr = curr.next
result.append(curr.data)
k번째 원소 얻어내기
def getAt(self,pos):
if pos < 0 or pos > self.nodeCount: # 기존에는 pos<1이었는데, 이젠 0이야.
return None
i = 0 # 지난번 코드에서는 1이었어. 이제는 0으로 바꿨어
curr = self.head
while i < pos:
cur = cur.next
i+=1
return curr
노드의 삽입 연산
def insertAfter(self,prev,newNode):
newNode.next = prev.next
if prev.next is None:
self.tail = newNode
prev.next = newNode
self.nodeCount+=1
return True
prev가 가리키는 node다음에
newNode를 삽입하고
성공/실패에 따라 True / False를 리턴한다는 점
지난 번과 동일
메서드 insertAt()의 구현
이미 구현한 insertAfter()를 호출하는 것으로 이용 가능
(1) pos 범위 조건 확인
(2) pos==1 인 경우에는 head 뒤에 새 node 삽입
(3) pos == nodeCount+1 인 경우는 prev<-tail
(4) 그렇지 않은 경우에는 prev <- getAt()
def insertAt(self,pos,newNode):
if pos<1 or pos> self.nodeCount+1:
return False
if pos != 1 and pos == self.nodeCount+1:
prev = self.tail
else:
prev = self.getAt(post -1)
return self.insertAfter(prev,newNode)
연결리스트 연산 삭제
주의사항 - prev가 마지막 node일 때, (prev.next == None)
- 삭제할 노드가 없음
- return None
(2) 리스트의 맨 끝의 node를 삭제할 때(curr.next == None)
- tail 조정 필요
두 리스트의 연결
앞서 있는 리스트의 tail 로 부터 head의 다음 노드를 이어줘야 함.
self.tail.next = L2.head.next
self.tail = L2.tail
def concat(self,L):
self.tail.next = L.head.next
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount
실습
(1) method popAfter() 구현 (2) method popAt() 구현
- 앞서 구현한 popAfter()를 호출하여 이용하는 것
def popAfter(self, prev):
curr = prev.next
if(prev.next == None):
return None
elif(curr.next == None):
prev.next = None
self.tail = prev
else:
prev.next = curr.next
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
if pos == 1 and self.nodeCount == 1:
prev = self.head
else:
prev = self.getAt(pos-1)
return self.popAfter(prev)
참고자료 [파이썬_자료구조_알고리즘]https://programmers.co.kr/learn/courses/57