Overview Web Programming 여러 분야의 개발을 동시에 하면서 항상 그래 왔지만 유난히도 '참 가야 할 길이 멀구나' 싶은 생각이 들었던 한 주였다. 우선 프런트엔드 쪽에서는 그동안 개발했던 웹 랜딩페이지(+모바일 대응) 보다는 철저히 모바일을 위한, 데스크톱이 아닌 디바이스의 환경에 최적화된 웹뷰 작업이었다. 프론트엔드 개발을 하면서 가장 귀찮았던 것이 크로스 브라우징이었는데 디바이스 쪽은 훨씬 고려해야 할 것들이 많았다. 기본적으로 브라우저 대응(iOS -> Safari, Android -> Chrome)및 다양한 해상도와 Notch 등의 디바이스 특성 등을 고려하면서도 전반적으로 데스크톱이 아닌 디바이스이기 때문에 고려해야 할 사항들(보안상 이슈로 인한 동영상 플레이 제한 등)까지 ..

풀이 소와 축사와의 관계를 네트워크 그래프로 정의하는 것이 핵심이 되는 문제였습니다. 가장 많은 축사가 채워지는 것을 Source와 Dest간의 최대 유량을 결정하는 문제로 바꾸어주면 포드-풀커슨 알고리즘을 통해 이 문제를 쉽게 해결할 수 있습니다. 아래 그림과 같이 Source에서 모든 Cow로 가는 간선이 있다고 하겠습니다. (아래 그림에서의 모든 간선의 가중치는 1이 됩니다.) Cow는 선호하는 Cage로 간선을 그릴 수 있으며 Source로부터 들어오는 Cow의 유량은 1이 되므로 여러 Cage로 가는 간선이 있다고 해도 결국에는 하나의 Cage밖에 선택할 수 없게 됩니다. 모든 Cage는 각각 Dest로 가는 가중치 1짜리 간선이 있습니다. 이 그래프에 따르면 가장 많은 우리가 채워지는 경우 =..

풀이 네트워크 유량과 관련된 기본적인 문제로, BFS를 사용하는 포드-풀커슨 알고리즘을 사용하여 구현하였습니다. 포드-풀커슨 알고리즘을 사용하여 이 문제를 해결 할 때의 주의점은, 파이프가 양쪽 모두로 물을 흘려보낼 수 있으므로, 파이프 하나를 양방향 간선으로 취급해야 한다는 점과, 동일한 파이프가 2개 이상 주어질 수 있다는 점입니다. 즉, A->B로 가는 용량 5짜리 파이프와 용량 2짜리 파이프가 동시에 입력될 수 있는데, 둘 중 어느 하나를 선택하는 것이 아니라 두 용량 모두를 더한 것이 A->B로 가는 파이프의 최종 용량이라는 것입니다. 소스 코드 (JAVA) import java.util.*; import java.io.*; /* @sckimynwa */ public class BOJ_6086 ..

풀이 이전 포스팅에서 다루었던 최소 스패닝 트리 문제를 아주 간단하게 응용하여 풀 수 있는 문제입니다. 최소 스패닝 트리를 이전과 마찬가지로 구하고 나서, 최소 스패닝 트리를 잇는 가장 가중치가 큰 간선을 제외하면 가장 작은 비용으로 두 마을을 나누어줄 수 있습니다. 따라서 최소 스패닝 트리를 생성할 때에 추가되는 간선의 가중치 중, 가장 큰 값을 저장해두었다가 트리의 생성 비용에서 제거해주면 됩니다. 소스 코드(JAVA) import java.util.*; import java.io.*; public class Kruskal { public static int[] parent; public static ArrayList edgeList; public static void main(String[] arg..

풀이 최소 스패닝 트리를 구하는 데에는 크게 2가지 알고리즘 (크루스칼 알고리즘, 프림 알고리즘)이 알려져 있습니다. 위 문제는 최소 스패닝 트리의 가중치 값을 묻는 기본적인 문제이기 때문에, 개인적으로 구현하기 편했던 크루스칼 알고리즘을 사용하였습니다. 크루스칼 알고리즘을 사용하기 위해서는 먼저 상호 배타적 집합 (Disjoint Set)을 먼저 구현해야 합니다. 크루스칼 알고리즘은 프림 알고리즘 과는 다르게, 간선을 가중치 순으로 먼저 정렬한 후에, 가중치가 작은 간선부터 이어 나가면서, 해당하는 간선의 두 정점이 이미 같은 트리에 속해 있는지를 판단해야 합니다. 예를 들어, 1과 2를 잇는 가중치 1인 간선을 추가하려고 할 때, 1과 2를 이어주는 경로가 이미 존재한다면 해당 간선을 추가해서는 안된..

Overview 펜윅 트리 (Fenwick Tree)는 구간 합을 빠르게 구하기 위해 고안된 자료구조입니다. 결론부터 말씀을 드리면 구간트리의 진화된 형태라고도 할 수 있습니다. 기존의 배열 자체에서 구간 합을 구하기 위해서는 해당 구간을 모두 순회하면서 값을 더해야 하므로 구간 길이에 비례하는 시간이 소요됩니다. O(N)의 시간복잡도를 갖는다는 의미이죠. 이를 더 빠르게 구현하기 위해 고안된 자료구조가 바로 구간트리이며, 구간트리가 갖는 장점을 살리면서 메모리를 훨씬 더 절약할 수 있도록 고안된 자료구조가 바로 펜윅 트리입니다. (구간 트리에 관한 자세한 내용은 구간 트리를 다룬 포스팅을 참고해주세요) Definition 펜윅 트리가 갖는 중요한 아이디어는 구간 합을 구하기 위해서 부분 합만을 빠르게 ..