All Good

BOJ80

★DP Expert(Easy) I - 4 Solved★ ★ 14003 가장 긴 증가하는 부분 수열 5 ★ import sysinput=sys.stdin.readlineN=int(input())A=list(map(int,input().split()))#binary searchdef binary_search(l, i, x): start,end=0,len(l)-1 while start ⛹️ LIS의 길이와 내용을 O(nlogn) 시간 복잡도 이내로 구하는 교과서 문제. LIS의 길이는 ans_num list에서 binary search로 update하며 내용 추가. LIS의 내용은 ans_i list에서 앞선 binary search로 삽입되는 원소의 index를 update하며 거꾸로 최댓값부터 1이 될때까지 해당 되는 inde.. BOJ/🏅 2024. 1. 7.
★DP Upper-Advanced I - 8 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()))de.. BOJ/🥇 2024. 1. 5.
★Binary Search Advanced I - 2 Solved★ ★ 2295 세 수의 합 ★ import sys input=sys.stdin.readline def 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(len(L)-1,-1,-1): for y in range(0,x).. BOJ/🥇 2023. 12. 29.
★Coordinate Compression Advanced - 2 Solved★ ★ 18869 멀티버스 II ★ import sys input=sys.stdin.readline from collections import defaultdict M,N=map(int,input().split()) cu_list,ans=[],0 def get_compressed_coordinate(l): sort_l = sorted(set(l)) cd = {sort_l[i]: i for i in range(len(sort_l))} x = [cd[n] for n in l] return x for _ in range(M): universe=list(map(int,input().split())) compressed_universe = get_compressed_coordinate(universe) cu_list.. BOJ/🥇 2023. 12. 28.
★Tree Advanced I - 1 Solved★ ★ 1068 트리 ★ import sys input=sys.stdin.readline N=int(input()) l=list(map(int,input().split())) tree=[[] for _ in range(N)] visited=[[] for _ in range(N)] start_node = 51 ans = 0 def dfs(tree, visited, delete_node, start_node): global ans visited[start_node] = True if len(tree[start_node]) == 0: #leaf-node ans += 1 else: len_child = len(tree[start_node]) if len_child == 1: #one child node child .. BOJ/🥇 2023. 12. 22.
★Tree Upper-Intermediate I - 3 Solved★ ★ 1991 트리 순회 ★ import sys input=sys.stdin.readline def pre_order(node): print(node, end='') if tree[node][0] != '.': pre_order(tree[node][0]) if tree[node][1] != '.': pre_order(tree[node][1]) def in_order(node): if tree[node][0] != '.': in_order(tree[node][0]) print(node, end='') if tree[node][1] != '.': in_order(tree[node][1]) def post_order(node): if tree[node][0] != '.': post_order(tree[node].. BOJ/🥈 2023. 12. 19.
★BFS&DFS Advanced I - 10 Solved★ ★ 7576 토마토 ★ (최단경로) import sys input=sys.stdin.readline from collections import deque M,N=map(int,input().split()) graph=[] starts=[] depths=[[0]*M for _ in range(N)] visited=[[False]*M for _ in range(N)] def BFS(graph, depths, starts, visited): queue = deque(starts) dx,dy=[0,0,-1,1],[-1,1,0,0] while queue: v = queue.popleft() for i in range(4): nx,ny=v[0]+dx[i],v[1]+dy[i] if 0 BOJ/🥇 2023. 12. 15.
★BF Upper-Intermediate I - 2 Solved★ ★ 2503 숫자 야구 ★ import sys from itertools import permutations input=sys.stdin.readline N=int(input()) pos=list(permutations(['1','2','3','4','5','6','7','8','9'],3)) idxs=[n for n in range(len(pos))] def get_strike_ball(a,b): strike=0 for x,y in zip(a,b): if x==y: strike+=1 return (str(strike),str(len(a+b)-len(set(a+b))-strike)) for _ in range(N): num,S,B=input().split() didxs=[] for i in idxs: p.. BOJ/🥈 2023. 10. 26.
★Greedy Upper-Advanced I - 1 Solved★ ★ 1700 멀티탭 스케줄링 ★ ❤️‍🔥 Optimal Page Replacement 알고리즘에서 콘센트에 처음으로 꼽는 page fault 횟수를 제외한 page fault의 횟수를 최소화하는 문제 ❤️‍🔥 ① 콘센트 채우기 → ② 콘센트에 존재하지 않는 첫 기기 등장하면(page fault 상황) (1) 이미 채운 기기 중 아예 존재하지 않는 기기가 있다면 해당 기기와 교체 (2) 없다면 콘센트 기기의 index 확인해 가장 나중에 등장하는 기기와 교체(greedy) import sys input=sys.stdin.readline N,K=map(int,input().split()) names=list(map(int,input().split())) ans=0 ps=[0]*N #power_strip in.. BOJ/🥇 2023. 10. 18.
★BF Advanced I - 3 Solved★ ★ 14500 테트로미노 ★ import sys input=sys.stdin.readline N,M=map(int,input().split()) tetris=[] for _ in range(N): tetris.append(list(map(int,input().split()))) ans=0 for i in range(N): for j in range(M): #1x4 if j BOJ/🥇 2023. 10. 6.
★Greedy Advanced I - 4 Solved★ ★ 1744 수 묶기 ★ import sys input=sys.stdin.readline N=int(input()) arr=[int(input()) for _ in range(N)] ans=0 pos,neg,zero,one=[],[],[],[] for n in arr: if n==0: zero.append(0) elif n==1: one.append(1) elif n>0: pos.append(n) else: neg.append(n) #1. don't tie ones ans+=len(one) #2.tie pos(from the biggest) pos.sort(reverse=True) for i in range(0,len(pos),2): if i==len(pos)-1:ans+=pos[i] else:ans+=.. BOJ/🥇 2023. 8. 30.
★Greedy Intermediate II - 4 Solved★ ★ 2012 등수 매기기 ★ import sys input=sys.stdin.readline N=int(input()) ans,i=0,1 for x in sorted([int(input()) for _ in range(N)]): ans+=abs(x-i) i+=1 print(ans) 💲 greedy 알고리즘은 직관적으로 optimal solution의 모음 → 전체 최적 solution이라 생각하고 진행하는 경우가 많다. 💲 greedy 관점 분석 : 개별 상황) 각자 예상한 등수에 실제 등수 부여, 그리고 불만도 구하기 : 종합 상황) 불만도의 합 / 최적의 종합 상황) 불만도의 합이 최소 ★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 먼저 예.. BOJ/🥈 2023. 8. 20.

티스토리툴바