얼레벌레 얼레벌레

그리디 알고리즘 - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 -> 기준에 따라 좋은 것을 선택함 ex) 가장 큰 순서대로, 가장 작은 순서대로 - 그리디 알고리즘은 자주 정렬 알고리즘과 짝을 이룸 예제 - 거스름돈) : 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정할 때, 손님에게 거슬러줘야할 동전의 최소 개수 구하기 가장 큰 화폐 단위부터 돈을 돌려주자 1260원일때 -> 500 * 2 + 100 * 2 + 50 * 1 + 10 * 1 -> 총 동전의 개수 6개 # 시간 복잡도 o(k) n = 1260 count =0 coin_type =[500,100,50,10] for coin in coin_types: count += n // coin n %= coin print(..

양방향 연결리스트란? 한쪽으로만 링크를 연결하지 말고 양쪽으로 - 앞으로도(다음node) 뒤로도(이전node)진행가능 node의 구조 확장 class Node: def __init__(self, item): self.data = item self.prev = None self.next = None 리스트 처음과 끝에 dummy node를 두자 -> 데이터를 담고 있는node들은 모두 같은 모양 L.insertAfter next = prev.next newNode.prev self.nodeCount: return None if pos > self.nodeCount // 2: i = 0 curr = self.tail while i < self.nodeCount - pos + 1: curr = curr.pre..

연결리스트는 삽입과 삭제가 유연하다는 것이 가장 큰 장점이다. (1)에서는 특정번째를 지정하여 원소를 삽입/삭제하는 연산을 구현해보았다면, (2)에서는 특정원소의 바로 다음을 지정하여 원소를 삽입/삭제하는 연산을 정의하고 구현해 볼 것이다. 그러자면, 맨 앞에 원소를 추가 (삽입) 하거나 맨 앞의 원소를 제거 (삭제) 하는 연산을 지정하기가 애매해짐 이런 경우에도 동일한 방법을 적용하기 위해서, 이번에는 연결 리스트의 맨 앞에다가 데이터 원소를 담고 있지 않은, 그냥 자리만 차지하는 노드 -dummy node 리스트를 정의하자 0번째 노드에 dummy node를 정의하자..! class Node: def __init__(self, item): self.data = item self.next = None ..

연결리스트에 관한 삽입 삭제 순회의 함수들을 모두 구현한 것이다. 문제는 popAt()함수를 구현하는 것이었다. 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 self.nodeCount: return None i = 1 curr = self.head while i < pos: curr = curr.next i += 1 return curr def insertAt(self, pos, newN..

연결리스트 (Linked Lists) - 선형배열이 번호가 붙여진 칸에 원소들을 채워넣는 방식이라고 하면, 연결리스트는 각 원소들을 줄줄이 엮어서 관리하는 방식임 - 연결리스트는 원소들이 링크라고 불리는 고리로 연결되어 있으므로, 가운데를 끊어 하나를 삭제하거나 삽입하기가 쉬움 - 하지만 메모리 소요가 큼 추상적 자료구조 Data ex) 정수, 문자열 ,레코드 ..... A set of operations ex) 삽입 삭제 순회/ 정렬 탐색 Node - data - link(next) 리스트의 맨앞 : head 리스트의 맨끝 : tail class Node: def __init__(self, item): self.data = item self.next = None class LinkedList: def ..

시간 복잡도 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계 공간 복잡도 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계 평균 시간 복잡도 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균 최악 시간 복잡도 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간 빅오 notation 점근 표기법의 하나 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현 (알고리즘의 복잡도를 표현할 때 흔히 쓰임) o(logn): 입력의 크기의 로그에 비례하는 시간 소요 o(n) : 입력의 크기에 비례하는 시간 소요 계수는 그다지 중요하지 않음 선형시간 알고리즘 - o(n) 예 : n개의 무작위로 나열된 수에서 최댓값을 찾기위해 선형탐색 알고리즘을 적용 최댓값 - 끝까지 다 살펴보기 전까지..