one Book a Day

이진트리?? 최대 두개의 자식 노드를 가지는 트리형태의 자료구조. 단순 저장보다는 탐색혹은 정렬을 위함. 힙도 이진트리의 일종. 이진 탐색트리? 이진트리의 특수한 경우. 모든 노드에 대해 그 왼쪽 자식들의 값이 현재 노드보다 작거나 같으며 오른쪽 자식들의 값이 현재 노드의 값보다 크다는 조건을 만족하면 이진 탐색 트리가 된다(작은값은 왼쪽 큰값은 오른쪽에 저장.) 가장 처음 입력된 값이 root 클래스 정의, 초기화 노드 클래스 정의 class Node(object): def __init__(self, data): self.data = data self.left = self.right = None 이진 탐색 트리 클래스 정의 class BinarySearchTree(object): def __init__..

모든 노드에서 모든 노드까지의 정보를 구해야하는 플로이드 워셜 문제다. 요새 최단거리 문제해결 연습을 많이하고있는데 플로이드 워셜의 핵심은 이것. "내가 저기 갈껀데 다른곳의 정보를 이용해서 가는게 빠르냐 아니면 그냥 가는게 빠르냐?" 이거다. 여기선 전자를 이용할 수 있느냐를 물어보는 문제. (다른곳의 정보는 나뿐만아니라 도착지에서도 알고있어야한다.) 알고있다면 1 아니면 0 import sys input = sys.stdin.readline N, M = map(int, input().split()) knowing_tall = [[0 for _ in range(N)] for _ in range(N)] # 플로이드 워셜은 인접행렬을 쓴다. for i in range(M): high, low = map(i..

LIS 시리즈 문제중 하나이다. 역순으로도 구해서 각 지점 카운트합이 가장 높아지는 부분이 꺽이는 부분. N = int(input()) A = [0] + list(map(int, input().split())) LDS = [1]*(N+1) LIS = [1]*(N+1) Bi = [] # 바이토닉 수열의 핵심은 앞에서 LIS하고 역순 LIS dp를 각각 만들어 # 두 dp 인자의 합 = 올라갔다 내려오는 cnt를 만드는 것. # 싸피 CT문제 예제로 나오는 문제라 아이디어는 매우 쉬웠다. for i in range(1,N+1): for j in range(1,i): if A[i]>A[j] and LIS[i]A[-j] and LDS[-i]

그냥 문제 나온대로 읽고 BFS만들어서 풀었다. 더 좋은 방법이 있을지도.. import sys input = sys.stdin.readline from collections import deque def BFS(i,j): candy_max = 0 queue = deque() queue.append([i,j]) visited_candy = [[-1 for _ in range(M)] for _ in range(N)] visited_candy[i][j] = maze[i][j] while queue: x,y = queue.popleft() if x==N-1 and y==M-1: if visited_candy[x][y] > candy_max: candy_max = visited_candy[x][y] for nx..

많은 방법이 있겠지만 나는 전체 다 구하는걸 좋아하므로 counter썼다. from collections import Counter n,d = input().split() n_list = ''.join(map(str,list(range(1,int(n)+1)))) b = Counter(n_list) print(b[d])

워낙 유명한 문제. 사용중인 회의실의 end시간기준 최소힙을 만들어 start기준 오름차순 정렬된 input과 비교하면 간단히 풀린다. import sys input = sys.stdin.readline from heapq import heappop,heappush N = int(input()) meeting_schedule = [list(map(int,input().split())) for _ in range(N)] meeting_schedule.sort() cnt = 0 heap = [] for start,end in meeting_schedule: if not heap or heap[0] > start : cnt +=1 heappush(heap,end) else: heappop(heap) heapp..

최단거리 문제연습. 모든 정점에서 모든 정점. 주의 할 점은 동일 출발, 동일 도착 간선이 있고 때문에 입력 시 최솟값만을 입력해주어야함. 플로이드 워샬은 간선이 없는 전 구간에 대해 조사하기 때문에 사실 인접리스트의 의미가 좀 없는 것 같다. 인접행렬로 표현하는게 더 효율저일듯 싶다. import sys input = sys.stdin.readline def floid_washal(): dp_dists = [[float('inf') for _ in range(n+1)] for _ in range(n+1)] for cur_node in graph: for next_node,dist in graph[cur_node]: if dp_dists[cur_node][next_node] > dist: dp_dists..

커맨드가 주어지고 최종값을 뽑는 문제는 실제 커맨드대로 다 하면 망한다. index만 바꾸거나 slice를 한다거나 최대한 소요를 줄이는 방법으로 사고하자. import sys input = sys.stdin.readline from collections import deque # R 뒤집기, D 버리기함수 # 비어있을때 D쓰면 에러. T = int(input()) for test in range(T): p = input().rstrip() n = int(input()) xi = input().rstrip().rstrip(']').lstrip('[').split(',') Xi = deque() if not n: xi.pop() flag=0 switch = 0 for x in xi: Xi.append(x)..

최단거리 알고리즘 연습하는중. 음수 간선이 있을 시 다른 모든 정점으로 가는 최단거리를 구하는 문제이다. 밸만포드로 구했다. import sys input = sys.stdin.readline def bellman_ford(start): dp_dists[start] = 0 # 모든 정점 수만큼 검사 for i in range(N): # 매 정점마다 모든 간선 검사(그 점에서 타 점까지) for cur_node in graph: for next_node, dist in graph[cur_node]: # 방문 안했거나 다음점보다 지금 가는 경로가 더 짧으면 갱신 if dp_dists[cur_node] !=float('inf') and dp_dists[next_node] > dp_dists[cur_node]+..

Disjoint Sets는 다양한 알고리즘에 사용될 수 있다. 특히 무방향 그래프 내에서의 사이클을 판별할 때 사용될 수 있다. 참고로 방향그래프에서의 사이클 여부는 DFS를 이용해 판별할 수 있다. [ 동작 과정 ] 1. 각 간선을 확인하며 두 노드의 루트노드를 확인한다. 2. 루트노드가 서로 다르다면 두 노드에 대하여 union연산을 수행한다. 3. 루트노드가 서로 같다면 사이클이 발생한 것이다. 4. 그래프에 포함되어있는 모든 간선에 대하여 1~3과정을 반복한다. 만약 모든 간선이 처리될 때까지 사이클이 발생하지 않았다면 해당 그래프에서는 사이클이 없다라고 판단될 수 있다. # 특정 원소가 속한 집합을 찾기위해서 루트노드를 반환하는 find연산 def find_parent(parent, x): # ..