HyunMaru Self_Study

본격적으로 논문 리뷰를 하기에 앞서 본 리뷰는 다음 영상을 참고하여 작성하였다. https://www.youtube.com/watch?v=F-JPKccMP7k 혼자서 여러 자료들과 논문들을 통해 이해하려고 하였고, semi-supervised learning에 관한 설명에 대한 글도 올렸었다. 이후, normalized graph laplacian, fourier transform in GCN, 1st order approximation in GCN, Chebyshev polynomials, spectral convolutions, fourier domian to spatial domain 등 글을 작성하기엔 너무 많기도 하며 어려웠기에 영상을 보면서 공부하게 되었다. GNN이란? Graph와 관련된 모..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 본 문제는 제목에서 말하듯이 구간합 이라는 알고리즘을 이용해야한다. 특정 숫자가 [5, 4, 3, 2, 1]이 들어왔을 때, 각 요소별로 구간합을 미리 구해놓는다. 즉, [5, 5 + 4, 5 + 4 + 3, 5 + 4 + 3 + 2, 5 + 4 + 3 + 2 + 1] => [5, 9, 12, 14, 15]가 나오게 된다. 이후, 특정 구간의 합을 구하라고 하면, 그 구간만..

ahttps://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 실버까지는 그래프 탐색 문제가 참 쉽다. 어째, Class 3에서 bfs, dfs 문제가 참 많이 나오는 것도 여기서 꿀빨라는것 같았다. 거두절미하고, 본 문제는 입력으로 받는 N을 통해 N*N 정사각형 내 0 또는 1의 값이 채워져있다. 여기서 1은 집이 있는 곳을 의미하며, 0은 집이 없는 곳을 의미한다. 이때, 연결된 집의 모임인 단지를 정의하면서 이 단지가 몇개가 있고, 각 단지별 집이 몇..

resource : https://arxiv.org/abs/1609.02907 Semi-Supervised Classification with Graph Convolutional Networks We present a scalable approach for semi-supervised learning on graph-structured data that is based on an efficient variant of convolutional neural networks which operate directly on graphs. We motivate the choice of our convolutional architecture via a loc arxiv.org Paper title : SEMI-SUP..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리 라는 방법이 있다. 휜 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상에서 같은 숫자의 점들이 한 곳에 많이 몰려 있으면 쿼드 트리에서는 이를 압축하여 간단히 표현한다. 즉, 이 문제에서는 2의 n승 * 2의 n승의 정사각형들에 대해 분석하는 문제이다. 8 * 8 에서 0 또는 1로만 이루어졌는지 판단한 뒤, 왼쪽 위..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 이중 우선순위 큐를 구현하여, D -1일때 우선순위가 낮은 숫자를 제거하고, D 1 일때 우선순위가 높은 숫자를 제거할 수 있도록 만드는 문제이다. 당연히 골드문제이기에 시간초과를 고려하여 코드를 효율적이게 짜는 것이 제일 중요했다. 우선순위 큐 이기에 heapq를 import하는것을 기반으로 문제풀이를 생각해보았다. heapq의 heappush의 시간복잡도 O(logn)임을 이용하고, 추가적..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net solve.ac에 있는 Class 3의 문제..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 이름처럼 에이씨(ㅂ..)를 하고싶었던 문제였다. (솔직히 정답률 19퍼 인거보고 쫄았음) 나름 "단순해보이는" 문제였다. 이유는 다음과 같다. 1. 명령어를 입력받는다. 2. 주어진 명령어는 단순하다. (R : 뒤집기, D : 첫번째 요소 지우기) 3. 주어진 명령어대로 수행한 이후, 출력한다. 당장 봐도 쉬운 수준이지만...이건 골드5 문제이다. 당연히 그대로 수행하면 바로 시간초과로 혼나버린다. 그래서, 뒤집을때도 첫번째 요소, 안뒤집을때도 첫번째 ..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 이 문제는 grid에 'R', 'G', 'B', 가 표현된 곳에서 같은 색상의 구역이 몇개나 있는지 구하는 문제이다. 즉, 하나의 색상을 탐색하기 시작해서 주변에 같은 색상이 있는지 탐색해야하는 문제이다. 그러면, dx, dy를 선언하여 현재 위치에서 상,하,좌,우로 이동할 수 있게끔 해야한다. dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] 이제 어떤 알고리즘을 택할 ..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 이 문제를 풀기 위해서 첫번째 했던 생각은 처음 딕셔너리 타입으로 입력을 받기로 하였다. 최초 입력이면 d[type] = 1, 이외에는 d[type] += 1 이후, 만약 d의 길이가 1이면 바로 결과를 d.values()의 값으로 출력하도록 하였다. 그외의 1보다 큰 d라면, list(comb(range..