All Good

BOJ88

★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.
★Sliding Window Upper + Intermediate - 2 Solved★ ★ 21921 블로그 ★import sysinput=sys.stdin.readlineN,X=map(int,input().split())visitors=list(map(int,input().split()))ans,freq,cursum,start=0,0,0,0for i in range(N): if i ans: ans = cursum freq=1 start+=1if ans == 0: print('SAD')else: print(ans,freq,sep='\n') 🏂 전형적인 슬라이딩 윈도우 문제. 고정된 X일 동안의 방문자 수 최댓값 구하는 문제. 여기에 추가로 최댓값 방문자 수 frequency까지 같이 구하는 문제. ans == cursu.. BOJ/🥈 2024. 10. 7.
★Implementation&Simulation Intermediate II - 3 Solved★ ★ 30458 팰린드롬 애너그램 ★import sysinput=sys.stdin.readlineN=int(input())S=input().rstrip()if N%2==1: left,right=S[:len(S)//2],S[len(S)//2+1:]else: left,right=S[:len(S)//2],S[len(S)//2:]s=left+rightkinds=set(s)for kind in kinds: if s.count(kind)%2!=0: print('No') sys.exit()print('Yes') 😘 바꾸는 횟수는 무제한이므로, 주어진 문자열의 길이가 짝수/홀수에 따라 주어진 문자의 kind 개수 짝/홀 따지면 된다.★ 30618 donstructive ★N=i.. BOJ/🥈 2024. 8. 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 Expert(Easy) I - 1 Solved★ ★ 11440 피보나치 수의 제곱의 합 ★n=int(input())BIG=1_000_000_007def get_power(a,b,c): if b  🙉 F1부터 Fn까지의 모든 피보나치 수의 제곱의 합은 아래와 같이 Fn*Fn+1 결과로 표현할 수 있다.🙉 이 때 Fn에서의 n이 매우 큰 수이므로 Fn을 구하기 위해 분할정복을 이용한 행렬 거듭제곱으로 O(logn)만에 구해야 한다. Fn과 Fn+1을 각각 O(logn)만에 구한 뒤, modulo multiplication property에 의해 ((Fn%BIG) * (Fn+1%BIG))%BIG를 최종 답으로 출력! BOJ/🏅 2024. 6. 30.
★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.
★Stack & Queue & Deque Intermediate II - 3 Solved★ ★ 25497 기술 연계마스터 임스 ★import sysinput=sys.stdin.readlineN=int(input())string=input().rstrip()l,r,s,k,ans=0,0,0,0,0for i in range(N): if string[i] in '123456789': ans+=1 else: if string[i] == 'L': l+=1 elif string[i] == 'R': if l==0: print(ans) sys.exit() else: l-=1 ans+=1 .. BOJ/🥈 2024. 5. 26.
★DP Intermediate II - 2 Solved★ ★ 10826 피보나치 수 4 ★n=int(input())def fibo(n): if n 🎋 전형적인 DP 피보나치 수 알고리즘. 이 때, 메모리 효율성을 위해 두 변수 a, b만 설정하고 a+b는 기존 a에 덮어서 메모리 효율 고려. 이 부분만 주의★ 10211 Maximum Subarray ★import sysinput=sys.stdin.readlineT=int(input())for _ in range(T): N=int(input()) arr=list(map(int,input().split())) if arr[0]🎋 DP 기법 사용할 때, 해당 원소가 반드시 들어가 있을 때와 아닐 때 두가지 케이스로 나눈다. 반드시 들어가 있을 때는 max(앞 원소가 포함했을 때 + 해당 원.. BOJ/🥈 2024. 5. 26.
★BFS&DFS Upper-Intermediate I - 16 Solved★ ☝️ 중상급의 BFS/DFS 유형은 그래프 연결 요소 / 연결 요소 내의 노드 개수 / 최단 거리(Easy) 3개의 알고리즘으로 분류할 수 있다.★ 11724 연결 요소의 개수 ★☝️ DFSimport sysinput=sys.stdin.readlinesys.setrecursionlimit(10000)N,M=map(int,input().split())#dfsdef dfs(graph,start,visited): visited[start] = True for node in graph[start]: if not visited[node]: dfs(graph,node,visited)#graphgraph=[[] for _ in range(N+1)]for _ in range(.. BOJ/🥈 2024. 5. 12.
★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.

티스토리툴바