thisisuser's study

Heavy-Light Decomposition이란 트리를 여러 개의 선형 구조로 분해하여 접근할 수 있게 해주는 기법입니다.먼저 트리 위에서 다음과 같은 쿼리가 주어지는 문제를 생각해 봅시다.정점 i의 가중치를 v로 변경한다.두 정점 간의 경로 상의 정점의 가중치 합을 구한다.당연히? $N \le 100000$ 정도입니다.배열 위에서였다면 바로 신나게 세그먼트 트리를 짰겠지만, 트리 위이다 보니 바로 적용하기는 어렵습니다. 배열에서는 되고, 트리에서는 안 되는 이유는 무엇일까요?당연한 소리지만, 트리는 배열과 달리 비선형구조이기 때문입니다. 그렇다면 이렇게, 트리를 여러 개의 선형 구조로 쪼갠다면 어떨까요?이 경우에는 부분 부분에 대해서는 세그먼트 트리로 관리해줄 수 있겠다는 생각이 듭니다.문제는 이걸 ..

solved.ac: Platinum I (2024.09.06) KOI 2023 본선 2번으로 출제된 문제입니다.https://www.acmicpc.net/problem/28327 문제를 요약하면,길이 $N$의 1부터 $N$까지의 자연수를 모두 원소로 가지는 수열이 주어진다.각각의 수 $x$에 대하여, 서로 다른 모든 구간에 대하여 지그재그 수열의 최대 길이의 합을 구하여라.이 되겠습니다.$O(N^{3})$ 풀이개인적으로 이 문제를 보자마자 $O(N^{2})$를 짜는 건 사실상 천재의 영역이라 생각됩니다.따라서, 핵심 아이디어를 뽑아내고 이를 먼저 나이브하게 구현해 보겠습니다. 지그재그 수열을 더 길게 만들고 싶다면, 바로 앞의 두 수와 이번에 추가할 수에 대하여계속 증가하거나 계속 감소하는, 단조성을 띄..

일단 시간복잡도는 제껴두고, 이 문제를 풀어봅시다.13323번: BOJ 수열 1 (acmicpc.net)  만약 $N \le 10000$ 정도라면, 약간의 관찰을 통한 간단한 $O(N^{2})$ DP를 통해 해결할 수 있습니다.대충 '$DP(x, k) = x$번째 값을 $k$로 만들었을때 최소 연산 어쩌구' 꼴로 구성해주고,$DP(x, k) = \min (1 \le i \le k - 1) DP(x-1, i) + |a[x] - k| $ 이라 정의하여 간단히 해결할 수 있습니다. 하지만 만약 $N$이 무지막지하게 커져서, 한 $10^{6}$ 쯤 된다고 해봅시다.그러면 당연히 시간 내에 풀 수 없을 것입니다. 물론 그 전에 메모리가 터지겠지만요. 문제를 해결하기 위해서는 DP(x, k)를 k에 따른 함수로 해..

서론 그래프(Graph)는 여러 개의 점과 선분으로 구성된 도형으로, 실생활의 여러 상황을 모델링하는 데 사용한다. 내비게이션에서 경로를 찾을 때 도시를 그래프로 모델링하는 경우도 존재하고, 여러 컴퓨터 간의 연결 관계를 나타나는 데에도 사용한다. 이 중 도시의 교통량을 최대한 분산시키거나, 시스템 간의 연결 관계가 주어졌을 때 데이터를 최대한 빠르게 전송시키는 경우를 구해야 할 때가 있다. 이를 일반화하면 그래프에서 간선의 용량이 주어질 때, 한 정점에서 다른 정점으로 최대한의 유량을 보내는 것이다. 이를 네트워크 유량 (Network Flow) 문제라 부른다. 본 탐구에서는 이를 편리하게 분석할 수 있도록 네트워크 유량 알고리즘이 포함된 그래프 시뮬레이터를 제작하였다. 사용 알고리즘 본 탐구에서는 에..

DP를 활용하는 대표적인 문제로 LCS(Longest Common Sequence)가 있습니다.시간복잡도 $O(N^{2})$, 공간복잡도 $O(N^{2})$로 해결하는 풀이가 가장 일반적입니다. 그렇다면 다음 문제를 봅시다.https://www.acmicpc.net/problem/18438 18438번: LCS 5LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.www.acmicpc.net문자열의 길이가 7000 이하이니 시간 복잡도는 문제될 게 없습니다만,공간 복잡도가 비정상적으로 줄어버리며 난이도가 확 올라갔습니..

