one Book a Day

간단한 hash-map import sys input = sys.stdin.readline num_set = {} N = int(input()) A = list(map(int, input().split())) for num in A: num_set[num] = True M = int(input()) Q = list(map(int, input().split())) for num in Q: if num in num_set: print(1) else: print(0)

Load Balancing 부하분산 : 해야 할 작업을 나눠서 서버의 부하를 분산시키는 서비스. request를 각각 서버들이 원하는 대로 나눠주는 것. 서비스 이용자가 많아지며 트래픽을 현재의 서버로 감당하기 힘들어져 나온 개념.(Scale Out) 서비스 트래픽 증가로 인해 하나의 서버로 감당이 불가능 => Scale UP!(서버 성능을 올리자!) 그래도 안 돼? => Scale Out!(여러대의 서버로 나누자!) 미리 측정된 웹 서버의 능력에 따라 분배 or 서버의 부하상태에 따라 분배. 부하 할당 알고리즘 Round Robin 단순히 Round Robin으로 분산하는 방식입니다. Least Connections 연결 개수가 가장 적은 서버를 선택하는 방식입니다. 트래픽으로 인해 세션이 길어지는 경..

기본적인 union-find로 무리짓고 대푯값의 갯수를 세는 문제입니다. def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(x, y): x = find(x) y = find(y) if x > y: x, y = y, x parents[y] = x for test in range(1, int(input()) + 1): N, M = map(int, input().split()) parents = {i: i for i in range(1, N + 1)} for i in range(M): a, b = map(int, input().split()) if find(a) != find(b):..

가중치가 있는 단방향 그래프의 왕복 최단거리를 묻는 문제로 정방향, 역방향으로 다익스트라를 그려준 후 합치면 왕복 최단거리를 구할 수 있습니다. (역방향 다익스트라는 돌아오는 경로에 대한 역탐색이기 때문) from heapq import heappop, heappush def dijkstra(graph, start): dp_dists = {i: float('inf') for i in range(1, N + 1)} dp_dists[start] = 0 heap = [] heappush(heap, (0, start)) while heap: cur_dists, cur_node = heappop(heap) for next_node, next_dist in graph[cur_node]: dists = cur_dis..

가중치 간선이 존재하는 2차원 배열의 이동 간 최소 cost를 묻는 문제로 다익스트라를 이용해 풀 수 있습니다. from heapq import heappush, heappop def dijkstra(x, y): heap = [] dists[x][y] = 0 heappush(heap, (0, 0, 0)) while heap: cur_dist, x, y = heappop(heap) for dx, dy in delta: nx, ny = x + dx, y + dy if 0

bfs로 대륙별 grouping한 후 행, 열 순회로 최소거리 측정하고 kruskal로 연결. 연결된 간선 n - 1개 미만이면 -1출력 import sys input = sys.stdin.readline from collections import deque from heapq import heappop, heappush def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(x, y): x = find(x) y = find(y) if x > y: x, y = y, x parents[y] = x def grouping_continent(x, y): q = deque() q.appen..

조합으로 거리구하고 간선 heap으로 정렬 후 n-1개만큼 연결 from heapq import heappop, heappush def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(x, y): x = find(x) y = find(y) if x > y: x, y = y, x parents[y] = x for test in range(1, int(input()) + 1): N = int(input()) X = list(map(int, input().split())) Y = list(map(int, input().split())) parents = {i: i for i in rang..

위클리 3주차이며 네이버 기출문제 중 하나인 퍼즐조각 채우기입니다. 가로세로퍼즐에 fit이 맞는 block을 채우는 문제로 이 문제는 빈칸없이 꽉 채워야 하기 때문에 hashing을 이용할 수 있을 것이라 생각했고 각 모양을 tuple형태의 key로 dictionary에서 관리하는 식으로 풀었습니다. from collections import defaultdict, deque def solution(game_board, table): answer = 0 n = len(game_board) delta = ((-1, 0), (0, 1), (1, 0), (0, -1)) def bfs(graph, start_x, start_y, num): ret = [(0, 0)] q = deque() q.append((sta..

집단을 나눠full-fill 하고 확장. 확장 시킬때마다 각 자리의 거리정보를 갱신 import sys from collections import deque, defaultdict input = sys.stdin.readline def find_continent(x, y): q = deque() q.append((x, y)) matrix[x][y] = numbering while q: x, y = q.popleft() for dx, dy in delta: nx, ny = x + dx, y + dy if 0

튜플을 이용해 union-find로 그룹핑했습니다 import sys input = sys.stdin.readline from collections import defaultdict def find(a): if parents[a] == a: return a parents[a] = find(parents[a]) return parents[a] def union(a, b): a = find(a) b = find(b) if a > b: a, b = b, a parents[b] = a N = int(input()) matrix = [list(map(int, list(input().rstrip()))) for _ in range(N)] delta = ((0, 1), (1, 0), (-1, 0), (0, -1)) ..