All Good

전체 글307

🎢 Topology Sort intro🎢 위상 정렬 = 사이클이 없는 방향 그래프(DAG; Directed Acyclic Graph)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것→ 위상 정렬은 DAG에 대해서만 수행할 수 있다→ 여러 가지 답이 존재할 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우(문제에서 오름차순, 내림차순 명시 없다면) 여러 가지 위상정렬 노드 결과가 존재 가능→ 모든 원소를 방문하기 전에 queue가 빈다면 사이클이 존재한다고 판단 가능(사이클에 포함된 원소 중에서 어떠한 원소도 queue에 들어가지 못한다) (또는 queue에서 노드를 뽑을 때마다 뽑은 노드의 개수가 카운트 되어서, 최종 카운트 된 노드의 개수와 그래프 전체 노드의 개수가 같은 지 다른 지 비교로도 알.. Computer Science/Algorithms 2024. 10. 11.
★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.
➡️ Linked List intro➡️ Linked List(연결 리스트)는 배열이라는 자료구조와 비교하며 이해하면 쉽다. 연결 리스트는 배열과 달리 연속된 메모리 공간에 데이터를 저장하지 않고, 각 데이터가 다음 데이터의 위치를 가리키는 방식으로 저장한다. (선형 자료 구조). 이 때의 각 데이터 단위를 node라고 하고, node는 데이터를 저장하고, 다음 노드를 가리키는 참조(주소)를 포함한다. ➡️ 연결 리스트는 아래와 같은 3가지 특징이 존재한다.① 동적 크기: 배열과 달리 연결 리스트는 크기가 고정 x. 따라서 노드를 언제나 추가 / 삭제를 쉽게 할 수 있어 크기가 가변적.② 삽입 / 삭제 쉬움: 배열의 경우 삽입 / 삭제 연산을 진행할 때 해당 위치 이후의 모든 요소를 이동시켜야 하는 번거로움이 있으나, 연결 리스트.. Computer Science/Data Structures 2024. 9. 26.
🌉 Monotonic Stack intro🌉 stack의 (파이썬 코드 기준 append()와 pop()) 연산이 O(1)임을 감안해 한 곳에서 넣고 빼고를 반복하는 과정에서 stack의 원소가 오름차순 또는 내림차순을 유지하게끔 하는 stack을 만드는 유형을 'monotonic stack' 유형이라고 한다. 🌉 아래 예시와 같이 내림차순으로 이루어진 stack을 유지하면서, 새로운 원소 6이 들어올 때 pop() 연산 4번 진행 후 빠르게 append() 진행🌉 오름차순 또는 내림차순 순서 stack으로 업데이트 되는 과정에서 현재 원소보다 오른쪽 또는 왼쪽 원소 중 가장 가까이 있는 원소 최대/최솟값 구하기 또는 현재 원소보다 오른쪽 또는 왼쪽 원소 중 가장 가까이 있는 원소의 위치 구하기가 대표 유형으로 많이 나온다. 🌉.. Computer Science/Data Structures 2024. 9. 23.
🧑🏻‍💻 LeetCode Medium Collections I - 17 Problems 0300. Longest Increasing Subsequence / 0053. Maximum Subarrayclass Solution: def lengthOfLIS(self, nums: List[int]) -> int: length = len(nums) dp = [1]*length for x in range(1,length): for y in range(0,x): if nums[y] class Solution: def maxSubArray(self, nums: List[int]) -> int: ans,curmax=-10001,0 for i in range(len(nums)): .. LeetCode Problems/Medium 2024. 9. 9.
🫂 Prefix Sum 1D Prefix Sum✊🏻 구간 합 문제는 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 계산하는 문제 유형을 뜻한다. ✊🏻 예를 들면, 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정했을 때, 2번째 수부터 4번째 수까지의 합은 20 + 30 + 40인 90이 된다. ✊🏻 N개의 정수로 구성된 수열이 있고, M개의 query 정보가 주어진다. 각 query는 left와 right로 구성. 각 query에 대하여 [left, right] 구간에 포함된 데이터들의 합을 출력해야 한다. (수행 시간 제한은 O(N+M)) → 위 예와 접목하자면, 5개의 데이터 (N=5)로 구성된 수열에서 매번 새로운 query 구간마다 해당 합을 구한다면 시.. Computer Science/Algorithms 2024. 9. 6.
😍 LeetCode Easy Collections II - 14 Problems 0283. Move Zeroes / 0344. Reverse Stringclass Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ length=len(nums) if length != 1: first_encountered = False for x in range(length-1): if nums[x] == 0: if not first_encountered: .. LeetCode Problems/Easy 2024. 9. 2.
★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.
😊 LeetCode Easy Collections I - 20 Problems 0001. Two Sum / 0268. Missing Numberclass Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dct = dict() for i in range(len(nums)): dct[nums[i]] = i for i in range(len(nums)): if (target-nums[i]) in dct: if i!=dct[target-nums[i]]: return [i,dct[target-nums[i]]]class Solution: def missingNumber.. LeetCode Problems/Easy 2024. 8. 5.
👔 Tuning fashionMNIST Classifier I: Adjusting the Number of epochs 👔 유명한 fashionMNIST Classifier에 Convolution과 Pooling을 적용한 후 성능 증가를 직접 경험해보았다. 이제 다양한 model tuning과 epochs를 조절하면서 소폭의 성능 증가에 기여할 수 있는 지 알아보도록 해보자! 👔 모든 코드는 GitHub 클릭! 👔 default fashionMNIST Classifier 모델: 2개 연산 → Flatten() → Dense(128, relu) → Dense(10, softmax)① Adjusting the Number of Epochs👔 epochs란 주어진 batch_size에 맞는 여러 batch를 미리 만들고 난 후, 동일 batch training을 반복적으로 몇 번 수행하는 가이다. 예를 들어 5 epo.. Deep Learning/Experiments 2024. 8. 2.
🎊Binary Heap 🎊 intro🎊 Priority Queue와 연결지어 설명할 수 있는 Binary Heap data structure에 대해 자세히 알아보자. 앞서 학습한 Priority Queue는 일종의 Abstract Data Structure(ADT)로, binary heap을 추상화한 개념이라 볼 수 있다. 즉, 실제 priority queue는 binary heap이라 생각하면 된다. priority queue의 우선순위가 최대 먼저, 또는 최소 먼저라면 binary heap으로 tree structure를 만들어 tree structure에서 우선순위에 맞게 꺼내준다. 최대 먼저라면 max-heap, 최소 먼저라면 min-heap이라 부른다. (여기서 priority queue는 무조건 binary he.. Computer Science/Data Structures 2024. 7. 17.
★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.
🍣 Fibonacci Sequence 🍣 유명하고 유명한 피보나치 수열(Fibonacci Sequence)은 아래와 같이 표현할 수 있다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ...① Recursive Definition🍣 즉, Fn을 n번째 피보나치 수라고 한다면 재귀 방식으로 Fn을 아래와 같이 표현할 수 있다. F(n) = F(n-1) + F(n-2)with initial conditions F(0) = 0 and F(1) = 1 : 즉, Fn을 구할 때 Fn-1과 Fn-2를 사용해 재귀적 호출로 Fn을 정의할 수 있다. Fn을 재귀적으로 구하는 알고리즘의 시간복잡도는 O(2^n). Fn 호출에 동일 재귀함수 .. Computer Science/Algorithms 2024. 6. 26.
★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.
📲 Divide&Conquer * intro🍻 분할(Divide)하고 정복(Conquer)하는 알고리즘은 분할 → 정복 → 결합 크게 세 단계로 진행 🍻① 분할(Divide): 주어진 문제를 더 작은 여러 개의 sub-problem으로 분할한다.② 정복(Conquer): 재귀적으로 sub-problem들을 각각 해결한다. 문제들을 각각 독립적으로 해결. ③ 결합(Combine): 각각의 sub-problem 해결 결과를 묶어 전체 문제의 최종 솔루션을 도출! 🍻 큰 problem을 여러 개의 sub-problem으로 나누는 과정에서 recursion 재귀가 사용된다. 분할을 재귀로 구현하면서 나누고 더 이상 나눌 수 없는 sub-problem 각각 conquer(정복)한 다음 각 sub-problem별 conquer된 결과를 c.. Computer Science/Algorithms 2024. 6. 8.
🚀 Power by Divide and Conquer intro🅰️ 분할정복(divide & conquer)은 복잡한 문제를 해결할 수 있는 여러 쉬운 문제들로 쪼개서 해결하는 접근법. 정수의 거듭제곱을 구하는 과정에서 분할정복 기법을 활용해 더 효율적인 시간 내에 진행할 수 있다. '실수 a와 음이 아닌 정수 x에 대해 a^x를 구하는 문제'① x = 1이면 답은 a로 직접 해결→ 시간복잡도 O(1) ②  x > 1이면 sub-problems로 쪼개기.🅰️ x가 짝수라면 a^(x/2) x a^(x/2)🅰️ x가 홀수라면 a^((x-1)/2) x a^ ((x-1)/2) x a→ 시간복잡도 T(x) = T(x/2) + O(1). 즉 T(x) = O(logx)example 7^10🅰️ 예를 들어 7^10을 구하는 문제가 있다고 하자. 두 가지 접근법으로.. Computer Science/Algorithms 2024. 6. 6.
Scalar & Vector 1. Scalar"단순히 변수로 저장되어 있는 숫자" ① vector 혹은 matrices에 곱해지는 경우 해당 값에 곱한 값으로 결정 ② 단일숫자 ③ 변수에 저장 시 소문자를 이용하여 표기 ④ 실수 & 정수 모두 가능 ⑤ 벡터의 크기를 맘대로 늘이는 걸 scaling한다고 해서 이 때 측정되는 크기를 scalar 라고 한다2. Vectorintro① 파이썬에서 주로 list로 사용된다. 숫자를 원소로 가지는 list 또는 array ② 아래 그림에서 벡터 x는 행벡터, xT는 열벡터 ③ 파이썬에서는 코드로 아래와 같이 벡터를 표현할 수 있다. list 또는 np array로 여러 원소가 순서를 갖는 모음으로 표현 가능하다.x = [1, 7, 2]x = np.array([1, 7, 2]) ④ 벡터에 있는.. Math & Linear Algebra/Concepts 2024. 6. 3.
👔Improving fashionMNIST Classifier using Convolutions 👔 앞서 만들었던 DNN fashionMNIST Classifier의 정확도를 Convolution & Pooling을 사용해서 높이려 한다 👔 fashionMNIST Classifierbefore 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 withsh-avid-learner.tistory.com① load the .. Deep Learning/Experiments 2024. 6. 2.
map & applymap & apply(for dataframe & Series) 1. apply🔺 pandas.DataFrame.apply 🔻(apply for dataframe)docuDataFrame.apply(func, axis=0, raw=False, result_type=None, args=(), **kwargs) "Apply a function along an axis of the DataFrame. Objects passed to the function are Series objects whose index is either the DataFrame’s index (axis=0) or the DataFrame’s columns (axis=1). By default (result_type=None), the final return type is inferred from.. Python/Pandas&Numpy 2024. 6. 2.
★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.
🛣️ Shortest Path in an Unweighted Graph intro🛣️ 그래프에서 최단거리를 구하는 알고리즘은 여러가지가 있다. 다익스트라, 플로이드-워셜, 벨만-포드와 같은 유명한 최단거리 TOP 3 알고리즘이 존재하는데, 간선의 가중치가 전혀 없는, 주어진 일반적인 그래프에서의 최단 거리를 구하는 방법은 BFS가 best. 이번 포스팅을 통해 주어진 그래프에서 BFS를 사용해 최단거리 구하기와 최단거리 내용 출력까지 알아본다.DFS는 안되고 BFS는 가능한 이유?🛣️ 그래프 순회의 대표적인 2가지 방법으로는 DFS, BFS가 있다. 그러나 shortest path in an unweighted graph를 찾기 위해서는 DFS보다는 BFS 방식을 적극 권장. 접근 방식에 차이가 있기 때문이다. : BFS의 경우 level-wise exploration .. Computer Science/Algorithms 2024. 5. 23.
⛆ Flood Fill intro⛆ 플러드 필(Flood Fill) 알고리즘 이란, 주어진 2차원 그래프에서 연결영역의 개수 및, 각 연결영역의 연결 노드 개수를 구하는 알고리즘이다. 즉, 플러드 필은 DFS / BFS 그래프 순회 알고리즘을 응용한 알고리즘으로, 주어진 2차원 배열에서 연결 영역 관련 문제를 풀 때 사용된다.  ⛆ 대표적인 케이스로, 연결 영역 개수 구하기, 가장 큰 영역 면적 구하기, 각 연결 영역 내의 노드 개수 구하기 등등이 나온다. ⛆ 시간 복잡도는 traverse할 2차원 그래프의 행 개수가 N이고 열 개수가 M이라면 O(NM), 공간 복잡도는 O(NM)이다.  1. 연결 영역 개수 구하기ex) BOJ 4963 S2 Q. 1과 0으로만 이루어진 2d array에서 1로만 이루어진 연결 영역, 즉 섬의.. Computer Science/Algorithms 2024. 5. 19.
★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.
🌸Model Analysis - Convolution / number of Pooling params + shape size ① case 1# Define the modelmodel = tf.keras.models.Sequential([ # Add convolutions and max pooling tf.keras.layers.Conv2D(32, (3,3), activation='relu', input_shape=(28, 28, 1)), tf.keras.layers.MaxPooling2D(2, 2), tf.keras.layers.Conv2D(32, (3,3), activation='relu'), tf.keras.layers.MaxPooling2D(2,2), # Add the same layers as before .. Deep Learning/Fundamentals 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.

티스토리툴바