출처 : https://www.acmicpc.net/problem/25402   1. 풀이해당 문제는 주어진 S에 대하여 집합 혹은 그룹을 만들고 각 그룹의 인원수를 Combination을 이용하여 푸는 것 임을 바로 알 수 있다. 이 문제에서 중요한 점은 주어진 집합 S에 대해 그룹의 인원수를 파악하는 것이다.  각 질문마다 S집합에 속한 노드를 chk배열에 확인해두고 단순히 dfs를 돌면 시간초과가 날 것이다. 그 까닭은 dfs는 O(N)이 아니라 O(V+E) 이기 때문이다. 이러한 dfs는 해당 노드에 연결된 모든 간선을 탐색하므로 해당 문제에서 최악의 경우 각 질문마다 O(N) 이 발생하며 결과적로 N*O(N) = O(N^2) 이 되며 시간초과가 난다. 위 예시에서 빨간색은 S집합에 속한 노드를 ..

해당 개념을 소개하기 앞써 Orthogonal의 중요성은 언급하고자 합니다. Orthogonal은 직교를 뜻하며 일반적인 Basis 를 나중에 소개할 Gram-Schmidt 혹은 QR factorization을 활용해 직교 좌표계를 만든 후, 정사영 개념을 응용하여 "근사" 에 사용할 수 있습니다.  해당 개념이 너무 중요한 까닭은 일반적으로 방정식의 해를 구하지 못하는 경우가 대다수인데... 이럴 때 근사를 사용해서 가장 가까운 해와 그 오차에 대해서 구할 수 있기 때문입니다.  Inner Product(내적)  내적은 위의 식처럼 표현할 수 있으며 이를 기하적인 의미로 해석하기 위해 아래처럼 표기할 수 있습니다. 즉 v벡터의 크기와 t를 v에 정사영 했을 때의 길이의 곱이란 결과와 위의 결과들이 모두..

해당 포스팅에선 FlexBox의 기본적이고 햇갈리는 개념을 중심으로 작성하였습니다.  FlexBox는 무엇일까? FlexBox란 유동적으로 배치하기 위한 layout 이라고 생각합니다. 이는 "유동적" 이기에 짧고 간단한 코드로 나타낼 수 있으며 정렬에 용이합니다. 그렇다면 Grid 보다 안 좋은 것 아닌가? 라고 생각하실 수 있지만, 이는 상황에 따라 다릅니다. 여기서 유심히 봐야할 것은 "유동적" 이라는 사실입니다. 해당 개념은 아래 예시들을 통해 알아보겠습니다.  출처 : https://www.acmicpc.net/problemset 제가 좋아하는 백준 사이트로 예시를 들어보겠습니다. (해당 예시는 "100% 맞다, 이렇다." 가 아니라 그저 "유동적" 이라는 느낌으로 받아드리면 될 것 같습니다.)..

해당 포스팅에서 수열과 함수의 대응성과 단조수열정리에 대해 알아볼건데요, 시험에서 감점당하기 좋은.. 부분과 기초적인 부분을 중심으로 알아보겠습니다.  해당 포스팅은 Calculus Early Transcendentals 원서를 기반으로 작성했습니다. 이번 내용은 기초적인 내용이기에 짧습니다.. 1. 수열과 함수의 대응성 기본적으로 수열에서 로피탈은 사용할 수는 없습니다. 왜냐하면 수열은 실수에 대해서 정의된 것이 아닌 정수로 끊겨져 있기 때문입니다. 따라서 수열을 연속인 함수와 대응할 경우에만 로피탈을 사용할 수 있습니다. If lim x->infinity f(x) = L and f(n) = a_n (n = integer), then limit n->infinity a_n = Lf(n) = a_n 으로..

부분공간(Subspace)space, 공간은 벡터들의 집합을 말하는데, 어떤 공간 집합의 부분 집합을 Subspace라고 하며 아래 3가지 규칙을 만족해야 합니다. Let H is Subspace of Rn1. H는 zero vector를 포함해야 한다.2. H에 속하는 임의 벡터 u, v에 대하여 u+v 또한 H 집합에 속해야 한다.3. H에 속하는 임의 벡터 u에 대하여 cu 또한 H 집합에 속해야 한다. 이를 만족하는 Subspace도 크게 2가지로 나눌 수 있습니다. 1. Zero subspace - 오직 zero vector만 포함2. Nonzero subspace - 다른 vector들도 포함만약 Nonzero subspace라면 (2), (3)에 의해 무한한 크기의 집합이 될 것이며 선형적인..

