All Good

전체 글 - Table of Contents288

🍝LIS(Longest Increasing Subsequence) O(n^2)/O(nlogn) LIS(O(n^2))「1」 LIS의 길이만 구할 경우 🍝 주어진 수열에서 가장 긴 증가하는 부분 수열을 구하는 문제. 이 때 부분 수열은 연속적일 필요 없고 unique할 필요도 없다. 띄엄띄엄 떨어진 원소 모음의 subsequence가 increasing하기만 하면 되며, increasing subsequence 중 최대 길이를 찾으면 된다. 예를 들어 [3, 10, 2, 1, 20]이 있다면 longest increasing subsequence는 [3, 10, 20] / [3,2]에서는 [3]과 [2] / [50, 3, 10, 7, 40, 80]에서는 [3, 7, 40, 80]이 있다. 이는 dp를 이용해서 쉽게 구할 수 있다. D[i]를 i번째 index에서 끝나는 LIS 길이라고 정의. .. Computer Science/Algorithms 2024. 1. 6.
★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.
📡Kadane's Algorithm 🔊 주어진 배열에서 '부분연속수열합'의 최댓값을 구하는 알고리즘이다. DP로도 구할 수 있고, well-known Kadane's Algorithm을 활용해서도 매우 간단히 해결할 수 있다. 🔊 각 element traversing할 때마다 max() 두 번 사용. max_till_now로 최종 최댓값 update하고, cur_max는 현재위치의 원소 only & 현재위치의 원소 포함 그 전의 cur_max 합 두 개중 최댓값 update. 즉 cur_max로 각 원소를 포함한 부분연속수열합 최댓값을 계속 구해나가는 dp 방식이나 마찬가지. 다만, dp는 최종적으로 max() 한 번 사용이지만, Kadane's algorithm에서는 max()를 그 때 그 때 update하는 방식만 차이점. 핵심은 '현.. Computer Science/Algorithms 2024. 1. 3.
🔬 Parametric Search 🐧 최적화 문제를 여러번의 결정문제(예 혹은 아니오)로 바꾸어 이분탐색으로 해결하는 기법 → 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 - 여기서 최적화란, 어떤 값을 최대한 높이거나 낮출 때 사용 🐧 ① Parametric Search로 구하고자 하는 값을 이분탐색으로 증/감 바꾸며 YES/NO 여부 확인 ② 결정문제를 만족하고 만족하지 않음에 따라 이분탐색 범위를 end를 mid-1 또는 start를 mid+1로 설정해 절반으로 줄임 ★ 탐색의 범위가 log2N씩 줄어드므로 1억이 넘어가는 범위라 하더라도 매우 효과적인 시간 내에 탐색 가능 ★ ① BOJ 3079 입국심사(골드5) : 입국심사대의 개수가 주어지고, 방문한 인원 M이 주어진 상태에서 입국심사를 받는 시간 x의 최.. Computer Science/Algorithms 2023. 12. 31.
★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.
2️⃣Bipartite Graph intro 2️⃣ Bipartite Graph(이분 그래프)란, 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로 칠할 수 있는 graph를 뜻한다. 2️⃣ a graph in which the vertices can be divided into two disjoint sets, such that no two vertices within the same set are adjacent. In other words, it is a graph in which every edge connects a vertex of one set to a vertex of the other set. : 즉, graph 내의 모든 간선은 두 가지 다른 색깔의 정점으로 무조건 연결되어 있어야 하고, 반대로 말하.. Computer Science/Algorithms 2023. 12. 21.
★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.
🌳 Binary Tree 🌳 theory 🌳 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 : Binary Tree is defined as a tree data structure where each node has at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. 🌳 트리 관련 용어 ① root node: 부모가 없는 최상위 노드 ② leaf node: 자식이 없는 노드 ③ size: 트리에 포함된 모든 노드의 개수 ④ depth: 특정 노드에서 루트 노드부터의 거리(즉 위 1번 노드의 깊이는 0, 2번 노드의 깊이는 1) ⑤ h.. Computer Science/Data Structures 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.

티스토리툴바