dldyou

수열 A와 수열 B가 주어졌을 때, 수열 A의 원소들이 수열 B의 원소들보다 큰 쌍이 몇 개나 있는지 구하는 문제이다. 2가지 방법으로 해결할 수 있다. 1. A, B 모두 정렬 후, 투 포인터 2. B만 정렬 후, 이분 탐색 2번의 경우 lower_bound을 이용해서 바로 풀어주면 된다. 1번의 경우는 merge sort에서 쪼개었던 두 배열을 다시 합칠 때 정렬하는 형태를 이용하자. A, B 모두가 정렬되어 있다면 A의 앞에서 나온 원소보다 뒤에 나온 원소가 B의 더 뒤의 원소들보다 클 것이다. 이를 이용해서 해결해주면 된다. int main(void) { fastio; cin >> T; while (T--) { cin >> N >> M; for (int i = 0; i ..

동아리 초심자 오늘 문제 추천으로 가져온 문제이다. 그래프에서의 사이클은 자주 접해봤을 것이다. 그러나 순싸분으로 불리는 '순열 사이클 분할'이라는 개념에 대해서는 들어본 사람이 많이 없을 것이다. 그래서 이 개념을 소개하고자 들고 온 문제이다. 순열 사이클의 개념 자체는 문제에 적혀있는 것과 동일하다. 개념 자체가 직관적으로 알 수 있고 문제 또한 그대로 구현하면 된다. 순열 사이클이라는 특수한 경우에 의해 in-out degree(들어오는 간선과 나가는 간선)이 하나이므로 구현 또한 간단하다. dfs를 통해 방문하지 않은 정점이 나올 때까지 돌려주면 된다. 각 정점은 한 번만 방문하므로 $O(N)$에 해결 가능하다. 코드 보기 ▼ 더보기 int T, N, A[MAXN]; bool vst[MAXN]; ..

서론 항상 새로운 기술을 배우기 시작하는 것은 귀찮지만 한편으로는 재미있는 것 같다. 저번 시간에 Flutter 프로젝트를 구성해 봤었는데, 오늘은 해당 프로젝트가 어떻게 이루어져 있는지, 어떻게 작동이 되는지를 알아보고자 한다. 프로젝트 구성 README 처음 생성 시에 README 파일과 main.dart 파일 하나를 띄워준다. README 파일에는 처음으로 Flutter 프로젝트를 진행하는 사람들을 위한 Docs들이 주어진다. https://docs.flutter.dev/get-started/codelab 따라 만들기만 해도 어느 정도의 기본 요소는 알아갈 수 있는 설명서가 제공된다. 카피 코딩에 대해 호불호가 갈리는 것은 사실이지만, 언제나 처음은 흥미로 시작하는 것이기에 나는 좋게 보는 편이다...

서론 틈틈이 개발을 진행하고자 해서 조금 둘러보다가 Flutter를 발견하게 되었다. 처음 봤을 때는 별 생각이 없었는데, 크로스 플랫폼 지원에 Flutter에서 사용하는 Dart라는 언어가 C / Java와 유사한 문법을 가지고 있다는 것에 혹해 설치부터 진행하게 되었다. 설치 뿐이라면 이 글이 더 이상 이어지지 않을 것이고, 시간이 나서 공부를 이어간다면 글도 이어지고 있을 것이다. 설치 1. Flutter 설치 우선, window환경으로 진행하였다. Flutter 홈페이지 https://docs.flutter.dev/ 에서 Get started > Windows > Android 순으로 들어가 SDK를 설치하였다. C: 드라이브 바로 아래에 옮겨서 압축을 풀어주고 나서 사용자 환경 변수에 C:\fl..

최단 경로 알고리즘(1) - floyd-warshall / dijkstra 이전 글과 달리 이번 글에서는 가중치가 음수인 간선에 대해서도 (가중치가 음수인 cycle이 생기는 그래프) 최단 경로를 구할 수 있는 알고리즘을 소개한다. Bellman Ford 첫 번째로 알아볼 벨만-포드 알고리즘이다. 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이며 간선의 가중치가 음수일 때도 경로를 구할 수 있다는 특징을 가지고 있다. 벨만-포드 는 아래와 같이 굴러간다. 모든 간선을 확인하면서 최단 경로를 갱신한다. 1.을 $V$번 반복한다. 만약 $V$번째에서도 최단 경로를 갱신하려 한다면 음수 사이클이 존재한다는 것이다. $V$번째에서도 갱신 시도가 있을 때 음수 사이클이 존재한다는 것의 이유는 $V..

[BOJ 2485번 가로수] 임의의 간격으로 배열 되어있는 가로수들이 모두 같은 간격이 되도록 가로수를 새로 심어야 하는 최소수를 구하는 문제이다. 1 3 7 13 위치에 있다면 1 3 5 7 9 11 13 과 같이 3그루를 심어주면 된다. 심는 가로수가 최소가 되려면 같은 간격이 되었을 때, 그 간격이 최대여야 한다. 즉, 최대공약수 를 구하는 문제이다. 모든 간격들의 최대공약수가 같은 간격이 되었을 때의 간격이 되는 것이고, 심어야 하는 가로수의 수는 간격들을 최대공약수로 나눈 값에 1을 빼준 값을 계속해서 더해가면 구할 수 있다. 그렇다면 최대공약수는 어떻게 구할까? 수학 시간에 최대공약수를 구하는 방법으로는 크게 서로소가 나올 때까지 공약수로 나누기 소인수 분해 후 공통인 것 중 지수가 작은 것 ..

[BOJ 11689번 GCD(n, k) = 1] 문제는 간단하다. 자연수 $n$이 주어졌을 때, $GCD(n, k)=1$ 을 만족하는 자연수 $1\leq k\leq n$ 의 개수를 구하면 되는 문제이다. 그냥 단순히 $O(N)$ 으로 반복문을 전부 돌려보며 카운팅을 하면 안되냐 할 수 있겠지만 $n$ 의 제한을 보면 $1\leq n\leq 10^{12}$ 이다. 만약 이 방식으로 제출했다면 채점 현황에 시간초과 가 찍혀 있을 것이다. 이 문제를 해결하기 위해서는 오일러 피(Euler's phi) 함수를 알아야 한다. 이 함수는 정의 자체가 $n$이 양의 정수일 때, $\phi{(n)}$은 $n$과 서로소인 1부터 $n$까지의 정수의 개수와 같다. 문제의 정의와 완전히 일치하는 것이다! $\phi{..

[BOJ 11401번 이항 계수 3] $\binom{n}{k}$ % 1,000,000,007 을 구하는 문제이다. 결론적으로 이 문제는 모듈러의 성질, 페르마의 소정리와 분할 정복을 이용해 해결 가능하다. 본문에 나오는 $p$는 소수 (1,000,000,007) 임을 인지하자. 우선 페르마의 소정리는 아래와 같다. $p$가 소수이면, 모든 정수 $a$에 대해 $a^p \equiv a\ (mod\ p)$ $p$가 소수이고 $a$가 $p$의 배수가 아니면, $a^{p-1} \equiv 1\ (mod\ p)$ 그런데 이 정리가 왜 필요하냐를 묻는다면 모듈러 산술의 정의를 보자. 위키 모듈러 산술은 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다. 그리고 다시 돌아와서 우리가 고등학교 때 ..

Spannig Tree 그래프 내의 모든 정점을 포함하는 트리 위의 정의에 따라 $N$개의 정점을 가지고 있는 그래프를 $N-1$개의 간선으로 연결하였다면 이는 트리의 형태가 되며 Spanning Tree 의 정의를 만족한다. Minimum Spanning Tree Spanning Tree 중 사용한 간선들의 가중치의 합이 최소인 트리 Spanning Tree 와 MST 는 하나의 그래프에 여러 개가 존재할 수 있다. 이러한 MST 를 구하는 알고리즘에는 2가지 방식이 있다. Prim 과 Kruskal 알고리즘이다. Prim 정점을 선택하며 진행되는 알고리즘이며, 하나의 집합에 계속해서 포함시키는 방식으로 진행된다. 시작 정점을 집합$(S)$에 포함시킨다. $S$에서 인접한 정점들 중에서 갈 수 있는 모..

이분탐색 말 그대로 두개로 나누어서 탐색하는 방식이다. 정확히는 정렬된 데이터에서 절반인 지점을 찍어 찾는 데이터가 맞는지 확인하는 과정을 계속해서 거쳐서 원하는 데이터를 찾는 방식이다. Up Down 게임 Up Down 게임을 생각하면 이해가 좀 더 쉬울 것이다. 상대방이 1부터 100사이의 수 중에 하나를 선택하고 우리는 턴마다 숫자를 물어봐서 선택한 수와 (동일한지 / 큰지 / 작은지)를 알 수 있다. 여기서 1, 2, 3, 4, ... 이렇게 차례대로 부른다면 언젠가는 맞겠지만 우리는 이 턴을 최대한 줄이고 싶다. 운이 좋으면 한 번에 맞출 수도 있겠지만 여러번의 게임을 진행했을 때를 고려하자. 이 게임을 어떻게 플레이할지는 모두 알 것이다. 50을 찍고 Up 이면 51과 100의 절반인 75, ..