All Good

전체 글287

🏘️Euler Sieve intro 🏘️ 소수 판정법으로 유명한 에라토스테네스의 체(Sieve of Eratosthenes)를 개선한 '오일러의 체(Euler Sieve)'에 대해서 소개한다. 에라토스테네스의 체는 소수 판별 시간 복잡도가 O(nloglogn)임이 알려져 있고, 이를 개선한 오일러의 체 시간 복잡도는 단 선형 시간만에 O(n)으로 판별이 가능하다. 🏘️ 에라토스테네스의 체의 시간 복잡도가 선형 시간(O(n))이 될 수 없는 이유는 합성수 210을 들면 쉽게 알 수 있다. 210은 2x3x5x7로 나타낼 수 있는데, 에라토스테네스의 체에 의해서는 2x3x5x7 / 2x3x5x7 / 2x3x5x7 / 2x3x5x7 와 같이 각각 빨간색 숫자일 때 210이 합성수임을 중복해서 알려주고 있다. 🏘️ 따라서, 이를 단 한.. Computer Science/Algorithms 2024. 4. 21.
🥐Counting Sort orders ① 정렬할 데이터 준비 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 ○ 이 때, 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 list를 생성 ○ ② 왼쪽부터 데이터를 하나씩 확인하며 데이터의 값과 동일한 index의 데이터를 1씩 증가시킨다. ③ 오름차순 결과를 확인하기 위해 각 원소의 계수가 저장된 list를 왼쪽 끝부터 돌려 해당 데이터의 값만큼 반복해 인덱스를 출력한다. - 출력 결과 - 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9 about Counting Sort 🥐 특정한 조건이 부합할 때만 사용할 수 있으나 매우 빠르게 동작하는 정렬 알고리즘. (*특정한 조건: 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용) 🥐 .. Computer Science/Algorithms 2024. 4. 17.
🗼Tower of Hanoi intro 🗼 유명한 '하노이의 탑' 알고리즘에 대해 소개한다. 3개의 기둥이 있고, 다양한 크기의 n개의 원판(원판의 크기는 모두 다르다)이 존재한다. 퍼즐을 시작하기 전에는 한 기둥에 n개의 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 아래 3가지 조건을 만족 시키면서 다른 기둥으로 옮겨서 다시 쌓는 퍼즐이다. ① 한 번에 1개의 원판만 옮길 수 있다. ② 가장 위에 있는 원판만 이동할 수 있다. ③ 큰 원판이 작은 원판 위에 있어서는 안된다. 이 때, 최소 이동횟수로 맨 왼쪽 기둥에서 맨 오른쪽 기둥으로 n개의 원판을 순서에 맞추어서 쌓아주면 된다 example demo (n=3) 🗼 n=3일 때 Hanoi Tower를 쌓아보자! 🗼 Hanoi Tower 문제는 크게 아래 3가지 순서로 진.. Computer Science/Algorithms 2024. 4. 9.
➕Merge Sort orders ★ 원소를 개별적으로 나누고, 병합하는 두 과정이 수반되는 정렬 ★ (아래 과정 ②는 divide / ③은 merge) (따라서 merge sort는 나누고 + 합치고 두 과정) ① 정렬할 데이터 준비 (오름차순 가정) 7 3 1 5 6 4 2 ② 본격적인 merge sort를 하기에 앞서서 각각 원소가 1개씩만 있게끔 recursive하게 array를 절반으로 쪼갠다 (recursion 적용) 7 3 1 | 5 6 4 2 → 7 | 3 1 | 5 6 | 4 2 → 7 | 3 | 1 | 5 | 6 | 4 | 2 ③-1) 두 개씩 쪼개는 루트의 역 방향으로 작은 원소를 앞에, 큰 원소를 뒤에 놓는다. (1) 3 1 에서 3 | 1로 쪼갰으므로 1 3으로 정렬 (2) 5 6 에서 5 | 6으로 .. Computer Science/Algorithms 2024. 4. 6.
★Implementation&Simluation Upper-Advanced I - 1 Solved★ ★ 19237 어른 상어 ★ import sys input=sys.stdin.readline from collections import deque N,M,k=map(int,input().split()) #NxNsize / M sharks / smell limit k trace=[] smell=[[0]*N for _ in range(N)] sharks=deque() shark_ds_priorities=[] #shark_ds dx,dy=['?',-1,1,0,0],['?',0,0,-1,1] num_of_sharks=M for i in range(N): l=list(map(int,input().split())) trace.append(l) for j in range(N): if l[j] != 0: sharks... BOJ/🥇 2024. 3. 3.
★Stack & Queue & Deque Advanced I - 1 Solved★ ★ 9935 문자열 폭발 ★ import sys input=sys.stdin.readline s=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 BOJ/🥇 2024. 2. 24.
🍡 Two Pointers intro 🍡 two pointers란 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 이중 for문으로 돌리면 i=0일때의 정보를 i=1일 때 전혀 쓰이지 않지만, two pointers는 i=0일 때의 작업이 i=1일 때의 작업에 쓰인다. 과거 정보를 기억한 채로 효율적이게 index를 O(N)으로 움직이는 알고리즘. 이분탐색 문제를 투포인터로도 풀 수 있는 경우가 많고, 그 반대도 많다. two pointers는 O(N)으로, 각각의 모든 case를 일일이 점검할 필요 없이, 일부 case는 점프하는 경우만 풀이가 가능. explanation 🍡 위와 같은 배열이 있다고 할 때, a일때 b~i를 돌고 / b일 때 c~i를 도는.. Computer Science/Algorithms 2024. 2. 11.
★Two-Pointers Advanced I - 7 Solved★ ★ 15961 회전 초밥 ★ import sys input=sys.stdin.readline from collections import defaultdict N,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 BOJ/🥇 2024. 2. 11.
★Two-Pointers Upper-Intermediate I - 5 Solved★ ★ 3273 두 수의 합 ★ import sys input=sys.stdin.readline n=int(input()) l=list(map(int,input().split())) X=int(input()) #array l.sort() #two-pointers x,y=0,n-1 ans=0 while x X y-=1 print(ans) 🍡 오름차순 정렬 뒤, x를 배열 왼쪽 끝 / y를 배열 오른쪽 끝에 배치. l[x]+l[y]가 X보다 클 경우, x를 아무리 오른쪽으로 이동해도 X보다 클 수 밖에 없음. 따라서 y를 왼쪽으로 이동 / l[x]+l[y]가 X라면 정답 찾음! ans+=1 한 뒤, l[x]와 l[y]는 이제 X 나오는 연산에 필요 없으므로 x 오른쪽 이동, y 왼쪽 이동 / l[x]+l[y]가.. BOJ/🥈 2024. 2. 11.
🦜 Pigeonhole Principle intro 🦜 총 19개의 구멍이 있는 비둘기집에서 20마리의 비둘기가 들어가려고 할 때, 적어도 한 곳의 비둘기집에는 적어도 2마리 이상의 비둘기가 반드시 있을 수 밖에 없다는 원리. ① theorem I: 각 구멍에 A마리의 비둘기가 평균적으로 들어가 있다면, A가 정수가 아니라면, 적어도 한 곳에는 ceil(A)마리의 비둘기가 있다는 뜻. 나머지 비둘기 집에는 최대 floor(A)마리의 비둘기가 있다. ② theorem II: n+1개의 물건을 n개의 상자에 넣으려고 할 때, 적어도 한 개 이상의 상자에는 2개 이상의 물건을 넣을 수 밖에 없다. 🦜 generalization ①) 만약 Kn+1마리의 비둘기가 n개의 비둘기집에 들어가려고 할 때, (Kn+1)/n은 K + 1/n이므로 적어도 한 곳의.. Computer Science/Algorithms 2024. 2. 2.
★Implementation&Simluation Advanced I - 5 Solved★ ★ 21610 마법사 상어와 비바라기 ★ import sys input=sys.stdin.readline from collections import deque N,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 moving dx,dy=[0,-1,-1,-1,0,1,1,1],[-1,-1,0,1,1,1,0,-1] for move in mo.. 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 sys input=sys.stdin.readline def 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='') else: #needs to be added for x in [' ','+','-']: if x == ' ': exp+=str(start) track(nums,exp,start+1) exp=exp[:-1.. BOJ/🥇 2024. 1. 21.
★Backtracking Upper-Intermediate I - 9 Solved★ ★ 15663 N과 M (9) ★ import sys input=sys.stdin.readline N,M=map(int,input().split()) nums=list(map(int,input().split())) nums.sort() num,visited=[],[False]*N def track(): if len(num)==M: print(*num) else: last=0 for i in range(len(nums)): if not visited[i] and last!=nums[i]: visited[i]=True num.append(nums[i]) last=nums[i] track() num.pop() visited[i]=False track() ★ 15664 N과 M (10) ★ import sys .. BOJ/🥈 2024. 1. 20.
★Backtracking Intermediate I - 10 Solved★ ★ 15649 N과 M (1) ★ N,M=map(int,input().split()) ans=[] def track(): if len(ans) == M: #completed print(*ans) else: for x in range(1,N+1): if len(ans) == 0 or x not in ans: ans.append(x) track() ans.pop() #backtrack track() 🙃 backtracking 포스팅 참조 ★ 15650 N과 M (2) ★ N,M=map(int,input().split()) ans=[] def track(): if len(ans) == M: #completed print(*ans) else: for x in range(1,N+1): if len(ans) == .. BOJ/🥈 2024. 1. 18.
🙃 Backtracking intro 🙃 backtracking이란, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. 구현력을 필요로 한다. 현재에서 나올 수 있는 모든 경우의 수를 모아 둔 decision space를 만들고, decision space의 각 부분마다 뻗어 나가며 그 다음으로 나오는 deicision space에서 계속해서 뻗어나가며 탐색. 만약 뻗어나간 결과 문제 상황에 맞지 않으면, 그 자리에서 중단하고 다시 뒤로 후퇴하면서 올라가 또 다른 경우의 수로 뻗어나가며 탐색. 🙃 즉, 요약하자면 재귀적으로 가능한 모든 case를 incrementally하게 탐색해나가면서 해당 문제 조건에 만족하지 않는 경우는 이전으로 돌아가(backtrack) 계속 솔루션을 찾는 기법(결론: 백트래킹은 그냥 .. Computer Science/Algorithms 2024. 1. 18.
👔 fashionMNIST Classifier before building a classification model ① check the version & load fashionMNIST data & load the training, test split of the fashionMNIST dataset : fashionMNIST dataset is a collection of grayscale 28x28 pixel clothing images. Each image is associated with a label as shown in this table import tensorflow as tf print(tf.__version__) #2.15.0 # Load the Fashion MNIST dataset fmnist = tf.keras.dataset.. Deep Learning/Experiments 2024. 1. 15.
🧿 Dijkstra's (Shortest Path) Algorithm intro 🧿 다익스트라 알고리즘이란 '방향 그래프 또는 무방향 그래프에서 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘'이다. 플로이드 알고리즘은 모든 정점 쌍 사이의 최단 거리를 일일이 구하는 알고리즘. 플로이드 알고리즘은 음수인 간선 존재는 괜찮지만 음수인 사이클이 있을 때만 문제이나, 다익스트라는 음수인 가중치를 가지는 간선이 있으면 아예 사용 불가능. 음수인 간선이 있다면 벨만포드 알고리즘 사용. 또한 정확한 최단거리가 아닌 근사치를 원할 경우 A* 알고리즘을 사용함. 다익스트라는 네트워크에서도 많이 사용. 🧿 일명 '최단 경로 알고리즘' 중 하나로, 최단 경로 문제 상황은 (1) 한 지점에서 다른 한 지점까지의 최단 경로 (2) 한 지점에서 다른 모든 지점까지의 최단 .. Computer Science/Algorithms 2024. 1. 14.
★Implementation&Simulation Upper-Intermediate I - 3 Solved★ ★ 2564 경비원 ★ import sys input=sys.stdin.readline w,h=map(int,input().split()) diameter = (w+h)*2 loc=[] ans=0 for _ in range(int(input())): d,l=map(int,input().split()) if d == 3: loc.append(l) elif d == 2: loc.append(l+h) elif d == 4: loc.append(h*2+w-l) else: #d==1 loc.append(h*2+w*2-l) d,l=map(int,input().split()) if d == 3: me = l elif d == 2: me = l+h elif d == 4: me = h*2+w-l else: #d==1 m.. BOJ/🥈 2024. 1. 8.
🥪Array & Linked List 1. Array 🥪 Array(배열)는 메모리 상에 원소를 연속하게 배치한 자료구조를 뜻한다. O(1)에 k번째 원소를 확인/변경 가능하다. 또한 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양(overhead)가 거의 없으며, 메모리 상에 데이터들이 붙어 있어서 cache hit rate가 높다. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸린다. ※ array에서의 cache hit rate가 높은 이유? : 데이터가 연속해서 배치되어 있으므로 cache 입장에서 array 내의 인근 데이터까지 cache block에 load 하므로 임의의 array 내의 원소 접근 시 인근 원소 역시 cache에 있을 확률이 높다. 그리고 반복적으로 동일한 array 내의 원소를 접근한다면 cac.. Computer Science/Data Structures 2024. 1. 8.
★LIS Expert(Easy) - 1 Solved★ ★ 14003 가장 긴 증가하는 부분 수열 5 ★ import sys input=sys.stdin.readline N=int(input()) A=list(map(int,input().split())) #binary search def binary_search(l, i, x): start,end=0,len(l)-1 while start BOJ/🏅 2024. 1. 7.
🍝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.
★LIS Upper-Advanced - 3 Solved★ 🥇 LIS 알고리즘이되, O(nlogn) 이내의 시간 복잡도만 통과 가능한 문제 정리 ★ 12015 가장 긴 증가하는 부분 수열 2 ★ import sys input=sys.stdin.readline N=int(input()) A=list(map(int,input().split())) #binary search def binary_search(l, x): start,end=0,len(l)-1 while start BOJ/🥇 2024. 1. 5.
★LIS Advanced - 6 Solved★ 🥇 일반적인 LIS 알고리즘 부터 정리 ★ 11053 가장 긴 증가하는 부분 수열 ★ import sys input=sys.stdin.readline N=int(input()) A=list(map(int,input().split())) dp=[1]*N for x in range(1,N): for y in range(x): if A[y] A[x]: dp[x] = max(dp[x], dp[y]+1) print(max(dp)) ★ 14002 가장 긴 증가하는 부분 수열 4 ★ import sys input=sys.stdin.readline N=int(input()) A=list(map(int,input().split())) dp=[[1,[A[i]]] for i in range(N)] for x in range.. 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.

티스토리툴바