Most Popular
-
미분과 경사하강법(Gradient Descent)
미분 (Differentiation) 미분의 정의 [출처] https://commons.wikimedia.org/wiki/File:Derivative1.png, Koantum 미분은 다음과 같이 정의할 수 있다. 변수의 변화에 따른 함수값의 변화량 함수 위의 주어진 점에서의 접선의 기울기 변화율의 극한 함수 내에서 미분을 사용하면 변수의 특정 값에서의 기울기를 구할 수 있다. 한 점에서 기울기를 알면 어느 방향으로 점을 움직여야 함수값이 증가 또는 감소하는지를 알 수 있다. $$f'(x) = lim_{h\rightarrow0}\frac{f(x + h) - f(x)}{h}$$ $$f(x) = x^2 + 2x + 3$$ $$f'(x) = 2x + 2$$ $f(x) = x^2 + 2x + 3$의 미분은 $f'..
-
GNN(Graph Neural Network)의 정의와 특징 그리고 추천시스템에서의 GNN 계열 모델
들어가기 전에 이제까지 딥 러닝 모델은 CNN(Convolution Neural Network), RNN(Recurrent Neural Network), Transformer 등 다양한 신경망 모델 종류로 발전해 왔다. 그렇지만 복잡한 구조 또는 관계를 지니는 문제를 임베딩하는 데 한계가 있어왔고, 이러한 문제를 해결할 수 있는 모델로서 그래프(Graph)를 사용한 신경망 모델이 제안된다. 이번 글에서는 그래프를 사용한 딥 러닝 모델인 GNN의 정의와 의의에 관해 살펴보고, GNN 모델을 해석하는 관점에서 제시된 여러 종류의 GNN 모델에 관해 살펴보자. 그래프(Graph)의 정의와 사용 그래프는 정보과학을 공부하면 항상 빼 놓을 수 없는 중요한 자료구조이다. 프로그래밍 문제를 푼 사람들이라면 알겠지만 ..
-
Linux(리눅스) Shell Command(쉘 명령어)
들어가기 전에 우리는 대개 컴퓨터를 주로 사용할 때 마우스를 움직여서 어떠한 그래픽 요소을 다루는 GUI(Graphic User Interface)에 익숙한 경우가 많다. 그러나 처음으로 Linux 또는 Unix를 접할 때 그동안 생전 보지 못했던 CLI(Command Line Interface)를 만날 수 있다. 막상 첫 CLI를 다룰 때는 어색할 수 있어도 기본적인 명령어를 익히고 Linux 환경에서 프로그램이나 시스템을 다룰수록 CLI의 편리함과 매력을 느끼게 될 것이다. 이번 글에서는 Linux에 관한 간단한 소개와 기본적인 명령어를 소개하고, 각각의 명령어가 구체적으로 어떠한 역할을 하는지 예시를 통해 다뤄볼 것이다. Linux Linux를 왜 알아야 할까? Linux는 서버에서 일반적으로 흔히..
-
나이브 베이즈 정리(Naive Bayes Theorem)와 나이브 베이즈 분류(Naive Bayes Classification)
Bayes 정리와 사후 확률, 증거에 관한 자세한 내용은 아래의 글을 참고하시기 바랍니다. https://glanceyes.tistory.com/entry/인공지능-기초-Uncertainty-1-확률적인-추정을-위한-확률과-사건-그리고-명제 [인공지능 기초] Uncertainty (1) - 확률적인 추정을 위한 확률과 사건, 그리고 명제 들어가기 전에 이 세상의 많은 일들은 확률적인 경우가 많다. 그 상황에서 우리는 자신의 목적에 가장 부합하면서 확률적으로 발생 가능성이 높거나 낮은 것을 고려하여 최선의 선택을 하려고 glanceyes.com https://glanceyes.tistory.com/entry/인공지능-기초-Uncertainty2-결합-확률과-조건부-확률-그리고-베이즈-정리 [인공지능 기초]..
-
원격 서버에서 Jupyter Notebook 또는 Jupyter Lab을 실행하여 접속하기
자신에게 할당받거나 또는 자신이 운영 중인 서버가 있는데, 이를 원격으로 접속하여 jupyter 환경을 이용하고 싶을 때 유용할 수 있다. 인터넷 환경이 갖춰진 곳에서 웹 브라우저만 있어도 본인이 알고 있는 비밀번호를 이용하면 서버의 jupyter를 이용할 수 있는 것. 이 글에서는 네이버 부스트캠프 AI Tech 활동에서 제공한 AI Stages의 서버를 이용하지만, AWS EC2, GCP 등 여러 클라우드 플랫폼의 서버에도 같은 방법으로 적용할 수 있다. 설정 과정 우선 서버에 터미널을 이용하여 ssh로 접속한다. which jupyter로 jupyter가 설치되어 있는지 확인하고, 설치되지 않았으면 pip install jupyter로 이를 설치한다. 이왕 설치하는 김에 뒤에서 필요할 Jupyter..
-
macOS(맥 OS) 로그인 배경화면(잠금화면) 변경하는 방법
macOS 빅 서(Big Sur) 이상 모두 가능합니다. 벤투라(Ventura)도 가능합니다. (2022-10-26 기준) macOS를 사용하면서 애플 기기간의 이음새 없는 연동성과 시각적인 유려함은 마음에 들었지만, 개인적으로 windows에서는 진작에 지원해주던 적지 않은 기능들을 macOS에서는 찾아볼 수 없는 점이 아쉽다. 특히 첫 부팅을 시작했을 때 뜨는 로그인 배경화면을 변경하는 기능은 시스템 설정에서 지원하지 않는다. 지원 안 하는 이유가 짐작가기는 하지만, 그래도 사용자가 자신이 원하는대로 인터페이스의 디자인을 소소하게 변경할 수 없어서 개인적인 아쉬움이 드는 건 어쩔 수 없나보다. 이처럼 이전에도 로그인 배경화면 변경은 지원을 안 했지만 몇 가지 방법이 있었는데, 2020년 11월에 빅 ..
-
확률(Probability)과 딥 러닝(Deep Learning)
딥 러닝과 확률론 딥러닝의 학습 방법은 확률론에 기반을 두고 있다. 특히, 기계학습의 손실함수는 데이터 공간을 통계적으로 해석하여 유도하게 된다. 즉, 예측이 틀리는 것을 최소화하도록 데이터를 학습하는 원리를 가진다. 예를 들어, 회귀 분석에서 손실함수로 사용되는 $L_2$ Norm은 예측오차의 분산을 가장 최소화하는 방향으로 학습하도록 유도한다. 또한 분류 문제에서 사용되는 교차엔트로피(cross-entropy)는 모델 예측의 불확실성을 최소화하는 방향으로 학습을 유도한다. 기계학습에서 사용되는 모든 손실함수는 실제 데이터의 분포와 모델을 예측하는 분포의 차이를 줄이려고 하는 것이며, 이 두 대상을 측정하는 방법은 통계학을 기반으로 한다. 확률분포(Probability Distribution) [출처]..
-
Transformer의 Multi-Head Attention과 Transformer에서 쓰인 다양한 기법
앞서 우리는 입력으로 주어진 sequence에서 어떠한 부분에 주목할지를 예측에 반영하는 attention 기법을 배웠다. 이러한 Self-Attention에서 좀 더 나아가 head를 여러 개 사용하여 주어진 데이터를 이해하려는 Multi-Head Attention 기법과 이외 'Attention is All You Need' 논문에서 소개되었던 다른 기법들도 이해해 보고자 한다. 이전의 transformer에 관해 다룬 포스트의 내용을 기반으로 하므로 아래의 글을 참조하면 이 글을 이해하는 데 도움이 될 수 있다. Self-Attention을 사용하는 Transformer Self-Attention을 사용하는 Transformer(트랜스포머) Sequential Model Sequential Mode..
-
VAE 계열 모델의 ELBO(Evidence Lower Bound) 분석
RecVAE 모델을 분석하기 위해 논문을 읽으면서 VAE에 관해 모르거나 잘못 알고 있던 내용이 많다는 걸 알게 되어 이를 정리하고자 한다. 특히 ELBO 부분이 그전에는 잘 이해가 안 갔는데, 이번에 붙잡고 공부하면서 좀 더 명확히 이해할 수 있게 되었다. 그리고 VAE의 ELBO 유도 과정을 완전히 잘못 알고 있어서 복습하면서 정정했다. VAE(Varational AutoEncoder) 한번에 이해하기 위의 노트 필기의 흐름을 따라가보면 VAE의 ELBO가 왜 loss function에서 나오는 건지와 그 학습 방법을 이해할 수 있다. VAE 계열 모델의 ELBO 분석 VAE(Variational Autoencoders) [출처] https://commons.wikimedia.org/wiki/File..
-
데이터 전처리의 피처 스케일링(Feature Scaling)
머신러닝의 데이터 전처리에서의 피처 스케일링(Feature Scaling) Feature Scaling이란? 서로 다른 변수의 값 범위를 일정한 수준으로 맞추는 작업이다. Feature Scaling을 하는 이유는? 변수 값의 범위 또는 단위가 달라서 발생 가능한 문제를 예방할 수 있다. 머신러닝 모델이 특정 데이터의 편향성을 갖는 걸 방지할 수 있다. 데이터 범위 크기에 따라 모델이 학습하는 데 있어서 bias가 달라질 수 있으므로 하나의 범위 크기로 통일해주는 작업이 필요할 수 있다. Feature Scaling의 종류 표준화 정규화 표준화(Standardization)란? 서로 다른 범위의 변수들을 평균이 0이고 분산이 1인 가우시안 정규 분포를 가진 값으로 변환하는 작업이다. 표준화를 하는 이유는..
Recent
-
[빠르게 정리하는 통계] Conjugate Prior와 Exponential Family
추후 완성 예정.
-
[빠르게 정리하는 최적화 이론] PCA(Principal Component Analysis)
추후 완성 예정.
-
[빠르게 정리하는 최적화 이론] MLE, MAPE 그리고 Fully Bayesian
MLE(Maximum Likelihood Estimation), MAPE(Maximum A Posterior Estimation) 그리고 Fully Bayesian approach에 관한 글. 추후 완성 예정.
-
[빠르게 정리하는 최적화 이론] Lagrangian과 Convex
추후 완성 예정.
-
[빠르게 정리하는 통계] 머신러닝에서 기본으로 알아야 할 확률분포 개념
추후 완성 예장.
-
[빠르게 정리하는 통계] 자주 쓰이는 확률분포 정리
자주 쓰이는 확률분포인 Bernoulli, Binomail, Poisson, Exponential, Gamma 그리고 Beta 분포에 관한 정리.
-
Generative Modeling by Estimating Gradients of the Data Distribution (Noise Conditional Score Network)
Diffusion Model의 시초인 Diffusion Probabilistic Models부터 Score-based Generative Model(NCSN), Denoising Diffusion Probabilistic Models(DDPM) 그리고 Denoising Diffusion Implicit Models(DDIM)까지 정리하는 시리즈의 세 번째 글에서는 Score-based Generative Model(NCSN)에 관해 리뷰해 볼 것이다. 이 논문을 이해하는 데 도움을 주는 전반적인 배경 지식과 내용은 아래 저자의 웹사이트에 잘 소개되어 있다. https://yang-song.net/blog/2021/score/ Generative Modeling by Estimating Gradients ..
-
DDPM(Denoising Diffusion Probabilistic Models)과 DDIM(Denoising Diffusion Implicit Modles) 분석
Diffusion Model의 시초인 Diffusion Probabilistic Models부터 Score-based Generative Model(NCSN), Denoising Diffusion Probabilistic Models(DDPM) 그리고 Denoising Diffusion Implicit Models(DDIM)까지 정리하는 시리즈의 두 번째 글에서는 DDPM과 DDIM에 관해 리뷰해 볼 것이다. 1. DDPM(Denoising Diffusion Probabilistic Models) (1) Key Point (2) Review DDPM에 관해 수식적으로 자세히 정리한 글은 아래 링크를 참조. https://glanceyes.tistory.com/entry/Generative-Model%EA..
-
Diffusion Model의 시초인 Diffusion Probabilistic Models
Diffusion Model의 시초인 Diffusion Probabilistic Models부터 Score-based Generative Model(NCSN), Denoising Diffusion Probabilistic Models(DDPM) 그리고 Denoising Diffusion Implicit Models(DDIM)까지 정리하는 시리즈의 첫 번째 글에서는 Diffusion Models를 위한 preliminaries와 Diffusion Probabilistic Models에 관해 리뷰한다. 1. Preliminaries (1) Generative Model vs. Discriminative Model (2) Explicit Density Approach vs. Implicit Density Ap..
-
Generative Model과 Diffusion Model, 그리고 Denoising Diffusion Probabilistic Model
Generative Model Generative Model이란? 이에 관한 자세한 내용은 아래 글의 'Generative Model' section을 참고하면 된다. 생성 모델(Generative Model)과 VAE, 그리고 GAN Generative Model Generative Model이란? Discriminative Model과 Generative Model 일반적으로 머신러닝에서 모델을 크게 두 범주로 분류하자면 discriminative model과 generative model로 구분할 수 있다. Discriminative model은 glanceyes.com 글 작성 시점 기준으로는 diffusion model이 큰 각광을 받고 있다. 이번 글에서는 diffusion model이 무엇이..
AI
-
[빠르게 정리하는 통계] Conjugate Prior와 Exponential Family
추후 완성 예정.
-
[빠르게 정리하는 최적화 이론] PCA(Principal Component Analysis)
추후 완성 예정.
-
[빠르게 정리하는 최적화 이론] MLE, MAPE 그리고 Fully Bayesian
MLE(Maximum Likelihood Estimation), MAPE(Maximum A Posterior Estimation) 그리고 Fully Bayesian approach에 관한 글. 추후 완성 예정.
-
[빠르게 정리하는 최적화 이론] Lagrangian과 Convex
추후 완성 예정.
-
[빠르게 정리하는 통계] 머신러닝에서 기본으로 알아야 할 확률분포 개념
추후 완성 예장.
-
[빠르게 정리하는 통계] 자주 쓰이는 확률분포 정리
자주 쓰이는 확률분포인 Bernoulli, Binomail, Poisson, Exponential, Gamma 그리고 Beta 분포에 관한 정리.
-
Generative Modeling by Estimating Gradients of the Data Distribution (Noise Conditional Score Network)
Diffusion Model의 시초인 Diffusion Probabilistic Models부터 Score-based Generative Model(NCSN), Denoising Diffusion Probabilistic Models(DDPM) 그리고 Denoising Diffusion Implicit Models(DDIM)까지 정리하는 시리즈의 세 번째 글에서는 Score-based Generative Model(NCSN)에 관해 리뷰해 볼 것이다. 이 논문을 이해하는 데 도움을 주는 전반적인 배경 지식과 내용은 아래 저자의 웹사이트에 잘 소개되어 있다. https://yang-song.net/blog/2021/score/ Generative Modeling by Estimating Gradients ..
-
DDPM(Denoising Diffusion Probabilistic Models)과 DDIM(Denoising Diffusion Implicit Modles) 분석
Diffusion Model의 시초인 Diffusion Probabilistic Models부터 Score-based Generative Model(NCSN), Denoising Diffusion Probabilistic Models(DDPM) 그리고 Denoising Diffusion Implicit Models(DDIM)까지 정리하는 시리즈의 두 번째 글에서는 DDPM과 DDIM에 관해 리뷰해 볼 것이다. 1. DDPM(Denoising Diffusion Probabilistic Models) (1) Key Point (2) Review DDPM에 관해 수식적으로 자세히 정리한 글은 아래 링크를 참조. https://glanceyes.tistory.com/entry/Generative-Model%EA..
-
Diffusion Model의 시초인 Diffusion Probabilistic Models
Diffusion Model의 시초인 Diffusion Probabilistic Models부터 Score-based Generative Model(NCSN), Denoising Diffusion Probabilistic Models(DDPM) 그리고 Denoising Diffusion Implicit Models(DDIM)까지 정리하는 시리즈의 첫 번째 글에서는 Diffusion Models를 위한 preliminaries와 Diffusion Probabilistic Models에 관해 리뷰한다. 1. Preliminaries (1) Generative Model vs. Discriminative Model (2) Explicit Density Approach vs. Implicit Density Ap..
-
Generative Model과 Diffusion Model, 그리고 Denoising Diffusion Probabilistic Model
Generative Model Generative Model이란? 이에 관한 자세한 내용은 아래 글의 'Generative Model' section을 참고하면 된다. 생성 모델(Generative Model)과 VAE, 그리고 GAN Generative Model Generative Model이란? Discriminative Model과 Generative Model 일반적으로 머신러닝에서 모델을 크게 두 범주로 분류하자면 discriminative model과 generative model로 구분할 수 있다. Discriminative model은 glanceyes.com 글 작성 시점 기준으로는 diffusion model이 큰 각광을 받고 있다. 이번 글에서는 diffusion model이 무엇이..
Algorithm
-
접미사 배열(Suffix Array)과 LCP(Longest Common Prefix)
개인적으로 알고리즘은 즉각적으로 바로 구현할 수 있도록 몸에 베어야 하되 복습하는 데 너무나 많은 시간을 투자해서는 안 되고, 문제를 풀면서 실전으로 익혀야 한다고 생각한다. 학기가 시작되면서 바빠진 만큼 지난 잊힌 알고리즘 개념들을 핵심과 코드만 짧게 정리하여 평소에도 자주 보면서 익숙해지고자 한다. 기본적으로 코드는 특별한 설명이 없으면 C++를 기반으로 한다. 접미사 배열(Suffix) 정의 문자열 $S$의 모든 접미사들을 사전 순으로 정렬한 배열. 여기서 접미사들은 문자열 $S$에서 시작 위치 번호로 관리한다. 문제 문자열 $S$="abcbca"의 접미사 배열을 구해보자. 접미사: "abcbca", "bcbca", "cbca", "bca", "ca", "a" 사전 순으로 정렬 시 "a", "abc..
-
가장 긴 증가하는 부분 수열 Longest Increasing Subsequence(LIS)
개인적으로 알고리즘은 즉각적으로 바로 구현할 수 있도록 몸에 베어야 하되 복습하는 데 너무나 많은 시간을 투자해서는 안 되고, 문제를 풀면서 실전으로 익혀야 한다고 생각한다. 학기가 시작되면서 바빠진 만큼 지난 잊힌 알고리즘 개념들을 핵심과 코드만 짧게 정리하여 평소에도 자주 보면서 익숙해지고자 한다. 기본적으로 코드는 특별한 설명이 없으면 C++를 기반으로 한다. 가장 긴 증가하는 부분 수열 Longest Increasing Subsequence(LIS) 정의 주어진 sequence의 모든 부분 수열(subsequence) 중 오름차순으로 정렬된 가장 긴 수열 문제 길이가 $N$인 임의의 수열 A의 Longest Increasing Subsequence(LIS) 길이를 구해보자. 방법 시간복잡도에 따라..
-
BOJ 백준 13257번 생태학
BOJ 백준 13257 생태학 문제: https://www.acmicpc.net/problem/13257 13257번: 생태학 첫째 줄에 N, C, D, M이 주어진다. (1 ≤ N ≤ 20, 1 ≤ C ≤ 20, 1 ≤ D ≤ 5, 0 ≤ M ≤ N) www.acmicpc.net $D$일 동안 매일마다 $C$ 마리를 포획하여 측정기가 부착이 안 된 새에 모두 측정기를 부착한다고 한다. 새가 총 $N$ 마리일 때, $D$일 후 $M$ 마리가 될 확률을 구하는 것이 문제이다. 처음에 문제를 봤을 때는 $N$, $C$, $D$, $M$의 크기가 작은 편이어서 브루스포스로 구하는 단순 확률 문제인 줄 알았으나, 날마다 C마리의 새를 포획했을 때 몇 마리가 이미 측정기가 부착되었는지를 고려해야 하므로 생각보다 ..
-
BOJ 백준 23242번 Histogram
BOJ 백준 23242 Histogram 문제: https://www.acmicpc.net/problem/23242 23242번: Histogram For a range of $[1, n]$, the natural numbers in the interval are called the data values and let $f_i$ be the frequency count of the data value $i$ in the range. The frequency of a data value $i$ is the number of occurrences of the data value $i$ in the lis www.acmicpc.net 길이가 n인 수열을 B개의 bucket으로 나누었을 때, 각 bucket의 ..
-
BOJ 백준 20047번 동전 옮기기
BOJ 백준 20047 동전 옮기기 문제: https://www.acmicpc.net/problem/20047 20047번: 동전 옮기기 입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T www.acmicpc.net 두 개의 동전을 서로 순서를 바꾸지 않고 자리를 이동하여 문제에서 주어지는 동전 배치를 만들 수 있는지 묻는 문제이다. 학회에서 ACM ICPC 예선을 준비하면서 팀원과 같이 풀었던 문제이다. 처음에는 Queue를 이용하여 푸는 구현 문제인 줄 알고 시도했는데, 계속 채점을 돌려봐도 86퍼센트에서 틀렸다고 떠서 접근 자체가 틀..
-
BOJ 백준 16467번 병아리의 변신은 무죄
BOJ 백준 16467 병아리의 변신은 무죄 문제: https://www.acmicpc.net/problem/16467 16467번: 병아리의 변신은 무죄 학교공부를 끝내고 집을 가던 다진이는 길가에서 병아리를 팔고 있는 아저씨를 발견했다. 병아리를 무척 사고 싶었던 다진이는 병아리의 상태를 확인하지도 않고 한 마리를 사서 집으로 향했다 www.acmicpc.net 병아리가 매일마다 혼자서 알을 한 개씩 낳고 이 알은 K일 후에 부화할 때, N일이 지난 후의 병아리 수를 구하는 것이 문제이다. 개인적으로 이런 유형의 문제는 우선 관찰을 자세히 하는 것이 중요하다고 생각한다. K = 0일 때와 K = 1일 때를 한 번 살펴봤다. K = 0일 때는 i일 후의 병아리의 수를 2의 거듭제곱 꼴로 나타낼 수 있고..
-
BOJ 백준 22953번 도도의 음식 준비
BOJ 백준 22953 도도의 음식 준비 문제: https://www.acmicpc.net/problem/22953 22953번: 도도의 음식 준비 첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다. 둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어 www.acmicpc.net K개의 요리를 조리하는 N명의 요리사의 조리시간이 주어진다. 한 요리사에게 격려를 여러 번 할 수 있고, 요리사에게 격려를 한 번 할 때마다 격려를 받은 요리사의 조리 시간은 1초 감소한다. 격려할 수 있는 최대 횟수가 C회일 때, K개의 요리를 조리하는 데..
-
BOJ 백준 22991번 수요응답형 버스
BOJ 백준 22991 수요응답형 버스 문제: https://www.acmicpc.net/problem/22991 22991번: 수요응답형 버스 현대오토에버는 In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라 관련 업무를 수행하는 회사이다. 현재 현대오토에버에서 수요응답형 버스(MOD)를 개발하고 있다. 수요응답형 버스는 승객이 호 www.acmicpc.net 배차 요청이 N개, 버스가 M개 주어졌을 때, 조건을 만족하면서 배차 요청에 버스를 최대 몇 대 배차 가능한지를 구하는 문제이다. 버스를 요청에 배차 가능한 조건은 다음과 같다. 배차의 탑승 인원 ≤ 버스의 정원 배차의 최대 대기 가능 시간 ≥ 버스의 도착 예정 시간 올해 2021년 SUAPC Summer(https://icpc-sinc..
-
BOJ 백준 22954번 그래프 트리 분할
BOJ 백준 22954 그래프 트리 분할 문제: https://www.acmicpc.net/problem/22954 22954번: 그래프 트리 분할 첫 번째 줄에 정점의 개수 $N$, 간선의 개수$M$이 주어진다. ($1 \le N \le 100\,000$, $0 \le M \le 200\,000$) 두 번째 줄부터 $M$줄에 걸쳐서 간선을 나타내는 정수 $u$와 $v$가 주어진다. ($1 \le u, v \le N$, $u www.acmicpc.net 정점 N개, 간선 M개의 그래프가 주어졌을 때 서로 다른 크기의 2개의 트리로 분할하라는 문제이다. 문제에서 주어지는 그래프에는 특별한 제약 사항이 없으므로 이미 그래프가 여러 개의 연결 요소로 분할되어 있을 수도 있다. 그래서 그래프의 연결 요소 개수를..
-
BOJ 백준 10273번 고대 동굴 탐사
BOJ 백준 10273 고대 동굴 탐사 문제: https://www.acmicpc.net/problem/10273 10273번: 고대 동굴 탐사 입력의 첫 줄엔 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 10) 각 테스트 케이스의 첫 줄엔 탐사할 수 있는 동굴의 수 N과 서로 직접 연결된 동굴 쌍의 수 E가 주어진다. (1 ≤ N ≤ 2 · 10 4; 0 ≤ E www.acmicpc.net 문제 내용이 길고 복잡해서 처음에는 문제 풀기가 까다로웠다. 그런데 간단히 정리하면 다음과 같다. 단방향 그래프가 주어지고 각 정점 방문 시 얻을 수 있는 이익과 각 간선을 탔을 때의 비용이 주어졌을 때, 해당 그래프를 탐색해서 얻을 수 있는 순이익의 최댓값을 구한다. 앞의 작업 진척도에 관한 내용은 사실 크..
- 방문자수
전체 방문자
오늘 방문자
어제 방문자