개발왕 양선규

import sys sys.setrecursionlimit(10**9) # 재귀호출 최대 깊이를 늘려준다 pre = [] # 전위순회 순서 입력받기 while True: try: n = int(sys.stdin.readline()) pre.append(n) except: break def postOrder(nodeList): # 전위순회 결과를 입력받는다 생각지 말고, 그냥 노드 리스트를 입력받는다 생각하면 이해가 편함 if len(nodeList) == 0: # 빈 리스트라면 return return left, right = [], [] root = nodeList[0] # root노드 기준으로 작은값, 큰값으로 나눈다 for i in range(1, len(nodeList)): # root노드 다음값..

import sys n = int(sys.stdin.readline()) tree = {} for _ in range(n): root, left, right = sys.stdin.readline().split() tree[root] = [left, right] # {'root' : ['left', 'right']} 형태로 저장한다 def preorder(root): # 전위 순회 if root != '.': print(root, end='') preorder(tree[root][0]) preorder(tree[root][1]) def inorder(root): # 중위 순회 if root != '.': inorder(tree[root][0]) print(root, end='') inorder(tree[r..

n = int(input()) # 변의 길이 board = [list(map(int, input().rstrip())) for _ in range(n)] # rstrip() 하면 개행문자 제거해서 한번에 입력할 수 있게 해준다 def quadTree(x, y, n): # x, y좌표와 변 길이를 입력받는다, 첫 호출은 0,0을 입력 color = board[x][y] for i in range(x, x+n): for j in range(y, y+n): # 현재 사각형의 모든 칸을 검사한다 if color != board[i][j]: # 색깔이 다른 칸이 하나라도 있다면 4등분 재귀호출 한다 print('(', end='') # 출력 양식에 맞게 괄호 입력 quadTree(x, y, n//2) # 출력 양..

import sys n = int(sys.stdin.readline()) # 탑 개수 towerList = list(map(int, sys.stdin.readline().split())) # 탑 목록 result = [0] * n # 결과 리스트 stack = [] # 후보 탑을 저장할 스택 for i in range(n): while stack: if towerList[stack[-1][0]]

import sys from collections import deque n = int(sys.stdin.readline()) # 보드의 크기 k = int(sys.stdin.readline()) # 사과의 개수 apple = [list(map(int, sys.stdin.readline().split())) for _ in range(k)] # 사과의 위치 l = int(sys.stdin.readline()) # 방향 전환 횟수 change = [] for _ in range(l): changeSec, changeDir = input().split() changeSec = int(changeSec) change.append([changeSec, changeDir]) # 초, 방향을 입력받되, 초는 int..

해시 테이블(Hash Table)- 먼저 키(key)와 값(value)으로 구성된 데이터가 필요하다.- 여기서 “key”를 해시값으로 만들어, 해당 해시값을 “인덱스”로써 활용하여 테이블에 저장한다. 여기서 해시값은 정수 형태가 된다.- 데이터(value)를 해시하여 인덱스로 쓰는 거 아니냐는 사람들이 있는데, 이럴 경우 value가 같으면 인덱스가 중복될 수 있다. 해시함수는 같은 입력에 대해서 항상 같은 해시값을 만들기 때문이다.- 어떤 값을 찾든 O(1)의 복잡도를 가진다. 고유값으로 접근하면 되기 때문.- 해시 테이블에서 만들어진 원소를 버킷(Bucket)이라고 한다. 해시 테이블의 장/단점- 장점 : 자료의 검색, 읽기, 저장 속도가 빠르다. 즉 데이터 조회가 빠르다.- 장점 : 자료가 중복되는..

import heapq as hq import sys n = int(input()) hqq = [] for _ in range(n): x = int(sys.stdin.readline()) if x >= 1: hq.heappush(hqq, -x) # hq는 최소힙만 지원하기 때문에, 최대힙 처럼 사용하기 위해 음수로 저장 else: # 음수로 저장하면 -가 붙으니, 가장 큰 값이 가장 위로 가게 된다 if len(hqq) == 0: print(0) else: print(abs(hq.heappop(hqq))) # 값을 꺼낼 땐 절댓값을 이용해 양수로 만든다 우선순위 큐가 사용된 문제다. 최대 힙으로 우선순위 큐를 구현하여 문제를 해결할 수 있다. 스택, 큐 문제처럼 문제 자체는 어렵지 않으나, 힙이라는 자료..

import sys from collections import deque n = int(sys.stdin.readline()) home = deque() for _ in range(n): control = sys.stdin.readline().split() c = control[0] if c == 'push': home.append(int(control[1])) elif c == 'pop': if len(home) == 0: print(-1) else: print(home.popleft()) elif c == 'size': print(len(home)) elif c == 'empty': if len(home) == 0: print(1) else: print(0) elif c == 'front': if l..

스택(Stack) - 후입선출(Last In First Out) 구조 - 마지막에 들어온 데이터가 가장 먼저 나간다 - 파이썬에서는 리스트와 pop(), append() 메소드로 스택을 구현할 수 있다 큐(Queue) - 선입선출(First In First Out) 구조 - 먼저 들어온 데이터가 가장 먼저 나간다. “공정한 자료구조” - from collections import deque 사용해서 deque 자료구조를 활용하는 게 좋다 - deque는 스택, 큐의 장점을 모두 채택한 것인데 리스트에 비해 빠르고 queue 라이브러리를 이용하는 것 보다 간단하다 - append(), popleft()를 이용하여 큐를 구현할 수 있다 DFS(Depth-First Search, 깊이 우선 탐색) - 그래프에..