CCW(Counter-Clockwise) 알고리즘 CCW는 벡터의 외적을 이용하여 한 선분에 대하여 한 점의 위치 관계를 파악하는 알고리즘을 말합니다.직선 AB에 대하여 점 C의 위치 관계 서술한다면 AB벡터와 AC벡터의 외적 값의 부호를 통해 알 수 있습니다. 그리고 이러한 위치 관계를 통해 기하에서 다양한 것들을 할 수 있습니다. ※ 벡터의 외적과 방향성오른손의 법칙을 통해 AB벡터로 손을 가르킨 후 점 C의 방향으로 손을 감을 때 엄지손가락이 위로 가면 반시계 ( 외적값이 + ) 반대로 아래로 가면 시계방향 ( 외적값이 - ) 로 나타납니다.  int ccw(pii v1, pii v2, pii v3){ ll val = (v2.first-v1.first) * (v3.second-v1.second..

SCC 알고리즘 목적 해당 알고리즘의 목적은 사이클을 한 개의 노드로 묶는 것을 목적으로 하며 이 알고리즘은 위상 정렬에서 많이 사용됩니다. 위상 정렬은 사이클이 없는 그래프, 즉 dag라는 조건이 있어야 했는데요. 하지만 실제 복잡한 그래프는 사이클이 존재하는 그래프가 매~우 많습니다. 이런 상황을 다루기 위한 테크닉이 바로 SCC 알고리즘이 되겠습니다!강한 연결 요소 Strong Connected Component의 Group에 속하는 노드는 u, v 에 대하여 u->v로 항상 이동이 가능한 집단을 말합니다. SCC알고리즘은 이런 조건을 만족하는 노드를 grouping하는 것입니다!일반적인 그래프(트리 포함) -> Dag(트리 포함x) 변환!  작동 메커니즘문제 출처 : https://www.acmi..

Anaconda 설치 아래 링크에서 email을 적은 후 최신 버전으로 설치하면 됩니다. Distribution | AnacondaAnaconda's open-source Distribution is the easiest way to perform Python/R data science and machine learning on a single machine.www.anaconda.com 중요한건 환경 변수인데요. 왠만하면 괜찮겠지만, 혹시나 하니 확인하는 것을 추천합니다. 만약 Anaconda를 사용하다 나중에 사용자 이름을 바꾸는 경우엔 나중을 위해서 지웠다 다시 설치하는 것을 추천합니다!  Pytorch 설치저는 Python = 3.10.0 / Pytorch = 2.3.0 을 사용하였고, gpu가 ..

Information정보이론에서 Information(정보량) 은 불확실한 상황을 결정하기 위해 필요한 정보량으로 정의되곤 합니다. 예를 들면 제가 1~100의 수 중 1가지 수를 선택했고 여러분이 수를 골라서 up / down 혹은 answer 이라는 대답을 받을 수 있으면 log100 번 물어보면 문제를 확실하게 맞출 수 있습니다. 어떤 사건이 발생할 확률이 p라면 p = (모든 상태수)의 역수 로 생각할 수 있으며, 정보량을 수식으로 나타내면log(1 / p)나타낼 수 있습니다. 이 때 log는 밑이 2인 log를 말합니다. 아래 예시를 통해 이해해보도록 하겠습니다.  해당 예시에선 그림으로 나타내기 위해 2^k 꼴의 확률을 사용했는데 수학적으론 1/3이나 1/7... 등 상관 없습니다  Entro..

해당 포스팅은 간단하게 코드를 어떻게 짰는지를 위주로 작성했습니다.사실... 정확도가 낮고.. 나중에 발전시킨걸 분석할라고 했는데.. 생각보다 잘 나와서 바로 올리게 되었습니다. 정보/인공지능 이론은 나중에 추가적으로 포스팅하겠습니다. 1. Datasetkaggle에 올라온 데이터를 이용했습니다.  Dogs vs. Cats | Kaggle www.kaggle.com class MyDataset(Dataset): def __init__(self, folder): super().__init__() self.url = f'./dataset/{folder}' self.transform = transforms.Compose([ transforms.Re..