세밍 로그

Queue와 스택은 둘이 함께 잘 비교가 당한다. 오늘 이 둘을 비교해줘버리자! Stack stack은 FILO 구조로, 처음 들어간 요소가 나중에 나중에 나오는 구조, 나중에 들어간 요고가 처음으로 나오는 구조이다. stack은 요소를 삽입할때 push, 요소를 빼낼때 pop 라고한다. 둘 모두 맨 마지막에 요소를 빼고, 넣기 때문에 O(1)이다. 스택은 대부분 array로 구현하는데, array로 구현하기 때문에, 데이터 최대 갯수를 미리 상정해 놔야 해서, 메모리 낭비가 있을 수 있다. 또한, 스택은 재귀적인 특성을 가지기도 하는데, 재귀적인 형태로 구현을 한다면 파이썬의 경우 1000개의 데이터 까지 넣을 수 있다. def recursive_stack(data): if data

링크드 리스트를 구현하려면 꽤 생각해야 할 것이 많습니다. 하지만 차분히 하나씩 구현해보도록 합시다(나에게 하는 얘기) 1. Node 만들기 링크드 리스트는 일단 데이터와 다음 주소를 가르키는 Node가 필요합니다. Node는 계속 반복해서 만들어질 것이기 때문에 클래스 형태로 만들어 줍니다 class Node: def __init__(self, data, next = None): self.data = data self.next = next 2. Node 연결해보기 앞선 Node 클래스에 만들어 놓은 next로 노드를 연결해줍니다. head도 만들어줘야 하는데, linked list의 시작점을 알려줍니다. node_1 = Node(1) node_2 = Node(2) node_1.next = node_2 ..

array와 Linked-List 모두 기본적인 자료구조입니다. 하지만 둘은 memory에 적재되는 방법의 차이로 여러 차이점이 생깁니다. Array array는 정해진 크기의 메모리에 연관된 데이터를 연속적으로 적재합니다. 물리 메모리 상에 봤을때, array의 데이터들이 하나의 4bit씩 차지하며 연달아 있는 것을 볼 수 있습니다. 연달아 붙어 있기 때문에 특정 데이터에 접근하는 것이 굉장히 빠릅니다. array의 첫 데이터 시작부터 접근하고자 하는 데이터의 인덱스(offset)를 산술적으로 더하면 바로 데이터를 찾을 수 있습니다.(O(1), random Access) 마지막의 데이터를 추가(append)하거나 데이터를 삭제하는 것도 마찬가지 입니다. (O(1)) 하지만 중간에 데이터를 삽입(inse..

삽입 정렬은 한 요소를 앞의 요소들과 비교해서 나보다 큰 요소가 있다면 그 요소 앞에 해당 요소를 배치하는 것입니다. 그래서 이 알고리즘을 고안하는데 필요한 것은 1. 한 요소를 특정할 수 있는 부분 2. 해당 요소 앞까지 확인할 수 있는 부분 3. 큰 수를 발견했을때, 위치를 바꿔주는 부분 def insertionSort(data): for i in range(len(data)): for j in range(i): if data[j]

버블정렬은 인접한 두 요소의 데이터를 비교해서, 둘의 자리를 바꾸는 것 입니다. 알고리즘에서 고안되어야 할 것은 1. 인접한 두 요소를 받아들이는 것 2. 두 요소의 크기를 비교해서 자리를 바꾸는 것 이 필요합니다. def bubbleSort(data): for i in range(len(data)): for j in range(i,len(data)): if data[i]

1. map iterable객체(list. tuple, dict, set)를 받아서 각 요소에 함수를 적용시켜주는 함수 2. split 특정문자를 기준으로 문자열을 분리해주는 함수 3. sorted - iterable 객체가 들어왔을 때,정렬된 결과를 반환한 함수 - 시간 복잡도를 고려하지 않아도 되는 간단한 경우 - key 속성으로 정렬기준을 명시, 'reverse' 속성으로 역정렬도 가능한 강력한 내장함수 4. 연산 관련 내장함수 5. 기타 내장 함수 6. math 라이브러리 7. itertools : 반복 관련(확통) 8. bisect : 정렬된 배열에서의 탐색 인덱스 찾는 함수 - bisect.bisect_left : 리스트가 정렬된 순서를 유지하도록 데이터를 삽입할 왼쪽 위치의 인덱스 - bis..

1. 스택 LIFO(Last In First Out)구조 : 가장 마지막에 들어간 원소가 가장 먼저 나옴 리스트를 사용해 구현 알 수 있는 값은 맨 위의 값 : 맨 위에 새 값을 쌓아 올리거나 맨 위에 있는 값을 빼거나 삽입/삭제 삽입 : push 연산 / 삭제 : pop 연산 / 맨위의 값을 보는 연산 : top 연산 파이썬에 따로 라이브러리가 있진 않고 리스트를 스택처럼 사용 O(1) 2. 큐 FIFO(First In First Out) : 가장 먼저 들어갔던 값이 가장 먼저 나온다 2.1 덱 앞 뒤로 모두 출입 가능 파이썬에서 기본으로 제공해주는 collections 모듈의 deque 클래스 사용 : 양방향 연결리스트로 구현되어 있어서 리스트보다 출입 연산에 효율적 : deque가 pop에 O(1)..