aeightchill

[백준] 2573. 빙산 / 골드4코드 변수 정의function : melt_icebergnew_graph : 녹은 후의 빙산 상태 그래프 생성을 위한 리스트directions : 상하좌우 탐색을 하기 위한 배열sea_cnt : 빙산에 인접한 바다의 개수function : count_icebergiceberg_cnt : 빙산 덩어리 개수function : maingraph : 현재 빙산 상태day : 경과 일수max_day : 무한 루프 방지용 최대 일수BFS시간복잡도 : O(N x M)from collections import deque# 현재 그래프 빙산 상태에서 녹은 후의 그래프를 반환하는 함수def melt_iceberg(graph, N, M): # 새로운 빙산 상태를 저장할 리스트 초기화 ..

[백준] 1707. 이분 그래프 / 골드4코드 변수 정의graph : 인접 리스트 그래프colors : 정점 색상 표시 배열results : 이분 그래프이면 YES, 아니면 NOBFS시간복잡도 : O(k * (V + E))from collections import deque# 이분 그래프인지 확인하는 함수def is_bipartite_graph(V, E, edges): # 그래프 초기화 graph = [[] for _ in range(V + 1)] for u, v in edges: graph[u].append(v) graph[v].append(u) # 색상 표시 배열 (0: 미방문, 1: 검정, -1: 흰색) colors = [0] * (V+1) ..

[백준] 2667. 단지번호붙이기 / 실버1코드 변수 정의graph : 아파트(1)가 표시된 지도cnt : 현재 단지 내 아파트 수dx, dy : 상하좌우를 탐색할 변수. 상(-1, 0), 하(1,0), 좌(0,-1), 우(0,1)nx, ny : 현재 위치에서 상하좌우로 이동했을 때의 좌표apartment : 각 단지의 아파트 수를 저장할 리스트BFS시간복잡도 : O(N^2)from collections import deque# BFS를 이용하여 연결된 아파트 단지의 크기를 계산하는 함수def bfs(graph, i, j, visited): q = deque([(i, j)]) # 큐에 시작 좌표(i, j)를 추가 cnt = 1 # 현재 단지 내 아파트 수 (초기값=1, 시작점 포함) wh..

[백준] 1697. 숨바꼭질 / 실버1코드 변수 정의x, time : 현재 위치, 현재 위치까지 오는 데 걸리는 시간ans : 수빈이가 동생을 찾을 수 있는 가장 빠른 시간BFS시간복잡도 : O(N)  *N=100001 (문제에서 위치 최대 값+1)from collections import deque# bfs 함수 : N에서 K로 이동하는 최소 시간을 계산def bfs(N, K, time): # 큐를 생성하고 초기 위치와 시간(time=0)을 삽입 q = deque() q.append((N, time)) # 위치 x를 방문했는지 방문 여부 기록 visited = [False] * 100001 # 최소 시간 변수 (초기값=무한대) ans = float('inf') ..

[백준] 1260. DFS와 BFS / 실버2DFS, BFS시간복잡도 : O(V(노드 수) + E(간선 수))from collections import deque# DFSdef dfs(graph, v, visited): visited[v] = True # 현재 위치 방문 표시 print(v, end = ' ') for i in graph[v]: if not visited[i]: dfs(graph, i, visited)# BFSdef bfs(graph, V, N): visited = [False] * (N + 1) q = deque([V]) # BFS 탐색 시작 위치 visited[V] = True # 시작 위치 방문 표시 while q..

[백준] 2470. 두 용액 / 골드5코드 변수 정의liquids : 가지고 있는 랜선 길이 리스트min_diff : 두 용액의 합 중 0에 가까운 값liquid_sum : 현재 선택된 두 용액의 합Two Pointers시간복잡도 : O(N)def binary_search(liquids, N): left, right = 0, N - 1 min_diff, ans = float('inf'), [0, 0] while left abs(liquid_sum): min_diff = abs(liquid_sum) ans = [liquids[left], liquids[right]] if liquid_sum 투 포인터투 포인터를 쓰기 위해서 용액의 특성값..

[백준] 2343. 기타 레슨 / 실버1코드 변수 정의videos : 강의의 길이가 담긴 리스트play_time : 한 블루레이에 들어간 영상의 길이cnt : 최대 영상 길이(mid)에 따라 생성되는 블루레이 총 개수ans : 가능한 블루레이 크기 중 최솟값Binary Search시간복잡도 : O(N * log(sum(videos)))def binary_search(videos, M): left, right = max(videos), sum(videos) # 블루레이 개수: N개, 블루레이 개수: 1개 ans = 0 while left mid: cnt += 1 play_time = 0 play_time += vid..

[백준] 11663. 선분 위의 점 / 실버3코드 변수 정의lidx : 선분(line)의 시작점(left)이 리스트(points)에서 추가될 수 있는 위치의 인덱스 값ridx : 선분(line)의 끝점(right)이 리스트(points)에서 추가될 수 있는 위치의 인덱스 값 + 1points : N개의 좌표상의 점lines : M개의 선분Binary Search시간복잡도 : O(N*logN + M*logN)     - points.sort : O(N * logN)     - M개 선분을 binary_search : O(M * logN)            *bisect : O(logN)from bisect import bisect_left, bisect_rightdef binary_search(point..

[백준] 1654. 랜선 자르기 / 실버2코드 변수 정의lans : 가지고 있는 랜선 길이 리스트cnt : 특정 길이를 만족하는 랜선의 총 개수max_length : N개를 만들 수 있는 랜선의 최대 길이(반환값)Binary Search시간복잡도 : O(N * log(max(lans)))def binary_search(K, N, lans): left, right = 1, max(lans) max_length = 0 while left = N: max_length = mid left = mid + 1 else: right = mid - 1 return max_lengthdef f(): K, N = map(in..

[백준] 2776. 암기왕 / 실버4코드 변수 정의ynum : 연종이의 '수첩1'dnum : 동규의 '수첩2'Hash시간복잡도 : O(T * (N1 + N2))def f(): N1 = int(input()) ynum = set(map(int, input().split())) # 집합 변환 -> 해시 기반 탐색 N2 = int(input()) dnum = list(map(int, input().split())) for num in dnum: print(1 if num in ynum else 0)def solution(): T = int(input()) for _ in range(T): f()solution()해시 기반 탐색을 하기 위해 ynum..