목록자료구조 (26)
정화 코딩
EDOC 2023-W 7회차 과제 (최소 공통 조상)
09-5. 최소 공통 조상 074. LCA (백준 11437번) https://www.acmicpc.net/problem/11437 import sys from collections import deque input = sys.stdin.readline n = int(input()) tree = [[] for _ in range(n+1)] depth = [0] * (n+1) parent = [0] * (n+1) visited = [False] * (n+1) def bfs(node): que = deque() que.append(node) visited[node] = True level = 1 size = 1 cnt = 0 while que: now = que.popleft() for nxt in tree..
EDOC 2023-W 6회차 과제 (이진 트리 / 세그먼트 트리)
09-3. 이진 트리 070. 트리 순회 (백준 1991번) https://www.acmicpc.net/problem/1991 from sys import stdin n = int(stdin.readline()) tree = {} for _ in range(n): self, left, right = stdin.readline().split() tree[self] = [left, right] def preOrder(now): if now != '.': print(now, end='') preOrder(tree[now][0]) preOrder(tree[now][1]) def inOrder(now): if now != '.': inOrder(tree[now][0]) print(now, end='') inOrd..
EDOC 2023-W 5회차 과제 (트리 알아보기 / 트라이)
09-1. 트리 알아보기 067. 트리의 부모 찾기 (백준 11725번) https://www.acmicpc.net/problem/11725 from sys import stdin import sys sys.setrecursionlimit(10 ** 6) n = int(stdin.readline()) g = [[] for _ in range(n+1)] parent = [0] * (n+1) def dfs(pre, cur): for nxt in g[cur]: if nxt != pre: parent[nxt] = cur dfs(cur, nxt) for _ in range(n-1): a, b = map(int, stdin.readline().split()) g[a].append(b) g[b].append(a) d..
EDOC 2023-W 3회차 과제 (다익스트라 / 벨만-포드)
08-4. 다익스트라 056. 최단경로 (백준 1753번) https://www.acmicpc.net/problem/1753 from sys import stdin from queue import PriorityQueue import sys v, e = map(int, stdin.readline().split()) g = [[] for _ in range(v+1)] dst = [sys.maxsize] * (v+1) visited = [False] * (v+1) que = PriorityQueue() start = int(stdin.readline()) dst[start] = 0 que.put((0, start)) for _ in range(e): a, b, c = map(int, stdin.readlin..
EDOC 2023-W 3회차 정모 (유니온 파인드 / 위상 정렬)
A. 여러분의 다리가 되어 드리겠습니다! (백준 17352번) https://www.acmicpc.net/problem/17352 #pythonfrom sys import stdinimport syssys.setrecursionlimit(100000)def find(a): if parent[a] == a: return a else: parent[a] = find(parent[a]) return parent[a]def union(a, b): a = find(a) b = find(b) if a != b: parent[b] = an = int(stdin.readline())parent = [i for i in range(n+1)]fo..
EDOC 2023-W 2회차 과제 (유니온 파인드 / 위상 정렬)
08-2. 유니온 파인드 050. 집합의 표현 (백준 1717번) https://www.acmicpc.net/problem/1717 from sys import stdindef find(a): if parent[a] == a: return a else: parent[a] = find(parent[a]) return parent[a]def union(a, b): a = find(a) b = find(b) if a != b: parent[b] = an, m = map(int, stdin.readline().split())parent = [i for i in range(n+1)]for _ in range(m): x, a, b =..
꾸준히 문제 풀기 - 1월, 2월
EDOC 과제를 다 풀고 추가로 푸는 문제들을 꾸준히 문제 풀기 글로 따로 정리하려고 한다. 1/14. 덩치 (백준 7568번) https://www.acmicpc.net/problem/7568 #python from sys import stdin n = int(stdin.readline()) data = [] ans = [] for _ in range(n): x, y = map(int, stdin.readline().split()) data.append([x, y]) for i in range(n): k = 1 for j in range(n): if (data[j][0] > data[i][0]) and (data[j][1] > data[i][1]): k += 1 ans.append(k) for x in..
파이썬으로 스택 구현하기 (by 리스트) class Stack : def __init__(self) : self.items = [] def push(self, item) : self.items.append(item) def pop(self) : if not self.isEmpty() : return self.items.pop() else : print("Stack underflow") exit() def peek(self) : return self.items[-1] def isEmpty(self) : return not self.items def size(self) : return len(self.items) def clear(self) : self.items = [] 파이썬으로 큐 구현하기 (by 리스..