본문 바로가기

자료구조15

[프로그래머스] - 길 찾기 게임 (파이썬) import sys sys.setrecursionlimit(10**3) class Node: def __init__(self, index, x, y): self.index = index self.x = x self.y = y self.left = None self.right = None class Tree: def __init__(self, index, x, y): self.head = Node(index, x, y) def insert(self, index, x, y): curr = self.head while True: if curr.x > x: if curr.left == None: curr.left = Node(index, x, y) break else: curr = curr.left else: .. 2022. 2. 15.
[백준] 2357번 - 최솟값과 최댓값 (파이썬) # 최솟값과 최댓값 import sys input = sys.stdin.readline MAX = sys.maxsize N, M = map(int, input().split()) arr = [0] for _ in range(N): arr.append(int(input())) tree = [[MAX, 0] for _ in range(N+1)] tree2 = [[MAX, 0] for _ in range(N+1)] def update(i, target): while i 0: tree2[i][0] = min(tree2[i][0], target) tree2[i][1] = max(tree2[i][1], target) i -= (i & -i) def find(start, end): result_min = MAX re.. 2022. 2. 13.
[백준] 10868번 - 최솟값 (파이썬) # 최솟값 import sys input = sys.stdin.readline MAX = sys.maxsize N, M = map(int, input().split()) arr = [0] for _ in range(N): arr.append(int(input())) def update(i, target): while i 0: update(i, x) update2(i, x) for _ in range(M): start, end = map(int, input().split()) print(find(start, end)) 자료구조, 펜윅트리 1. 입력을 받고 트리를 두 가지를 할당해준다. 2. 초기값을 이용해서 펜윅트리를 업데이트해준다. - update : 앞에서 뒤로 펜윅트리를 만든다. - update2 :.. 2022. 2. 13.
[백준] 2042번 - 구간 합 구하기 (파이썬) # 구간 합 구하기 import sys input = sys.stdin.readline N, M, K = map(int, input().split()) arr = [0] for _ in range(N): arr.append(int(input())) tree = [0] * (N+1) def update(i, diff): while i 0: result += tree[i] i -= (i & -i) return result def print_sum(start, end): print(fromOne_sum(end) - fromOne_sum(start-1)) for i, x in enumerate(arr): if i > 0: update(i, x) for _ in range(M+K): type, a, b = map.. 2022. 2. 12.
[프로그래머스] - 자동완성 class Trie(): head = [0, dict()] def add(self, word): current = self.head current[0] += 1 for x in word: if x not in current[1]: current[1][x] = [0, dict()] current = current[1][x] current[0] += 1 def check(self, word): current = self.head result = 0 for x in word: if current[0] == 1: return result result += 1 current = current[1][x] return result def solution(words): answer = 0 T = Trie() for w.. 2022. 2. 7.
[백준] 1202번 - 보석 도둑 (파이썬) # 보석 도둑 import sys import heapq input = sys.stdin.readline N, K = map(int, input().split()) gem = [] for _ in range(N): weight, cost = map(int, input().split()) heapq.heappush(gem, (weight, cost)) bags = [] for _ in range(K): w = int(input()) bags.append(w) bags.sort() result = 0 temp = [] for bag_weight in bags: while gem: if bag_weight >= gem[0][0]: weight, cost = heapq.heappop(gem) heapq.heap.. 2022. 1. 30.
[백준] 9935번 - 문자열 폭발 (파이썬) # 문자열 폭발 str = input().strip() bomb = list(input().strip()) result = [] for i in range(len(str)): result.append(str[i]) if result[-len(bomb):] == bomb: for _ in range(len(bomb)): result.pop() if result: print(*result, sep='') else: print('FRULA') 자료구조 (스택) 1. result에 문자열을 하나씩 넣는다 2. 만약 result의 뒤에서 bomb길이 만큼의 문자열이 bomb와 같으면 bomb의 길이만큼 pop을 해준다. 3. result가 빈 문자열이면 'FRULA'를 아니면 result를 출력 기존의 파이썬 문.. 2022. 1. 28.

티스토리툴바