걸음마코딩기

[C++] 18185. 라면사기

https://www.acmicpc.net/problem/18185 처음에는 단순한 그리디 문제라고 생각해서, 3번방법을 최우선으로 문제를 풀었다가 완전히 막혀버렸다계속 고민하다가 찾아보니, 반례가 있다더라반례 케이스를 설명해보자면, 3번 방법을 사용할 수 있는 상태인데, i+2보다 i+1이 더 큰 경우이다 예시A[4] = 1 2 1 1 3번 방법 우선시A[0], A[1], A[2] -> 7A[1], A[3]이 1씩 남으므로 -> 3 * 2 = 6==> 7 + 6 = 132번 방법 우선시A[0], A[1] -> 5A[1], A[2], A[3] -> 7==> 5 + 7 = 12이렇게 반례가 생겨버린다.. 안 찾아봤으면 절대 몰랐을듯.. 아무튼, 이 반례를 적용해주려면 i+2랑 i+1 크기 비교하고, i+..

머신러닝 데이터를 다루다 보면 너무 많은 변수들을 다룰 때가 있다. 이 변수들을 전부 머신러닝에 학습시킨다면 오히려 예측에 혼선을 주는 변수가 있을 수도 있고, 학습속도 또한 느려질 것이다. 따라서 타겟 예측에 유의미하게 사용될 수 있는 변수들을 선택해줘야할 것이다. 하지만, 당최 변수들을 쳐다봐도 이 변수가 예측에 유의미할까를 판단하는 것은 쉽지않은 것 같다. 이때 변수의 중요도를 보고 선택하는 방법을 사용한다 변수의 중요도를 보는 방법은 여러가지이지만, 이번 포스팅에서는 RFE와 REFCV에 대해 알아보고자 한다. RFE (Recursive Feature Elimination) : 변수 선택 방법으로, 원하는 개수의 변수들이 남을 때까지 학습을 반복하며 유의미하지 않은 변수들을 제거해 나가는 Back..

map을 이용하면 쉽게 풀리는 구현문제이다. string 입력에서 어떻게 해야할지만 안다면 바로 풀린다. 문자열 일부를 return하는 substr함수를 이용해서 '.' 다음 글자부터 끝까지 return받는다. 그렇게 받은 값을 맵에 저장한다. (default가 오름차순이므로) #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; map m; for(int i=0; i> t; string extension = t.substr(t.find('.')+1); m[extension]++; } for(auto x : m) cout

아.. 인덱스가 너무 헷갈리고 회전 레이어 다루는게 어려워서 어려운 문제가 아니었는데도 좀 고전했다.. 다시 풀어봐야할 것 같다ㅜㅠ (확실히 구현에 좀 약한듯..) 우선, 회전 레이어 갯수는 N 또는 M 중 작은 값을 2로 나눈 값과 같다. 시작점은 (0,0), (1,1) ...로 되므로 이를 이용하여 시작점을 잡아주면 된다. 우선, 회전하는 방법을 잘 생각해야 하는데, 시작점을 0,0으로 잡았기 때문에 이를 temp 변수에 넣어주고 시작점부터 채워주기 시작한다. [ 시작점부터 채우는 방향 ] 맨 윗줄 : 오 -> 왼 방향으로 채워준다 가장 오른쪽 열 : 아래 -> 위 방향으로 채워준다 맨 아랫줄 : 왼 -> 오 방향으로 채워준다 가장 왼쪽 열 : 위 -> 아래 방향으로 채워준다. 이 과정을 각 레이어마..

이번 문제는 bfs문제이다. 백준의 토마토와 비슷한 문제이다. 토마토도 괜찮은 문제이니 한번 풀어보길 추천한다! -> 토마토 문제 바로가기 전체 영토 중 방문하지 않은 영토부터 차례대로 순회를 시작한다. 큐에 넣어놓고 주변 영토(상하좌우)를 방문해보며 연합이 될 수 있는지 조건을 체크한다. 연합이 될 수 있으면 bfs용 큐와 연합들을 저장할 벡터에 저장해주고 총합을 더해준다. (나중에 인구수 조정을 위함) 연합이 만들어졌다면 (2개이상) 인구수를 조정해준다. 두번째 for루프에서 방문을 검사하는 코드, 즉 bfs를 실행하는 코드는 같은 날 다른 연합을 또 만들어야하므로 연합을 저장해주는 벡터를 초기화해준다. 두개의 for루프가 끝나고 연합이 아직 남아있다면 days를 증가시켜주고 위 과정을 연합이 만들어..

