분류 전체보기 (49) 썸네일형 리스트형 4386 별자리 만들기 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 전형적인 Minimum Spanning Tree 문제이다. 입력으로 별의 x, y 좌표를 받아서 Complete Graph가 되도록 모든 별들 사이의 간선을 만들어준다. 그리고 이제부턴 크루스칼 알고리즘을 적용해서 간선을 정렬해서 최소 비용의 간선부터 루프를 생성하지 않으면 선택하는 식으로 풀면 된다. 간단한 문제였는데, 오랜만에 풀다 보니 사소한 데서 에러가 좀 있었다. 그리고 코드도 좀 더럽게 짠 거 같기도 하고... 꾸준히 풀어야 겠다. C++ 더보기 #in.. EECS 498-007 / 598-005 Lecture 5 : Neural Networks 강의 링크 https://www.youtube.com/watch?v=g6InpdhUblE&list=PL5-TkQAfAZFbzxjBHtzdVCWE0Zbhomg7r&index=5 강의 슬라이드 https://web.eecs.umich.edu/~justincj/slides/eecs498/498_FA2019_lecture05.pdf Linear Classifier는 간단한만큼, Geometric Viewpoint나 Visual Viewpoint에서 확인할 수 있듯이, 한계가 많다. 이러한 한계는 Feature Transform으로 어느 정도 극복이 가능하지만, 현실적으로 고차원의 데이터를 적절히 Feature Transform 하기 위해서는 고려해야 할 것이 한 둘이 아니다. 그래도 Feature Transfo.. 2624 동전 바꿔주기 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 전형적인 DP 문제이다. 이차원 배열 dp를 만들고 dp[i][j]에는 i번째 동전까지 사용했을 때, j원을 만들 수 있는 가능한 경우의 수를 저장하는 방식으로 해결했다. C++ 더보기 #include #include using namespace std; int cnt, k; int main(void) { cin.tie(nullptr); ios_base::sync_with_stdio(false); int t; cin >> t >> k; vecto.. 1707 Maximum XOR With an Element From Array 이번 문제는 Trie 구조를 이용해서 푸는 문제인데, Trie로 푸는 알고리즘 문제는 처음이었고, 그래서 풀 때, 시간이 좀 걸렸었다. 문제는 nums 배열에서 Queries 배열의 각 query의 두 번째 원소보다 같거나 작은 원소들과 첫 번째 원소와 XOR 연산을 했을 때의 최댓값을 찾는 문제이다. 어떠한 수 n과 임의의 수에 대해 XOR연산을 할 때, 만약 임의의 수가 5(101)와 4(100)라면, 공통되는 부분인 10의 계산 결과를 저장할 수만 있다면, 2번 계산하지 않아도 될 것이다. 이 문제에서는 XOR연산의 이러한 점을 이용하여 비트 레벨에서 Trie구조를 만들어 문제를 풀 것이다. 일단 우리가 짤 Trie는 root가 상위 비트, child가 하위 비트인 Trie이다. 그래서 querie.. 1706 Where Will the Ball Fall 이 문제도 조금 색다르긴 한데 어쨌든 전형적인 DFS 문제이다. C++ 더보기 class Solution { public: vector findBall(vector& grid) { vector res(grid[0].size()); for(size_t i = 0; i < res.size(); ++i){ size_t j = i, s = 0; while(res[i] == 0 && s < grid.size()){ if(grid[s][j] == 1){ if (j == res.size() - 1 || grid[s][j + 1] == -1) res[i] = -1; else{ ++j; ++s; } } else if (grid[s][j] == -1){ if (j == 0 || grid[s][j - 1] == 1) res.. 1705 Maximum Number of Eaten Apples 이 문제는 먼저 썩는 사과 먼저 먹어야 하는 전형적인 우선순위 큐 문제이다. C++ 더보기 class Solution { public: int eatenApples(vector& apples, vector& days) { using mypair = pair; priority_queue pq; int cnt{}; size_t i; for(i = 0; i < apples.size() || !pq.empty(); ++i){ while(!pq.empty() && pq.top().first 0) pq.push(top); } else{ int offset = min(top.first - int(i), top.second); cnt += offset; i += offset - 1; } } } return cnt; }.. 1704 Determine if String Halves Are Alike 이 문제는 주어진 문자열을 이등분한 후, 각 문자열에 포함된 모음의 수가 같으면 true를 반환하는 문제다 별다른 거 할 필요 없이 문제 그대로 구현하면 된다. C++ 더보기 class Solution { public: bool halvesAreAlike(string s) { map score; score['a'] = 1; score['e'] = 1; score['i'] = 1; score['o'] = 1; score['u'] = 1; score['A'] = 1; score['E'] = 1; score['I'] = 1; score['O'] = 1; score['U'] = 1; int a = 0, b = 0; for(size_t i = 0; i < s.length() / 2; ++i) a += score[.. EECS 498-007 / 598-005 Lecture 4 : Optimization 강의 링크 https://www.youtube.com/watch?v=YnQJTfbwBM8&list=PL5-TkQAfAZFbzxjBHtzdVCWE0Zbhomg7r&index=4 강의 슬라이드 https://web.eecs.umich.edu/~justincj/slides/eecs498/498_FA2019_lecture04.pdf Optimization은 Loss를 최소화하는 W를 찾는 것으로 것으로 이 과정은 사람이 고지대에서 저지대로 가는 길을 찾는 것과 유사하다. Linear regression 등의 간단한 모델에서는 간단한 미분을 통해 최소 Loss를 가지는 W를 찾을 수 있지만, 복잡한 모델에서는 Linear regression이 가지는 것과 같은 명료한 공식을 통해 최적의 W를 찾기란 매우 어려운 .. 이전 1 2 3 4 5 6 7 다음
