Mo's 알고리즘 이란?구간 질의하는 Query 문제에서 업데이트되지 않는 특수한 상황에서 사용할 수 있는 알고리즘으로 기존의 구간 쿼리는 O(NM)인 반면 Mo's 를 사용하면 O(M sqrt N) 으로 줄일 수 있습니다.  아이디어데이터가 추가적으로 업데이트되지 않는다면, 모든 쿼리에 대해서 항상 전체를 탐색해줄 필요는 없습니다. 이 전에 계산한 구간의 값을 참고하여 답을 구할 수 있습니다.   일단 데이터 길이를 N으로 했을 때 sqrt(N) 의 길이로 그룹을 나눕니다. 위 그림은 N = 10 일때의 그림이며 4개의 구간으로 나눌 수 있습니다. ( 왜 sqrt(N) 으로 나누는지는 아래에 설명하겠습니다 )  만약 위처럼 3가지 쿼리가 주어졌다고 할 때 어떻게 작동하는지 간략하게 그림으로 보고 자세히..

드디어 플래티넘2에 도착했습니다... 눈치가 빠르신 분은 알아챘을 수도 있습니다. 플3 포스팅을 안한 것과 뒤의 저 프로필이 의미하는 바가 무엇인지.. 플3 찍고 나중으로 포스팅을 미뤘다가 어느세 50%정도 채워져서 그냥 포스팅하지 않았습니다. 그리고 뒤의 프로필을 수열과 쿼리를 여러 문제를 풀면 주는건데... 넴, 세그 트리가 대량으로 과제로 나와서 본의 아니게 날먹했습니다.  티어가 실력을 전부 나타내진 않는다 어느정도 티어를 쌓으면서 위의 말이 공감되기 시작했습니다. 예전에는 티어 올리는 재미로, 티어를 목적으로 공부한 반면 지금은 알고리즘을 공부하기 위해 공부하고, 티어는 그 추가적인 결과물이라고 생각합니다.  예전에는 실버나 골드 하위 문제는 그냥 넘기는 버릇이 있었는데, 이제는 일단 풀어야겠습..

오늘은 C언어를 입문하는 사람에게 가장 어렵다고 소문난 포인터를 쉽게 이해할 수 있도록 설명해보겠습니다. 잘 이해되지 않는 부분은 댓글로 남겨주세요. 연산자 ( 배경지식 )&(변수 이름) = 해당 변수의 주소*(주소) = 해당 주소의 값 int a = 10; printf("a의 주소 = %d\n",&a); printf("해당 주소의 값 = %d", *(&a)); /// a의 주소 = 6422044 ( 사용자 마다 다름 ) /// 해당 주소의 값 = 10  변수 ( 배경지식 )모든 변수와 값은 메모리의 어딘가에 저장되며 저장된 위치를 가르키는 것이 주소이다. 예를 들면 int a = 5; 라고 할 때 사용자가 편히 사용할 수 있도록 그냥 a만 사용하면 되지만 컴퓨터 내부에..

출처 : 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..