한 걸음씩 기록하며

⛏ 문제 파악 얼마 전에 풀었던 회전하는 큐와 비슷한 문제 Deque를 구현하는 문제이면서 동시에, circular Queue를 보여주기 위한 문제 rotate를 사용하면 쉽게 풀 수 있다. 👉🏻 답안 from sys import stdin from collections import deque N, K = map(int, stdin.readline().split(' ')) answer = [] arr = deque([]) for i in range(1, N+1): arr.append(i) for j in range(N): arr.rotate(-K+1) answer.append(str(arr.popleft())) print("" %(", ".join(answer))) 📑 간단한 설명 파이썬 내장함수 d..

⛏ 문제 파악 최소힙을 구하는 문제 저번에 풀었던 최대힙을 구하는 문제에서 음수 부분만 제거하면 된다. 👉🏻 답안 from sys import stdin import heapq N = int(stdin.readline()) heap = [] for i in range(N): x = int(stdin.readline()) if x != 0: heapq.heappush(heap, [x]) elif x == 0: if heap: print(heapq.heappop(heap)[0]) else: print("0") 📑 간단한 설명 그냥 간단하게 지난 번 리스트에서 [1]을 제거했다.

1. BST (Binary Search Tree) vs Tree Tree 트리는 그 자체로는 데이터의 특성에 아무런 제약이 없음 트리 구조는 특정한 값을 찾기 위해서 모든 값을 탐색해야함 (시간 복잡도 O(N)) BST 이진 탐색 트리는 이진 트리의 구조이지만, 데이터 값의 제약이 생긴다는 점에서 차이를 보인다. 아래와 같은 제약을 줆으로써, 탐색 속도를 향상시켜준다. (시간 복잡도 O(logN)) 하나의 노드라도 아래의 조건을 충족하지 못하면 BST가 아님 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리 중복된 키를 허용하지 않음 2. BST 연산 2.1 검색 전..

1. 트리와 용어 정리 트리(Tree)는 그래프의 일종으로, 노드들이 나무가지처럼 연결된 비선형 계층적 자료구조이다. 트리는 데이터 구조의 계층적인, 상하 관계 속성을 표현한다. 선형적 자료구조는 데이터의 이전 데이터나 다음 데이터의 순서가 존재했다. 트리도 내부적으로 순서 정보를 가지도록 구현할 수 있지만, 트리라는 자료구조 자체에서 데이터의 순서는 그리 중요한 요소가 아니다. * Tree와 관련된 용어 정리 - 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다. - 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다. - 내부(internal) 노드: 단말 노드가 아닌 노드 - 간선(edge): 노드를 연결하는 선 (l..

⛏ 문제 파악 최대힙을 구하는 문제 시간초과 때문에 heapq을 임포트 안하고 그냥 구현하면 시간초과가 뜬다 파이썬 내장모듈인 heapq은 최소힙만 지원하기 때문에 최대힙으로 사용하기 위해서는 값을 음수로 변환하는 방법을 사용해야한다. 음수로 변환하는 것은 튜플이나 리스트를 이용하거나, 값에 * -1을 하는 방법이 있다. 👉🏻 답안 from sys import stdin import heapq N = int(stdin.readline()) heap = [] for i in range(N): x = int(stdin.readline()) if x != 0: heapq.heappush(heap, [-x, x]) elif x == 0: if heap: print(heapq.heappop(heap)[1]) e..

⛏ 문제 파악 세계 질서를 잘 잡아줘야한다. 우리는 그 질서를 스택 이용하여 잡겠다. 스택은 후입선출이다. 👉🏻 답안 from sys import stdin while True: stack = [] sentence= stdin.readline().rstrip() if sentence == ".": break for i in sentence: if i == "(" or i == "[": stack.append(i) elif i == ")": if stack and stack[-1] == "(": stack.pop() else: stack.append(")") break elif i == "]": if stack and stack[-1] == "[": stack.pop() else: stack.append..

Deque (Double-ended-queue) 덱(deque)은 double-ended queue의 줄임말이다. rear로만 데이터를 삽입했던 큐와 달리, front와 rear에서 삽입과 삭제가 모두 가능한 양방향 큐이다. 연속적인 메모리를 기반으로 하는 시퀀스 컨테이너이고, 선언 이후 크기를 줄이거나 늘릴 수 있는 가변적 크기를 갖는다. 또한 중간에 데이터가 삽입될 떄 다른 요소들을 앞, 뒤로 밀 수 있다. 중간 삭제시 성능이 그리 좋진 않다. 삽입 삭제 연산은 O(1)의 시간 복잡도를 가지고, 스택&큐와 달리 index를 통해 요소들에 탐색이 가능하므로 검색 또한 O(1)의 시간복잡도를 가진다. 장점 구현자의 편의에 따라 deque는 stack처럼 사용할 수도 있고, queue처럼 사용할 수 있다...

1. Stack 후입선출(Last-In First-Out / LIFO) : 나중에 들어온 데이터가 먼저 나감 후임선출 방식의 자료구조로, 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 대표적인 스택의 활용으로는, 컴퓨터 내부의 프로세스 구조의 함수 동작 방식이 있다. 장점 구조가 단순해서 구현이 쉽다. 데이터 저장/ 읽기 속도가 빠르다 단점 데이터 최대 개수를 미리 정해야한다. 저장 공간의 낭비가 발생할 수 있다. 미리 최대 개수만큼의 저장 공간을 확보해야한다. 스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다. (이 경우 위에서 열거한 단점이 발생한다.) 2. Queue 1) Queue 선입선출 (First-In Fast-Out / FI..