🍋 ⚾️ 💻 🎬 🎮

TiL 26

99클럽 코테 스터디 _ 6일차 TIL (DFS, BFS)

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

99클럽 코테 스터디 _ 5일차 TIL (투 포인터)

[백준] 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 투 포인터투 포인터를 쓰기 위해서 용액의 특성값..

99클럽 코테 스터디 _ 4일차 TIL (이분탐색)

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

99클럽 코테 스터디 _ 3일차 TIL (이분탐색, Bisect)

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

99클럽 코테 스터디 _ 2일차 TIL (이분탐색)

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

99클럽 코테 스터디 _ 1일차 TIL (해시, 이분탐색)

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

728x90
반응형