Algorithm (35) 썸네일형 리스트형 코딩테스트 자주사용하는 코드 (JAVA) 여러 코딩테스트를 하다보면 VS Code, 이클립스같은 IDE를 사용하지 못하는 코딩테스트가 있다. 또한 요즘 코로나로 퍼지면서 실시간 녹화와 원격으로 감시하기 때문에 검색을 하거나, IDE의 자동완성에 대한 힘을 빌리지 못한다. 그렇기 때문에 여러가지 코드들을 공유하고자 한다. Import import java.util.*; import는 java.util.* 하나만 선언하면 대부분의 라이브러리 함수, 콜렉션 함수들을 사용할 수있다. 코딩테스트시 이거하나 선언하고 시작하면 함수를 찾지 못한다는 에러는 만나지 않을 것이다. Sort 함수 int[] arr = {1,3,4,5,6}; Arrays.sort(arr); 정말 자주 사용한다. Math 함수 int answer = 1; answer = Math.m.. 레드 블랙트리 레드블랙 트리 규칙 4가지 1. Root Property : 루트 노드의 색깔은 검정(Black) 2. External Property : 모든 external Node 들은 검정(Balck) external Node : 자식이 없는 노드 3. Internal Property : 빨강(Red) 노드의 자식은 검정(Balck) == No Double Red(빨간색 노드가 연속으로 나올수 없다.) 4. Depth Propery : 모든 리프노드에서 Black Depth는 같다. == 리프노트에서 루프노드까지 가는 경로에서 만나는 블랙 노드의 개수는 같다. 위의 4가지 규칙을 지키는 이진 트리는 Red Black Tree 라고 한다. AVL Tree 보다 Blance 제약이 느슨하기 때문에 삽입 삭제 수정에 .. CCW 세 점이 시계방향인지 평행하는지 반시계방향인지 확인할때 쓰는방법 또한 ccw의 크기의 /2 는 세점으로 하는 삼각형의 크기라는 것을 알 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 package algo; import java.util.Scanner; public class B11758 { static class Pair { int y; int x; public Pair(int x, int y) { super(); this.y = y; this.x = x; } } static int ccw(Pair a, Pair b, Pair c) { int.. 강한 연결 요소 java 업데이트 예정 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 package algo; import java.io.BufferedReader; import java.io.IOException; import java.i.. 트라이(Trie) : JAVA / 백준 5052 트라이 알고리즘 일반 적인 정수들은 O(1) 시간내에 비교가 가능합니다 . 1==1 ,123>4 처럼 단순연산으로 접근 할 수 있습니다. 하지만 String 같은경우에는 "ABC" == "ABCD" 를 고려하기 위해서는 최대 문자열의 길이 O(M) 시간이 걸립니다. (첫 번째 인덱스부터 계속 비교해 나가야 되기 때문입니다.) 따라서 기존 이진 트리로 정수형 데이터를 찾는데 걸리는 시간이 O(logN) 이라고한다면 문자열의 경우에는 O(MlongN) 시간이 걸리게 됩니다. 하지만 트라이 알고리즘을 사용한다면 O(M) 시간내에 자료를 찾을 수 가 있습니다. 문자열 집합 S={"BE","BET","BUS","TEA","TEN"} 을 트라이 자료구조로 표현하면 다음과 같습니다. 여기서 주황색으로 표시된 Node.. 이분 매칭 알고리즘 ( JAVA),열혈강호1,2,3 문제 이분 매칭 알고리즘이란 용량이 1인 이분 그래프에서 최대로 매칭 할수 있는 수를 구하는 알고리즘이다. 기본적으로 DFS알고리즘을 사용한다. 알고리즘 매커니즘 기본 적으로 1~N 노드 까지 DFS 탐색을한다. 이때 각각의 노드마다 Dfs탐색을 한다. 1. 현재 here 노드에서 연결된 there 노드가 방문하지않았으면 there은 here과 이어젔다고 표시한후 true를 반환 2. 만약 there이 누군가와 연결되었다면 there과 연결한 간선을 다시 Dfs탐색하여 다른것과 매칭 할수 있는지 탐색 만약 할수 있다면 here과 there을 이어준다. 그리고 true를 반환한다. 3. 위에 1, 2 번으로 이을수 없다면 false를 반환한다. 4. 1 2 3 을 1~N 번 노드 까지 반복한다. 그때마다 Dfs.. 포드-폴커슨 인접리스트 구현하기 JAVA 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 package 개인공부; import java.util.ArrayList; import 개인공부.포드폴커슨_인접리스트.Edge; public class 포드폴커슨_인접리스트 { static class Edge { int target, capacity, flow; // 역방향 정보를 넣을 곳 Edge reverse; public Edge(int target, int capacity, int flow) { super(); this.target .. 네트워크 유량 ( network flow) / 포드 - 풀커슨 알고리즘 JAVA network flow는 실세계에서 적용이 가능한 유명한 알고리즘이다. network flow를 이해하기 위해서는 먼저 몇가지 용어 정리가 필요하다. A -> B 로가는 네트워크에 대해서 최대 x라는 트래픽으로 보낼 수 있다면 capactiy(a,b) = x 가된다. 즉 a->b로 보낼 수 있는 최대 용량은 x라는 뜻이다. 만약 a->b에서 실제 y라는 트래픽이 발생한다면 flow(a,b) = y 가된다. 즉 a->b로가는 유량은 y라고 한다. 여기서 몇가지 속성을 알아보자 1. 용량 제한 속성 flow(u,v) 0 을 만족하는 u v 간선을 경로라고 생각하고 BFS 너비우선 탐색으로 경로를 탐색한다. 3. 만약 경로가 없으면 알고리즘은 종료한다. 4. 만약 경로가 존재한다면 경로에서 가장작은 flow .. 이전 1 2 3 4 5 다음
