CS STUDY

https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 이 문제는 딕셔너리에 대해서 좀더 명확하게 이해할수 있게 만들어준 문제이다. 딕셔너리를 만든후 딕셔너리 구조를 d[key]: [단어개수, 단어길이, 단어] 로 구성한다 1. 정렬 파이썬의 sort및 sorted 함수는 key 인자 값으로 정렬에 있어서 우선 순위 기준을 설정 할 수 있다. sort(key= lambda x: (기준..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 간단해 보이지만 간단히 완전탐색으로 풀면 시간복잡도가 최악의 경우 n! 이 되기때문에 스택을 써야한다 또한 인덱스를 저장해야하기 때문에 스택안에 리스트가 들어가는 구조로 풀어줘야 한다. import sys N=int(sys.stdin.readline()) tower=list(map(int,sys.stdin.readline().split())) stack=[] ans=[] for i in rang..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 이 문제는 BFS 문제이긴 하지만 한가지 조건이 있다. 바로 graph에서 1(벽)인 부분을 깨고 진행할 수 있다는 점이다. 그러므로 visited 배열을 잘 사용해야 하는데 최단거리를 저장하는것이 아닌 1이 만났을때만 count를 올려주는 방법이 좋다. 또한 graph 내에서 0들만 먼저 탐색할 수 있도록(벽을 최소한 부신다고 했다) appendleft 함수를 사용해서 탐색..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net DFS를 사용해 트리를 추적하는 문제이다. 먼저 말단 노드까지 도착한 뒤 올라오면서 왼쪽 오른쪽 자식 노드들의 길이와 합을 구한다. 트리의 지름은 무조건 왼쪽 최장경로 + 오른쪽 최장경로 이다. DFS로 리프 노드까지 내려간 뒤 해당 노드의 가중치를 리턴한다.그리고 자식 노드가 있는 부모 노드부터는 자식들의 경로들 중 가장 큰 두 길이를 선택한다.두 길이를 더한 것은 현재 노드..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 처음에 숫자를 일일히 써가면서 규칙을 찾는데 엄청 고생했는데 다음과 같이 풀이하는 방법이 더 효율적이다. 위 표는 마지막 자리 숫자가 무엇일때 생성될수 있는 가지수를 적어놓은 것이다. 예를 들어 dp[2][1]은 21 이렇게 하나밖에 존재 하지 않고 dp[2][3]은 23,43 두개가 존재한다. 위처럼 작성해 놓으니 규칙을 쉽게 발견할수 있는데 빨간 화살표처럼 왼쪽 오른쪽 대각선 원소의 합이다. 생각해보면 당연한게 5가 맨 뒷자리에 오려면 앞에 4나 6이 와야 하기 때문에 4나 6이 오는 경우의 수를 모두 합해..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 이러한 유형의 문제는 가능한 조건을 미리 정리해놓고 풀이하는게 더 좋은 방법인것 같다. 특히 첫번째 부터 규칙을 찾으려고 하면 번거롭기 때문에 적당히 i값을 0이 아닌 4,5 정도의 값을 설정하고(규칙에 따라 유동적으로) 앞의 원소들을 체크하면서 풀이해야한다. 위 문제의 조건을 바탕으로 가능한 경우는 3가지가 있다. 1. i 번째 포도주를 마시면서 i-2번째 포도주까지 마셔온 경우 (arr[i] +..

이번 포스팅에서는 Aggregated Residual Transformations for Deep Neural Network논문에 소개된 ResNeXt에 대해서 정리해 보겠다. 이 network는 동일한 위상을 가진 일련의 변환을 집계하는 빌딩 블록을 반복하여 구성된다. 간단한 설계 덕분에 설정할 하이퍼 파라미터가 몇 개에 불과한 동종 멀티 브랜치 구조가 구축된다. ResNext 모델은 2016 ILSVRC 에서 1st Runner를 달성했다. 1. Aggregated Transformation 우리가 이미 알듯이 간단한 neuron은 아래 그림과 같다. 이 모델에서의 주된 특징 중 하나는 Aggregated Transformation이다. Network in Network와 반대로 Network in ..

이번 포스팅에서는 신경망을 깊이 관점이 아닌 너비 관점으로 해석한 논문인 Wide Residual Networks를 리뷰해 보겠다. Abstract Deep residual network는 수천 층으로 scale up 될수 있음을 보여주었고, 여전히 성능을 향상시키고 있다. 그러나 층이 깊어질수록 훈련 속도가 느려진다. 이러한 문제를 다루기 위해, 이 논문에서는 ResNet block의 구조에대해 자세한 실험을 했고 이들은 residual network의 깊이는 줄이고 너비를 늘렸다. 이들은 이러한 구조를 wide residual network(WRNs)라고 하고 이 구조가 일반적으로 사용되는 얇고 매우 깊은 네트워크보다 훨씬 우수하다는 것을 보여주었다. 예를 들어서 이들의 16층 wide residua..

이번 포스팅에서는 SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and

이번 포스팅에서는 Densely Connected Convolutional Networks논문에 소개된 DenseNet에 대해서 리뷰해 보겠다. Abstract 최근의 연구 결과에 따르면, 입력에 가까운 계층과 출력에 가까운 계층 간의 짧은 연결이 포함될 경우, 컨볼루션 네트워크가 훨씬 더 깊고, 정확하며, 훈련에 효율적일 수 있다. 이 논문 저자들은 이러한 관찰을 바탕으로 Dense Convolutional Network(Dense Net)을 소개할 것인데 이는 각각의 층을 모든 다른 층에 feed forward fashion 형태로 연결한 것이다. 전통적인 합성곱 신경망은 L개의 층이 있으면 L개의 연결이 있다. 그러나 이들의 network는 L(L+1)/2 개의 직접 연결이 있다. 각각의 층에 대해..