thisisuser's study

마지막으로, 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)에 사용되는 합성곱 알고리즘을 구성하는 문제를 제작하게 되었습니다. 배경..

문제 링크 https://www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 문제 선정 과정 그래프 기반 문제로, 온라인 쿼리로 간선이 추가되며 두 정점 사이의 거리를 구해야 하는 문제로 보였습니다. 난이도도 적당해 보이기 때문에 이 문제를 풀기로 하였습니다. 문제 풀이 전략 문제를 모델링하면 다음과 같습니다. $N$개의 정점에 대하여 두 가지의 쿼리가 주어집니다. 쿼리 1: 가중치가 있는 방향 간선이 추가됩니다. 쿼리 2: 두 정점..

문제 링크 Codeup: 5313 잔디밭의 개미굴 고등3) KOI 공원의 잔디밭에는 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 $N$ 개의 방으로 구성되어 있으며, 서로 다른 두 개미굴을 직접 잇는 $N - 1$ 개의 통로가 있고, 임의의 서로 다른 두 codeup.kr Baekjoon: 28328 28328번: 잔디밭의 개미굴 KOI 공원의 잔디밭에는 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 $N$ 개의 방으로 구성되어 있으며, 서로 다른 두 개미굴을 직접 잇는 $N - 1$ 개의 통로가 있고, 임의의 서로 다른 두 개미굴 www.acmicpc.net 문제 선정 과정 먼저 문제가 굉장히 길었다. 대략적으로 요약하면 다음과 같다. 트리 구조의 그래프가 주어지고, 각 노드는 0 또는 1의 데이..