aeightchill

[백준] 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..

문제유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.파이프를 밀 수 있는 방향은 총 3가지가 ..

문제테트리스는 C열 필드위에서 플레이하는 유명한 게임이다. 필드의 행의 수는 무한하다. 한 번 움직일 때, 아래와 같은 일곱가지 블록 중 하나를 필드에 떨어뜨릴 수 있다.블록을 떨어뜨리기 전에, 플레이어는 블록을 90, 180, 270도 회전시키거나 좌우로 움직일 수 있다. 이때, 블록이 필드를 벗어나지 않으면 된다. 블록을 필드의 바닥이나 이미 채워져있는 칸의 위에 놓여지게 된다.창영이가 하고있는 테트리스는 일반적인 테트리스와 약간 규칙이 다르다. 블록이 떨어졌을 때, 블록과 블록 또는 블록과 바닥 사이에 채워져있지 않은 칸이 생기면 안 된다.예를 들어, 아래와 같이 각 칸의 높이가 2, 1, 1, 1, 0, 1인 경우를 생각해보자. 블록 5번을 떨어뜨리는 방법의 수는 아래와 같이 다섯가지이다.테트리스..