본문 바로가기

컴퓨터공학 & 정보통신84

[알고리즘/기초] 피보나치 수 알고리즘의 기초 이론 중 하나인 피보나치 수에 대하여 간단하게 기록한 글입니다. 정의 피보나치 수는 첫째 항, 둘째 항이 1이고 N번째 항이(N>=2) 직전 두 항의 합을 값으로 가지는 수열입니다. 1. 연습 문제 기본적인 피보나치 수 관련 문제입니다. 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 1-1. 방법 (시간 초과) 재귀적인 방식으로 솔루션을 작성할 수 있습니다. 허나 이 방식으로는 연습 문제를 해결할 수 없습니다. 연습 문제의 시간 제한이 1초이기 때문입니다. #.. 2023. 8. 5.
[백준] 1463 1로 만들기 요약 처음에 2차원 배열로 풀이를 작성하였지만 시간초과였습니다. 1차원 배열의 Bottom-UP 방식의 배열을 1회 순회하는 코드를 작성하여 문제를 해결하였습니다. 이전 단계에서의 최솟값을 어떠한 값을 기준으로 해야 하는 지 아는 것이 문제의 핵심으로 보입니다. 제가 이전에 풀었던 설탕 배달 문제와 유형이 동일합니다. 솔루션 python3 으로 솔루션을 작성하였습니다. def getMin(n): ''' e.g n==10일때 0 1 2 3 4 5 6 7 8 9 10 0 0 1 2 3 ''' dp = [0 for _ in range(n+1)] dp[1] = 0 for index, value in enumerate(dp): if index == 0 or index == n: continue if index+1 2023. 7. 7.
[백준] 2839 설탕 배달 요약 DP bottom-up 방식으로 문제를 풀면 됩니다. 기존 존재하는 값과의 비교를 통해 최솟값을 갱신하는 구조, 문제 풀이에는 크게 문제가 없었지만 index out of range 에러를 방지하기 위한 N 과 i+3, i+5 과의 비교 식을 잘못 작성하였었습니다. 솔루션 def getMinCount(N): dp = [-1 for _ in range(N+1)] if N >= 3: dp[3] = 1 if N >= 5: dp[5] = 1 for i, v in enumerate(dp): if v == -1: continue if N >= i+3: if dp[i+3] == -1 or v+1 = i+5: if dp[i+5] == -1 or v+1 < d.. 2023. 7. 2.
[머신러닝] Unsupervised Learning input만 주어지고, 이에 대한 기조를 스스로 찾아가는 학습 방식 PCA (Principal Component Analysis) 앞서 차원 축소에도 활용했던 기법으로 비지도학습에도 응용됨 각 Z1, Z2, Z3... 는 서로 상호 연관성이 없음 적절한 갯수의 주성분 분석을 통해 적절한 군집을 진행해야 (ex. US Arrest 에서 Rape, Assault, Murder는 PC1 에 연관 UrbanPop은 PC2와 연관) 이때, Elbow method 사용 (가장 PVE 급감 시점을 사용) K-means Clustering homogeneous subgroup을 우리가 선택한 K 만큼 분류하는 것, 좋은 clustering은 군집 내 변동성이 최소인 것 모두가 적어도 하나의 군집에 포함 non-over.. 2023. 6. 12.
[머신러닝] Model Selection Model Selection Problem 데이터의 갯수 n이 predictor p의 갯수와 비슷한 경우 Least Square 는 무용 -> p의 갯수를 의도적으로 줄일 필요가 있음 (불필요한 복잡성 및 true relationship 잘 보이게) Subset Selection 모든 경우의 수 다 해보기(O(2^p) : exponential) -> 비효율적 greedy 정책 활용(O(p^2) : polynomial) forward stepwise : p 없 -> p 추가 backward stepwise : p 풀 -> p 제거 이때, RSS 및 R square는 p의 갯수가 많을 수록 계속 감소 -> 적절한 p의 갯수를 찾을 수 없음 이를 대처하기 위한 다양한 수치식 존재 Cp, AIC, BIC = 작.. 2023. 6. 12.
[머신러닝] Resampling Resampling Test 데이터가 현저히 부족, 접근에 제한 있음 -> train 데이터에서 다양한 방법으로 리샘플링하는 것이 현명함, CV와 Bootstraping 두가지 방법이 있음 Cross-Validation validation set = subset of TRAIN DATA ===> test error rate의 추정치를 뽑을 수 있음 다양한 split 방식이 존재 Randomly Split 무작위로 절반 validation set, 절반 training set 장점 : 간단 단점 : high variability MSE (무작위로 split 하므로 변동성 높음), sample 적음 (절반을 validation set 으로 사용하므로) LOOCV (Leave One Out Cross Vali.. 2023. 6. 12.

티스토리툴바