본문 바로가기

분류 전체보기

 (49)
2056 작업 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net DP와 DFS를 활용하여 해결했다. 각 작업을 노드로, 그리고 각 작업과 선행작업을 방향이 있는 간선으로 연결했다. 그래프를 구성한 다음에는 각 노드에 연결된 선행 작업들을 DFS 방식으로 순회하며 최대 작업 시간을 가진 노드를 찾고, 그 노드의 작업시간과 해당 노드의 수행 시간을 더해 작업시간으로 정했다. 그리고 이 과정에서 각 노드의 작업시간을 구하면 메모리제이션을 이용하여 한번만 찾도록 했다. 이 과정을 수행하면서 모든 작업을 완료하기 위한 최소 ..
EECS 498-007 / 598-005 Assignment #3-2 Assignment #3-1의 Fully Connected Network에 이어서 이제는 Convolutional Neural Network와 Batch Noramlization을 다룬다. 더보기 class Conv(object): @staticmethod def forward(x, w, b, conv_param): """ A naive implementation of the forward pass for a convolutional layer. The input consists of N data points, each with C channels, height H and width W. We convolve each input with F different filters, where each filte..
EECS 498-007 / 598-005 Assignment #3-1 드디어 미루고 미뤘던 Assignment # 3이다. 우선 Computational Graph에서 gradient를 계산하는 일종의 공식으로 쓰일 수 있는 각종 게이트부터 외우고 시작하자. 앞으로 과제 진행할 때 매우 매우 유용할 것이다. Assignment # 3는 먼저 Fully-Connected Neural Network와 Dropout을 구현하는 것부터 시작된다. 일단 Linear 레이어에서의 forward와 backward부터 구현하는데 더보기 @staticmethod def forward(x, w, b): """ Computes the forward pass for an linear (fully-connected) layer. The input x has shape (N, d_1, ..., d..
EECS 498-007 / 598-005 Lecture 10 : Training Neural Networks (Part 1) 강의 링크 https://www.youtube.com/watch?v=lGbQlr1Ts7w&list=PL5-TkQAfAZFbzxjBHtzdVCWE0Zbhomg7r&index=10 강의 슬라이드 https://web.eecs.umich.edu/~justincj/slides/eecs498/498_FA2019_lecture10.pdf 이번 시간부터는 신경망을 제대로 학습시키기 위해 해야 할 것들에 대해 알아볼 것인데, 이번 시간에는 위 3 가지 사항 중, 첫 번째 것만 강의하고 나머지 2개는 다음 강의에서 강의할 것이다. Activation Function은 신경망에 Non-Linearity를 추가해주는 매우 중요한 역할을 수행하는데 Activation Function으로는 여러 가지를 사용할 수 있다. 먼저 ..
1987 알파벳 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 전형적인 DFS 문제이다. 리트코드에서 DFS 사용하는 문제랑 비교도 할 수 없을 정도로 단순하게 입력받아서 DFS 돌리면 된다. 그런데 이거 의외로 시간 복잡도가 빡빡해서 DFS 내부적으로 쓰이는 연산은 가벼운 걸로 수행해야 했었다. 그냥 아무 생각 없이 map 사용하고, 매번 map 복사하니까 바로 시간 초과가 났다... 그래서 그냥 배열 써버리고 재사용하니까 여유롭게 통과됐다. C++ 더보기 #include using namespace std; in..
1806 부분합 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 배열의 연속된 부분합 중, 합이 S 이상이 되는 가장 짧은 부분의 길이를 구하는 문제이다. 일단 분류는 투 포인터로 되어있는데 난 그냥 이진 탐색 써서 풀었다. 먼저 각 구간의 누적합을 계산한 다음, 배열의 첫번째 위치부터 n - 1번째 위치를 구간의 시작점으로 두고, 구간의 끝점은 이진 탐색으로 찾았는데, 끝점이 될 수 있는 left bound는 lbound, right bound는 rbound로 정하고 lbound와 rbound 사이의 거리를 ..
1721 Swapping Nodes in a Linked List 링크드 리스트에서 두 개의 노드를 교체하는 것을 구현하는 문제이다. 리스트의 앞에서 k번째, 뒤에서 k번째의 노드를 교체해야 하는데, 리스트의 맨 앞에서부터 리스트를 순회하면서 앞에서 k번째, 뒤에서 k번째 노드의 포인터를 저장하고, 각 포인터에 저장된 값을 교환하는 식으로 구현하였다. C++ 더보기 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next)..
1720 Decode XORed Array encode 배열의 N번째 원소와 decode 배열의 N - 1번째 원소와 XOR 연산을 수행해 encoded 배열의 N번째 원소를 만들어 주면 된다. 전에 XOR 연산과 Trie 이용해서 푸는 1707 때문에 살짝 트라우마 왔었는데, 생각할 거리도 없이 무척 간단하게 풀었다. 더보기 class Solution { public: vector decode(vector& encoded, int first) { vector res; res.push_back(first); int i = 0; for(auto v : encoded) res.push_back(v ^ res[i++]); return res; } }; 더보기 class Solution: def decode(self, encoded: List[int],..
728x90

티스토리툴바