All Good

BOJ/🥇21

★Topology Sort Advanced - 2 Solved★ ★ 2252 줄 세우기 ★import sysinput=sys.stdin.readlinefrom collections import dequeN,M=map(int,input().split())indegree = [0] * (N+1)graph = [[] for _ in range(N+1)]for _ in range(M): A,B=map(int,input().split()) graph[A].append(B) indegree[B] += 1result = []queue = deque()#1for i in range(1,N+1): if indegree[i] == 0: queue.append(i)#2while queue: node = queue.popleft() result.. BOJ/🥇 2024. 12. 29.
★Divide & Conquer Upper-Advanced I - 7 Solved★ ★ 11442 홀수번째 피보나치 수의 합 ★n=int(input())BIG=1_000_000_007def get_power(a,b,c): if b  🧚 F1부터 Fn까지의 홀수번째 피보나치 수의 합은 n이 홀수일 경우 F(n+1), n이 짝수일 경우 F(n)으로 구하면 된다. (피보나치 포스팅 증명 참조) 이 때 F 피보나치 값은 행렬의 분할정복 거듭제곱 알고리즘을 활용해 O(logn)만에 구하면 된다.★ 11443 짝수번째 피보나치 수의 합 ★n=int(input())BIG=1_000_000_007def get_power(a,b,c): if b =0 else ans+BIG) 🧚 n이 짝수일 경우 F1~Fn까지의 짝수번째 피보나치 수의 합은 F(n+1)-1, n이 홀수일 경우 짝수번째 피보.. BOJ/🥇 2024. 7. 3.
★Divide & Conquer Advanced I - 5 Solved★ ★ 18291 비요뜨의 징검다리 건너기 ★import sysinput=sys.stdin.readlinedef power_divide_conquer(a,b,c): if b==1: return a%c halved = power_divide_conquer(a,b//2,c) if b%2==0: return ((halved%c) * (halved%c)) %c else: return ((halved%c) * (halved%c) * (a%c))%cBIG = 1000000007for _ in range(int(input())): N=int(input()) if N==1: print(1) elif N==2: pri.. BOJ/🥇 2024. 6. 15.
★Math & Geometry Advanced I - 2 Solved★ ★ 1011 Fly me to the Alpha Centauri ★import sysinput=sys.stdin.readlinefor _ in range(int(input())): x,y=map(int,input().split()) diff=y-x closest_root=int(diff**(1/2)) if diff == (closest_root**2): print(closest_root*2-1) elif (diff-(closest_root**2)) 🍋 kn은 kn-1 / kn / kn+1 중 한 개만 가능 + 맨 앞과 맨 뒤의 거리 step은 1만 가능하다는 조건 하에 수학 규칙성을 찾는 문제→ y-x를 diff라고 한다면, 중복된 step 간격 없이 오름차순 -.. BOJ/🥇 2024. 4. 27.
★Implementation&Simluation Upper-Advanced I - 1 Solved★ ★ 19237 어른 상어 ★ import sysinput=sys.stdin.readlinefrom collections import dequeN,M,k=map(int,input().split()) #NxNsize / M sharks / smell limit ktrace=[]smell=[[0]*N for _ in range(N)]sharks=deque()shark_ds_priorities=[]#shark_dsdx,dy=['?',-1,1,0,0],['?',0,0,-1,1]num_of_sharks=Mfor i in range(N): l=list(map(int,input().split())) trace.append(l) for j in range(N): if l[j] != 0: .. BOJ/🥇 2024. 3. 3.
★Stack & Queue & Deque Advanced I - 3 Solved★ ★ 9935 문자열 폭발 ★ import sysinput=sys.stdin.readlines=list(input().rstrip())explode=list(input().rstrip())explode_length=len(explode)ans=[]for x in range(len(s)): ans.append(s[x]) if s[x] == explode[-1]: if explode_length 😮 폭발 문자열의 길이가 최대 36이므로, 문자열을 계속 ans에 넣다가 맨 마지막 폭발 문자열이 들어갈 경우, 앞선 들어간 문자열이 폭발 문자열이 맞다면 pop() 연산으로 빠르게 삭제. 그리고 계속 update. stack에 넣고 빼는 연산 O(1)을 활용해 시간 복잡도 최대 O(N)★ 1.. BOJ/🥇 2024. 2. 24.
★Two-Pointers Advanced I - 10 Solved★ ★ 15961 회전 초밥 ★ import sysinput=sys.stdin.readlinefrom collections import defaultdictN,d,k,c=map(int,input().split())kinds=[int(input()) for _ in range(N)]y,ans,cnt,freq=0,0,0,defaultdict(int)for x in range(N): while cnt 🧦 x와 y 투 포인터 모두 첫 초밥부터 시작하되, k개의 묶음마다 진행하므로(슬라이딩 윈도우 포스팅 참조), x가 전체 초밥 x(1)부터 x(8)까지 움직일 때 y의 끝은 y(1) 부터 y(11)까지 (k=4일 경우) 움직인다 / dictionary 활용해 freq로 종류 개수 update하며 freq.ke.. BOJ/🥇 2024. 2. 11.
★Implementation&Simluation Advanced I - 5 Solved★ ★ 21610 마법사 상어와 비바라기 ★ import sysinput=sys.stdin.readlinefrom collections import dequeN,M=map(int,input().split())baskets=[]for _ in range(N): baskets.append(list(map(int,input().split())))moves=[]for _ in range(M): moves.append(tuple(map(int,input().split())))clouds=deque([[N-2,0],[N-2,1],[N-1,0],[N-1,1]])#(1) clouds movingdx,dy=[0,-1,-1,-1,0,1,1,1],[-1,-1,0,1,1,1,0,-1]for move in moves: .. BOJ/🥇 2024. 1. 28.
★Backtracking Upper-Advanced I - 1 Solved★ ★ 9663 N-Queen ★ #n-queens #place n queens (not placed in the same row / col / diagonal dir) def track(x): global ans if x == N: #finished ans+=1 return else: for ny in range(N): if v1[ny] == v2[x+ny] == v3[x-ny] == False: v1[ny] = v2[x+ny] = v3[x-ny] = True track(x+1) v1[ny] = v2[x+ny] = v3[x-ny] = False N=int(input()) ans=0 v1=[False]*(N) #horizontal 0~(N-1) v2=[False]*(2*N-1) #diagonal (right.. BOJ/🥇 2024. 1. 24.
★Backtracking Advanced I - 3 Solved★ ★ 7490 0 만들기 ★ import sysinput=sys.stdin.readlinedef track(nums,exp,start): if start == len(nums)+1: res=eval(exp) if res == 0: ans=[] for i in range(len(exp)): if i>=1 and exp[i-1].isdigit() and exp[i].isdigit(): ans.extend([' ',exp[i]]) else: ans.append(exp[i]) print(*ans,sep='.. BOJ/🥇 2024. 1. 21.
★DP Upper-Advanced I - 9 Solved★ ★ 12015 가장 긴 증가하는 부분 수열 2 ★ import sysinput=sys.stdin.readlineN=int(input())A=list(map(int,input().split()))#binary searchdef binary_search(l, x): start,end=0,len(l)-1 while start 🍜 LIS(O(nlogn)) 문제★ 12738 가장 긴 증가하는 부분 수열 3 ★ 🍜 수열 원소가 음수여도 LIS(O(nlogn)) 알고리즘은 성립★ 1365 꼬인 전깃줄 ★ import sysinput=sys.stdin.readlineN=int(input())n=list(map(int,input().split()))def binary_search(l,x): start.. BOJ/🥇 2024. 1. 5.
★Binary Search Advanced I - 2 Solved★ ★ 2295 세 수의 합 ★ import sysinput=sys.stdin.readlinedef binary_search(target, l): start,end=0,len(l)-1 while start target: end=mid-1 else: start=mid+1 return False#O(N^2logN)N=int(input())U=set()for _ in range(N): U.add(int(input()))L=list(U)L.sort()two=[]for x in range(len(L)): for y in range(x,len(L)): two.append(L[x]+L[y])two.sort()for x in range(.. BOJ/🥇 2023. 12. 29.

티스토리툴바