전체 글
-
[JAVA] 구간 합, 차를 빠르게 구할 수 있는 세그먼트 트리얼렁뚱땅 JAVA 알고리즘 2023. 4. 14. 00:18
문제가 쉽다. != 내가 실력이 늘었다. 그저 시간을 빡세게 잡기 때문에 내가 생각한 방법으로는 통과될 수 없는 것이다. 구간 합, 차와 같은 문제를 실제로 만나면 나는 Prefix Sum으로 주로 문제 해결을 하고자 한다. 그런데, PrefixSum은 특정 구간의 합을 구할 때 O(1)이라는 장점은 분명하게 존재하지만, 단점은 중간 값을 수정한다면 O(N)의 시간이 걸린다는 단점이 존재한다. 그래서 저걸로 풀면 시간초과 뜰 때가 있다. 여기서 배워야 하는 것이 세그먼트 트리다. 세그먼트 트리의 갱신은 O(NlogN)으로 시간을 줄일 수 있다. 몰라 ? 일단 외워. import java.util.*; import java.io.*; class SegmentTree { long [] tree; int tr..
-
[JAVA] 최소 거리를 찾아주는 다익스트라 알고리즘얼렁뚱땅 JAVA 알고리즘 2023. 4. 12. 11:30
조건 1. 음수인 거리가 있으면 안됨 (무조건 양수) 시간복잡도 : O(ElogV) 웬만하면 PQ + 다익스트라로 접근하면 좋을 거 같음 (그렇다고 우선순위 큐를 사용했을 때, 기본 다익스트라 알고리즘보다 절대적으로 속도가 빠른건 아님) (근데 그게 어느경우인지 아직 잘 모르겠음 ㅜ) (문제 자체도 비공개 문제이고 나만 알아보면 되니까 좀 코드가 친절하지 않음ㅎ_ㅎ) (혹시 검색으로 들어오시는 분이 계시다면 죄송합니다 구냥 여긴 저의 메모장입니다 ㅜ) 그래도 간단히 써보자면 mStart라는 노드에서 다른 노드로 갈 때 최소시간이 얼마인지를 cost라는 배열에 정리한 것 임다. PriorityQueue pq = new PriorityQueue(); int [] visited = new int[n]; int..
-
[JAVA 백준 문제풀이] 얼렁뚱땅 1717번 집합의 표현 풀이얼렁뚱땅 JAVA 문제풀이 2023. 3. 29. 20:12
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net import java.util.*; import java.io.*; public class 집합의표현_1717 { static int n; static int [] rank; static int [] arr; public static int find(int x) { if(arr[x]==x) { return x; } else { int y = find(arr[x..
-
[JAVA] 동일한 그룹이 뭔지 확인하는 알고리즘 Union-Find얼렁뚱땅 JAVA 알고리즘 2023. 3. 29. 19:50
동일한 그룹이 뭔지 확인하기 위해 기존에는 dfs/bfs 방식만 알았다면, 그것보다 효율적인 Union-Find 알고리즘에 대해 정리하고자 한다. 아래는 예전에 파이썬으로 풀었던 문제인데, 이땐 dfs/bfs로 아마 풀었을 것이다. 새롭게 Union-Find, JAVA로 풀어보았다. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net import java.io.*; import java.util.*; public class Union_find_Study..
-
아씨 일단 외워얼렁뚱땅 내 일상 2023. 3. 24. 10:49
오늘 시험에서 우선순위 큐가 나올까 ? 안나올까 ? ㅜ 아아아아아아아 프로시험 진짜 너무 어려운데 살려주세요 ㅜㅜㅜㅜㅜㅜㅜㅜㅜ 우선순위 큐 작성하는 법 이따 인재개발원 가면서 봐야하니까 여기에다 올려놓는다. 우선순위 큐 외워라 밍쟈밍쟈밍쟈 할 수 있다 밍쟈밍쟈밍쟈 https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90 [Java] Priority Queue(우선 순위 큐) PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터 ve..
-
[JAVA] 순서가 있는 트리에서 위상정렬얼렁뚱땅 JAVA 알고리즘 2023. 3. 22. 16:49
단, 비순환 그래프임이 가정되어야 함. import java.io.*; import java.util.*; public class 작업순서 { static ArrayList as; static int n; static int m; static int [] visited; static int [] count; static ArrayList [] al; public static void topo() { ArrayList q = new ArrayList(); for(int i=1;i
-
[JAVA] Rabin-karp 알고리즘 - 동일 패턴 유무 찾기얼렁뚱땅 JAVA 알고리즘 2023. 3. 15. 11:10
가장 쉽게 생각할 수 있는 무지성으로 비교하기 String : ababc Pattern : abc Step 1. aba != abc Step 2. bab != abc Step 3. abc == abc Step 3에서 존재한다고 빠르게 파악할 수 있을 것이다. 각 Step에서 사람처럼 한번에 딱 보면 O(1)의 시간이 걸릴 거 같지만, 사실은 아니다 한 str1과 str2를 비교하기 위해서는 한글자 한글자 비교한다. 예를 들어 JAVA의 str1.equals(str2)를 사용한다면(Step 1) a == a true b == b true a != c false 으로 Step 1은 False라고 판단하는 것이다. 다시 말해, 글자 하나하나 보기 때문에 글자가 크거나 하면 시간이 매우 오래 걸린다. 이것을 해..