목록알고리즘 (45)

쫑쫑이의 블로그

백준 2357 최솟값과 최댓값 Java [세그먼트 트리]

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 세그먼트 트리는 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조이다. 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다. 시간복잡도 O(logN) 최솟값, 최댓값을 구해야하므로 2개의 세그먼트 트리를 만들었다 예제 입력으로 최솟값 세그먼트 트리를 만들면 먼저 배열의 크기를 N * 4의 크기로 만든다 ( N보다 큰 2의..
알고리즘/백준 2022. 12. 16. 01:35
백준 5430 AC Java [구현, 파싱]

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제는 어렵지 않은데 입력값을 받는 것과 출력값 만드는 과정에서 많이 힘들었다 1. 입력값을 받을 때 [], 를 처리 2. 출력값을 만들 때 int[]를 reverse 처리 R이 나오면 boolean 값으로 reverse할지 안할지 처리하는 flat으로 사용하고 D가 나오면 left가 right보다 크면 Error처리하고 break한다 크지 않으면 flat에 따라 left 값을 늘리거나, right 값을 줄였다 package gold; import ja..
알고리즘/백준 2022. 12. 1. 01:48
백준 3020 개똥벌레 Java [누적합]

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 동굴에 종유석과 석순을 하나하나 만들어주면 예제가 모두 최대값인 50만 x 20만번으로 시간이 부족하다 그래서 종유석과 석순 배열을 동굴의 높이 크기로 만들어 1이 나오면 0번 인덱스에 1을 추가하고 n이 나오면 n-1번 인덱스에 1을 추가하는 방식으로 갯수를 카운트해줬다 동굴 배열도 높이 크기로 만들고 0번 인덱스를 최상단으로 하여 종유석 전체 갯수 N/2개를 동굴 0번 인덱스에 더하고 종유석 전체..
알고리즘/백준 2022. 11. 30. 01:49
백준 20924 트리의 기둥과 가지 Java [DFS]

https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net 당연히 단방향 간선인줄 알고 풀었다가 틀렸다... 예제 입력이 양방향 간선이고, 루트로부터 dfs로 기둥을 찾고 기둥의 끝 지점부터 다시 dfs로 최장 길이의 가지를 찾는다 루트에서는 간선이 1개이고, 그 다음부터는 2개인 노드들은 기둥이므로 첫 간선만 1개인지 확인하고 나머지는 2개..
알고리즘/백준 2022. 11. 29. 00:52
백준 1068 트리 Java [DFS]

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 예제에 없는 조건만 찾으면 빨리 해결할 수 있다 먼저 루트가 0번 인덱스가 고정이 아니다 어떤 노드의 자식 노드가 제거됐을 때 남은 자식 노드가 없으면 리프 노드가 된다 입력값을 이용하여 먼저 root를 찾아주고 인덱스별 자식 노드를 children에 담아주었다 이 때 삭제될 노드는 자식 노드로 넣어주지 않았다 3번 예제가 루트 노드와 삭제 노드가 같은 경우인데 이런 경우에는 큐에 값을 넣지..
알고리즘/백준 2022. 11. 28. 03:35
백준 11000 강의실 배정 Java [우선순위 큐]

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 우선순위 큐를 2개 만들어 한 우선순위큐는 예제의 첫번째 값을 오름차순으로 하여 만들고 이 큐의 size가 0이 될 때 까지 반복문을 돌려 큐의 peek값보다 작거나 같은 끝나는 시간 값 큐에 있는 값들을 모두 빼고, 강의실 카운트에서 뺀다 하나씩 꺼내고 끝나는 시간 값을 다른 우선순위큐에 오름차순으로 하여 넣고, 강의실 카운트를 더한 후 강의실 최대값과 비교하여 갱신한다 import java.awt.*; import java.io.*; imp..
알고리즘/백준 2022. 11. 27. 00:09
이전 Prev 1 2 3 4 ··· 8 Next 다음