[JAVA] 신발끈 공식 좌표평면상의 좌표로 구성된 다각형의 면적을 구하는 공식이다. 좌표값이 다갹형을 구성하는 시계 또는 반시계 방향으로 주어져야 사용 가능하고 변이 교차하는 경우는 사용할 수 없어 쓰임새가 제한적이다.(다시 볼 일 없다는 뜻) 계산법은 위 그림과 같이 [{(적색 화살표의 곱의 합) - (청색 화살표의 곱의 합)} / 2] 이다. public class Main { static BufferedReader br; static StringTokenizer st; static StringBuilder sb; public static void main(String[] args) throws Exception { // 사용 예 Point[] pArr = new Point[4]; .. [JAVA] 그래프와 다익스트라 DFS를 쓰면 시간 초과가 나고, BFS를 쓰면 메모리 초과가 나서 문제 분류를 보면 DP거나 다익스트라였던 적이 있는가?고통받은 김에 정리해봤다. class Graph { Deque[] dqArr; // 연결 노드를 저장할 자료구조 int nodeCount; // 노드 개수 public Graph(int nodeCount) { // 그래프 선언 this.nodeCount = nodeCount; dqArr = new Deque[nodeCount + 1]; for (int i = 0; i (); } void addEdge(int start, int dest, int cost) { // 그래프에 간선 추가 dqArr[start].add(new Node(dest, cost)); } .. [C#, JAVA] n이하의 소수 리스트 소수는 알고리즘 문제의 단골 손님인데, 보통 시간 초과에 막히는 문제가 많다. 따라서 소수 판별 시간을 줄이는 것이 일순위인데 아래 코드에선 소수의 두 가지 성질을 이용했다. 1. 어떤 수를 그 수의 제곱근보다 작은 소수들로 나눴을 때 나누어 떨어지지 않는다면 그 수는 소수이다. 2. 2를 제외한 모든 짝수는 소수가 아니다. 더 빠른 방법을 찾을 시 수정 using System; using System.Collections.Generic; class Program //사용 예 { static void Main(string[] args) { Prime p = new Prime(); p.makePrime(100); List list = p.getList; foreach (long l in list) Cons.. [C#] 세그먼트 트리 코딩을 할 때 시간을 단축하기 위해 메소드를 호출해서 사용하듯이 비슷한 문제를 풀 때마다 같은 알고리즘을 짜는 건 시간낭비이다. 따라서 알고리즘 도장을 파서 적재적소에 활용하고자 한다. 세그먼트 트리는 단말 노드에 값들이 저장되고 그 부모노드엔 단말 노드의 값들을 조합한 결과가 저장되는 트리이다. 예를 들어 노드의 합을 저장하는 세그먼트 트리라면, 단말 노드의 일부가 1 / 2 || 3 / 4라면 부모 노드엔 3 / 7이 저장되고 그 부모 노드엔 10이 저장된다. 그리고 뿌리 노드엔 모든 단말 노드의 합이 저장된다. 따라서 어떤 데이터들이 주어질 때, 세그먼트 트리를 만들면 데이터의 특정 구간의 연산(합, 곱, 최대, 최소 등)이 가능하다. 노드의 합 세그먼트 트리: update는 해당 값을 완전히 바꾸.. 이전 1 다음
