데굴데굴

디큐 Dequeue / deque dequeue는 Stack과 Queue를 합친 자료구조로, 왼쪽과 오른쪽에서의 삽입과 삭제가 모두 가능하다. 파이썬에는 collections 모듈에 deque 클래스로 구현되어 있다. from collections import deque 오른쪽에 값 넣을 때 = append / 왼쪽에 값 넣을 때 = appendleft 가장 오른쪽 값을 삭제할 때 = pop / 가장 왼쪽 값 삭제할 때 = popleft 디큐 활용 예: Palindrome 문자열 s와 s를 거꾸로 뒤집은 문자열이 서로 같다면 Palindrome ex) 기러기, salsa, 다시합창합시다 (디큐를 쓰지 않고도 Palindrome 판별 코드를 작성할 수 있음.) 디큐를 쓰지 않은 코드 s = input('단..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 https://www.youtube.com/watch?v=nqCNk_DmPio&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=11 앞서 배운 스택이 후입선출의 구조였다면, 큐는 선입선출(First-in First-Out)의 구조이다. 먼저 들어온 것이 먼저 나간다. 그래서 선착순 자료구조라고도 한다. 파이썬 리스트로 큐 구현하기 1 enqueue(value): 큐의 가장 오른쪽 끝에 값을 삽입 dequeue(): 큐의 가장 왼쪽 값을 삭제 후 리턴 front(): 큐의 가장 왼쪽 값을 리턴 len(): 큐의 저장된 값의 개수 isEmpty(): 큐가 비었는지 알려줌 class Queue: def __init__(se..

* Stack 클래스를 정의하여 코드를 작성했다. 입력 1 2 3 + 4 / + 출력 2.2500 Stack 클래스 정의 push(value): 스택에 값을 넣음 pop(): 스택의 가장 위에 있는 값을 삭제 후 리턴, 스택이 비어있으면 "Stack is empty"를 출력 top(): 스택의 가장 위에 있는 값을 리턴, pop()과 마찬가지로 스택이 비어있으면 "Stack is empty"를 출력 __len__(): 스택의 길이 출력 isEmpty(): 스택이 비어있는지 아닌지 판단 class Stack: def __init__(self): self.items = [] def push(self, val): self.items.append(val) def pop(self): try: return self..

* class로 Stack을 정의한 후 코드를 작성했다. * 수식에는 이항연산자만 사용한다고 가정한다. 어설프지만 infix와 postfix 그리고 스택은 아래 링크에 정리해두었다. 순차적 자료구조 & 스택 (stack) 순차적 자료구조 (Sequential data structures) 1. 배열, 리스트 - index로 임의의 원소에 접근 - 연산자 [ ] - 삽입 (append, insert) - 삭제 (pop, remove) 2. stack, queue, dequeue - 제한된 접근(삽입, 삭제).. haruisshort.tistory.com 입력 1 + ( 2 + 3 ) / 4 출력 1 2 3 + 4 / + Stack 클래스 정의 push(value): 스택에 값을 넣음 pop(): 스택의 가..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 https://www.youtube.com/watch?v=OzFXiukhv8o&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=8 순차적 자료구조 (Sequential data structures) 1. 배열, 리스트 - index로 임의의 원소에 접근 - 연산자 [ ] - 삽입 (append, insert) - 삭제 (pop, remove) 2. stack, queue, dequeue - 제한된 접근(삽입, 삭제)만 허용 - 실제로 이런 자료구조가 많이 쓰임. stack : LIFO (Last In First Out) 밑에서부터 차곡차곡. push. 중간 삽입 불가. queue : FIFO (FIrst In Firs..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 https://www.youtube.com/watch?v=Lqd8o7vL2Z8&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=6 배열 (array) vs. 리스트(list) 파이썬 - 가장 기본적인 순차적인(sequential) 자료구조 C언어의 배열 A[2] = A[2] + 1은 기본연산만 포함하기 때문에 O(1) A[2]의 주소: RAM A[0] 주소 + 2 * 4bytes 100 + 8 = 108 배열은 읽기와 쓰기를 연산으로 제공. 기본시간 내에 다 수행할 수 있다. 파이썬의 리스트 A = [2, 4, 0, 5] 결정적인 차이: 객체가 다른 메모리에 저장됨 A[2] = A[2] + 1 0이 1로 바뀌는 것이 ..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 (주요 알고리즘 배울 때마다 슈퍼마리오 블로그 정독할 것!) [강의 주요 내용] 알고리즘의 수행시간을 함수로 표현 다항식의 성질에 따라서 수행시간이 어떻게 변화하는가 수행시간을 표기하는 간단한 방법 함수로 표현하여 그래프를 그림. Algorithm2가 Algorithm1보다 2배 느리다. True Algorithm3 n5/3면 항상 Algorithm2보다 느리다. T1(n), T2(n), T3(n) 앞의 두 개는 n값에 따라 선형적으로 증가하는 반면, T3(n)은 제곱으로 증가함. (최고차항이 n제곱) n이 증가함에 따라 얼마만큼 빠른 속도로 기본연산 횟수가 증가하는가는 최고차항이 결정함. 모든 함수를 다 분석해서 표현하기보다는 최고차항만 표시하면 수..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 알고리즘의 시간복잡도를 어떻게 측정하는가? algorithm ArrayMax(A,n): # 지금부터 ArrayMax라는 가상의 코드를 기술하겠다 input: n개의 정수를 받는 배열 A output: A의 수 중에서 최대값 리턴 currentMax = A[0] for i=1 to n-1 do if currentMax 현실적으로 불가능 (고려해야 할 입력이 무한히 많기 때문) 가장 안 좋은 입력(worstcase input, 기본연산을 가장 많이 요구하는 입력)에 대한 기본..