주뇽's 저장소

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 82478 36840 25903 42.457% 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순..

https://web.stanford.edu/class/cs224w 목차 1. GNN 학습(3) Supervised vs UnSupervised - Supervised - UnSupervised 2. Training Piepeline - Loss Function - Classificaion Loss - Regression Loss - Evaluation metrics 👉 1. GNN 학습(3) Supervised vs UnSupervised - Supervised 지도학습은 그래프 외부에서 얻은 레이블 정보를 활용하는 방식이다. 예를 들어 인용 네트워크 그래프에서 각 노드(논문)가 어떤 주제 분야에 속하는지를 예측하는 문제에서는 외부에서 제공되는 논문의 주제 분야 정보가 레이블로 사용될 수 있다. 트랜잭..

https://web.stanford.edu/class/cs224w 목차 1. GNN 학습(2) Hierarchical - Hierarchical Pooling - Hierarchical Aggregate - Graph-Level Issue : Graph Level의 예측을 수행할 때 Gloabal pooling은 그래프 정보를 유실시킬 수 있다. ex): Node embeddings for G1 : {-1, -2, 0, 1, 2} Node embeddings for G2 : {-10, -20, 0, 10, 20} G1과 G2 그래프는 완전히 다른 노드 임베딩을 가지고 있고 구조적으로도 완전히 다르다. 만약 여기서 gloabl sum pooling을 사용하게 된다면 결과값은 다음과 같다. Predicti..

https://web.stanford.edu/class/cs224w 목차 1. GNN 학습(1) Prediction-head - Node-Level - Edge-Level - Graph-Level 👉 1. GNN 학습(1) Prediction-head GNN의 출력은 노드 임베딩의 집합 {𝐡v ∈ ℝd, ∀𝑣 ∈ 𝐺} 이다. 이 노드 임베딩들을 가지고 최종적인 prediction을 생성하기 위해서는 prediction head 모듈이 필요하며 Prediction head는 노드, 에지, 그래프 레벨의 예측 작업에 따라 다르게 설계된다. - Node-Level 방법: 가장 간단한 방법은 노드 임베딩에 대해 선형변환을 수행하는 것이다. 노드 분류 문제의 경우 선형변환 결과에 Softmax를 적용해 multi..

https://web.stanford.edu/class/cs224w 목차 1. 그래프 변형(Graph Manipulation) - 특징(Feature) 수준의 그래프 변형 (Graph Feature Manipulation) - 구조(Structure) 수준의 그래프 변형 (Graph Structure Manipulation) 👉 1. 그래프 변형(Graph Manipulation) GNN에서는 일반적으로 입력 그래프를 그대로 사용하여 노드 임베딩을 학습한다. 하지만 항상 원본 그래프가 노드 임베딩을 학습하는 데 최적인 것은 아니다. 따라서 상황에 따라 그래프를 변형하여 사용하면 더 나은 성능을 얻을 수 있다. 그래프 변형이 필요한 이유는 크게 두 가지 관점에서 살펴볼 수 있다. 1. 특징(Feature)..

https://web.stanford.edu/class/cs224w 목차 1. 다층 GNN Layer (Layer connectivity) 2. Over-Smoothing 문제 - 수용필드(Receptive field) 3. 얕은 GNN 레이어의 문제를 해결하는 방법 - MLP - Skip Connection 👉 1. 다층 GNN Layer (Layer connectivity) 단일 GNN 레이어를 다층 GNN 레이어로 만드는 가장 기본적인 방법은 GNN레이어를 순차적으로 쌓는것이다. Input : 초기 V노드의 특성 Xv Output : L번의 레이러를 통과한 임베딩 벡터 Hv^(L) GNN에서의 레이어의 개념은 정보를 수집하기 위해 얼마나 많은 홉을 이동해야 하는지에 대한 정보이다. 이 때 너무 많은..

분류 분류 문제란 주어진 입력 데이터를 미리 정의된 몇 개의 클래스 또는 범주 중 하나로 할당하는 문제를 말한다. 이는 기계 학습, 특히 지도 학습(Supervised Learning)의 대표적인 문제 중 하나이다. 분류 문제의 다른 예시로는 다음과 같은 것들이 있다: 의료 진단: 환자의 증상, 검사 결과 등을 바탕으로 질병의 유무 또는 질병의 종류를 판단 손글씨 인식: 이미지로 주어진 손글씨를 0부터 9까지의 숫자 중 하나로 분류 감성 분석: 영화 리뷰, 상품 평가 등의 텍스트 데이터를 '긍정', '부정', '중립' 등의 감성 클래스로 분류 분류 문제는 클래스의 개수에 따라 이진 분류(Binary Classification)와 다중 클래스 분류(Multi-class Classification)로 나눌 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 1 초 256 MB 73396 34595 24514 46.854% 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉..