one Book a Day

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)) ..

재귀 dp로 안쪽에서부터 경우의 수를 뽑아오며 밖으로까지 cnt 값을 누적시켜 꺼내왔습니다. import sys input = sys.stdin.readline ans = list(map(int, input().split())) dp = [[[[-1 for score in range(11)] for pre2 in range(6)] for pre in range(6)] for depth in range(11)] def make_dp(depth, pre, pre2, score): if dp[depth][pre][pre2][score] != -1: return dp[depth][pre][pre2][score] if depth == 10: return 1 if score >= 5 else 0 cnt = 0 fo..

정렬 후 투포인터로 풀면 됩니다. import sys input = sys.stdin.readline N = int(input()) M = int(input()) arr = sorted(map(int, input().split())) left = 0 right = N - 1 answer = 0 while left M: right -= 1 else: left += 1 print(answer)

로직이 완전 깔끔하지는 못하지만 시간 내에 통과하도록 최소한의 연산을 하도록 노력함. 기본적으로 재귀를 통해 폭탄을 한발씩 떨어뜨리는 함수, 폭탄이 블록과 만나면 연쇄 폭발을 일으키는 재귀함수 폭발 후 빈칸에 블록을 중력을 적용해 채우는 함수. 3가지 함수와 남은 블록을 카운팅해주는 함수 1개의 함수 총 4개의 함수로 구성했으며 중간에 블록이 모두 터졌을 경우 바로 종료하지는 못했으나 더이상 N을 파고들지 않아도 W를 0~ W-1까지 순회해서 continue로 넘어가게 만듦. 모두 터지지 않을 경우의 로직은 효율적으로 짰다고 생각함. def delete_block(board, x, y, cnt): board[x][y] = 0 if cnt > 1: for i in range(1, cnt): for dx, ..

조합을 dfs로 짜고, 조합에 속한 요소와 속하지 못한 요소간 차이를 비교. 삼성기출 스타트와 링크. 웰노운 def choose_parts(cur_node, cnt): global min_gap if cnt == N // 2: S1, S2 = 0, 0 for i in range(N - 1): for j in range(i + 1, N): if check[i] and check[j]: S1 += S[i][j] + S[j][i] elif not check[i] and not check[j]: S2 += S[i][j] + S[j][i] min_gap = min(min_gap, abs(S1 - S2)) for next_node in range(cur_node, N): if not check[next_node]:..

dfs 분기를 이용해 사각형을 그리도록 직선이동 시킴. 간만큼 돌아오도록 dx, dy를 이용해 통제. # 기본적으로 방향성 유지 이동, 간만큼 돌아오도록 dx, dy 변수가 늘어났다가 0으로 돌아오게끔 통제. def dfs(x, y, dx, dy, direction, cnt): global max_size nx, ny = x + delta[direction][0], y + delta[direction][1] # 속행 if 0