마지막으로, UI를 개선하고 데이터 저장 및 불러오기 기능을 제작하였다. 먼저 UI 개선이다. 기존에 제작한 프로그램에서는 유량이 어느 방향으로 흐르는 지 알 수 없었다. 따라서 방향을 표시해주어 이를 알 수 있도록 제작하였다. 화살표는 밑변 16, 높이 14의 이등변삼각형으로 구성해 주었다. 이때, 유량이 흐르는 방향을 판별하여 이를 향하게 해주어야 하므로 삼각비를 응용하였다. 기본적으로 다음과 같이 설정을 해줄 수 있다. 꼭짓점에서 20만큼 뺀 이유는 정점의 반지름이 20으로 표현되기 때문에 이렇게 설정하였다. 각도는 기울기로 구현하였고, 이 과정에서 고려해야 할 사항이 2가지 존재한다. 1. 기울기가 x축에 수직일 때 두 정점을 지나는 직선의 기울기는 $\frac{y_{to} - y_{from}}{..

이번에는 생성한 그래프에서 두 정점 간의 최대 유량을 계산하는 알고리즘을 구현하였다. 최대 유량 문제란, 용량이 주어진 간선에 대해 최대 유량을 구하는 문제를 의미한다. 다음과 같이 그래프가 주어진 상황을 가정하면, 1 → 3 → 4 → 2로 1의 유량을 흘려주고, 1 → 4 → 2로 2의 유량을 흘려주고, 1 → 3 → 2로 2의 유량을 흘려주면 총 5의 유량을 보낼 수 있다. 최대 유량 알고리즘으로는 에드몬드-카프 (Edmonds-Karp) 알고리즘을 사용하였다. 시간복잡도는 $O(VE^{2})$으로, 돌아가기에는 충분한 알고리즘이기에 이를 활용하였다. 두 지점을 연결하는 어떠한 경로에 대해 유량을 흘려줄 수 있다면, 항상 흘려주는 것이 더 이득이다. 즉, 그리디하게 문제를 해결할 수 있다. 만약 이..

이번 시간에는 그래프를 생성 및 수정할 수 있는 프로그램을 제작하기로 했다. 먼저 다음과 같이, 그래프를 다룰 수 있는 변수들을 설정했다. //network flow int [][]capacity = new int[101][101]; int [][]flow = new int[101][101]; int []parent = new int[101]; //graph simulation float []x = new float[101]; float []y = new float[101]; boolean []exist = new boolean[101]; 먼저 capacity와 flow는 각각 해당 간선의 용량과 현재 흐르고 있는 유량을 의미한다. 네트워크 플로우 알고리즘을 사용할 것이기 때문에 이렇게 2개의 데이터를 ..

문제 인식 그래프(Graph)는 여러 개의 점과 선분으로 구성된 도형으로, 실생활의 여러 상황을 모델링하는 데 사용한다. 예를 들어 내비게이션에서 경로를 찾을 때 도시를 그래프로 모델링하는 경우도 존재하고, 여러 컴퓨터 간의 연결 관계를 나타나는 데에도 사용한다. 이 중 도시의 교통량을 최대한 분산시키거나, 시스템 간의 연결 관계가 주어졌을 때 데이터를 최대한 빠르게 전송시키는 경우를 구해야 할 때가 있다. 이를 일반화하면 그래프에서 간선의 용량이 주어질 때, 한 정점에서 다른 정점으로 최대한의 유량을 보내는 것이다. 이를 네트워크 유량 (Network Flow) 문제라 부른다. 본 탐구에서는 이를 편리하게 분석할 수 있는 프로그램을 제작할 계획이다. 관련 조사 시행 및 문제 해결 방안 먼저 기본적인 네..

문제 https://judge.codingpanda.kr/problem.php?id=1761 Discrete Convolution - 문제 - CodingPanda 합성곱 (Convolution)은 신호 및 시스템, 디지털 처리 등 다양한 분야에서 쓰인다. 특히 인공지능 쪽으로는 합성곱 신경망 (Convolution Neural Network, CNN)에 응용되는 개념이다. 두 벡터 A,B에 대해, 이산 judge.codingpanda.kr 문제 제작 과정 알고리즘들을 배우면서 실제로 사용되는 분야에 적용시켜 문제를 만들고자 하였습니다. 따라서 인공지능 분야의 합성곱 신경망 (Convolution Neural Network, CNN)에 사용되는 합성곱 알고리즘을 구성하는 문제를 제작하게 되었습니다. 배경..