All Good

전체 글 - Table of Contents332

★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.

티스토리툴바