오랜만에 string 문제를 들고와봤다. 문제는 쉬운편인데, 나는 진짜 단순하게 풀었다. 조금 더 생각하면 깔끔한 코드가 나올 것 같기도 한데, 일단 queue에 무지성으로 때려박고 tag와 단어, 공백 3가지 유형으로 넣어주었다. 출력할때는 단어인 경우에만 reverse를 이용해서 출력해주었다. #include #include #include using namespace std; /* a-z, 0-9, ,(두개 개수 같음) 태그 말고 단어만 뒤집어서 출력 태그는 안으로 길이는 3이상, 공백 포함가능 태그와 단어사이에는 공백 없음 --- // inputs string tag; string words; queue q; if (input starts '') { tag += input; } q.p..

오랜만에 문제 풀기~ 처음에는 큐를 이용해서 문제를 풀까 생각했는데, 더 간단하게 풀릴것같아서 단순 구현으로 풀었다. 어차피 days는 계속 누적되고, cnt만 배포될때마다 확인 후 reset시켜주면 되는거라 while문으로 progress + speed * days가 100 넘을때까지 days를 누적시켜주고, 이후 배포되는 친구들을 위해 cnt가 0이 아닐 때, answer에다가 push해준다. 마지막 값이 누락되는 것을 방지하고자, 루프를 다 돌고 나왔을 때 cnt가 0이 아니면 answer에 push 해준다. #include #include using namespace std; vector solution(vector progresses, vector speeds) { vector answer; i..

이전 포스팅에 이어 RMSProp과 Adam에 대해 계속해서 알아보겠다!📌 Gradient Descent Algorithm이란?📌 Batch gradient descent에 대해서--- momentum 이용1️⃣ Momentum2️⃣ Nesterov Momentum--- learning rate 이용3️⃣ AdaGrad(NEW!) 지수가중이동평균이란?4️⃣ RMSProp5️⃣ Adam  RMSProp를 알기 이전에 "지수가중이동평균"에 대해 알아야한다. 💡 지수가중이동평균이란? 이전의 값과 현재의 값에 다른 가중치 (두 가중치의 합은 1)를 주는 방식이다. 이 식에서 β가 Hyper parameter이고, 보통 0.9를 사용한다.β=0.9일때, 이전값(최근값들)인 Vt-1에..

이번 포스팅에서는 경사하강법이 무엇인가에 대한 것과 Optimizer의 여러 종류들에 대해 알아보고자 한다.목차는 대충 아래와 같다.📌 Gradient Descent Algorithm이란?📌 Batch gradient descent에 대해서--- momentum 이용1️⃣ Momentum2️⃣ Nesterov Momentum--- learning rate 이용3️⃣ AdaGrad4️⃣ RMSProp5️⃣ Adam  📌 Gradient Descent Algorithm먼저 경사하강 알고리즘이란 함수의 변화도가 가장 큰 방향으로 이동하고자 하는 알고리즘으로,목적함수 J가 있을 때, 이 값을 최소화 하는 θ를 구하는 알고리즘이다.( 여기서 θ는 learnable parameter이고, α..

이번 포스팅에서는 한번쯤은 들어봤을 법한 차원의 저주(Curse of Dimention)와 차원축소 방법들에 대해서 알아보겠다. 차원의 저주란? 간단히 말해 데이터의 차원이 증가할수록 모델의 성능이 저하되는 현상이다. 단순히 데이터 변수의 수가 증가하는 것이 아닌, 관측치 수보다 변수의 수가 많아지는 상황을 말한다. 차원의 저주가 그래서 정확히 뭘 말하는 걸까? 예를 들어, 1차원 데이터에 5개의 샘플이 있을 때, 이때 하나의 샘플은 전체 데이터에서 1/5의 밀집도를 가질 것이다. 여기서 만약 데이터가 2차원일때 하나의 샘플은 5*5 전체에서 1/25의 밀집도를 가지게 된다. 데이터가 3차원이라면? 하나의 샘플은 1/125의 밀집도를 가질것이다. 즉, 차원이 증가할수록 데이터의 밀집도는 줄어들고, 빈공간..