PS (81) 썸네일형 리스트형 [Java] 백준 2533번 사회망 서비스 - Dynamic Programming https://www.acmicpc.net/problem/2533 부모 노드가 adapter인 경우와 그렇지 않은 경우를 나누어 dp[n][1], dp[n][0] 로 구분해 dp를 적용한 것이 인상깊었다. import java.util.*; import java.io.*; public class g3_2533_adapter { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(System.out); static Node[] nodes; static int n; static int[][] dp; public static void main(String[] args) { n = fs.nextInt(); nodes.. [Java] 백준 3653 영화 수집 - Lazy Segment Tree https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net leaf 노드의 경우 좌측부터 i번 영화가 node[i] 번째에 놓여있도록 하였다. 하지만 탐색 회수를 최적화하기 위해 해당 노드를 root로 가지는 트리에 대하여 mintree, maxtree로 나누어서 mintree[node] >= v 라면 그 트리는 놓여있는 위치의 값을 더해선 안되므로 return maxtree[node] < v 라면 그 트리의 모든 노드는 1을 더해주므로 minla.. [Java] 백준 10999번 합 구하기 - Lazy Segment Tree https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net import java.util.*; import java.io.*; public class p5_10999 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(System.out); static int n, m; static long.. [Java] Index Tree / Segment Tree Lazy Propagation https://www.acmicpc.net/blog/view/26 세그먼트 트리 나중에 업데이트 해야지! 글이 업데이트 되었습니다. https://book.acmicpc.net/ds/segment-tree-lazy-propagation 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제가 있습니다. 10999번 문제: 구간 합 구하기 2 구간 l, r (l www.acmicpc.net https://steady-coding.tistory.com/129 [BOJ] 백준 6549번 : 히스토그램에서 가장 큰 직사각형 (JAVA) 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그.. [Java] Segment Tree https://www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 글이 업데이트 되었습니다. https://book.acmicpc.net/ds/segment-tree 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + .. www.acmicpc.net https://steady-coding.tistory.com/126 [BOJ] 백준 2357번 : 최솟값과 최댓값 (JAVA) 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와.. [Java] 2-Dimentional Fenwick Tree https://uldada.tistory.com/3 2차원 펜윅트리 이해하기(2-dimentional Fenwick Tree) 펜윅트리는 비트연산을 통해 빠른 시간에 구간합을 구하는 배열 형태의 트리이다. 이 글에서는 2차원 펜윅트리만을 설명하고 있다. 1차원 펜윅트리에 대한 이해가 필요하면 블로그 내 펜윅트리 uldada.tistory.com 해당 칸이 들어가는 tree 칸에 대해 전부 들어가야 하므로 각 x row에 대해 모든 y col 칸의 업데이트가 필요하다. static void update(int x, int y, int v){ while (x 0){ sum += tree[x][temp_y]; temp_y -= (temp_y & -temp_y); } x -= (x & -x); } return .. [Java] TSP (Traveling Salesperson Problem) - 모든 노드를 지나는 최소 길이 사이클 https://withhamit.tistory.com/246 외판원 순회(TSP: Traveling Salesperson Problem) 외판원 순회(TSP: Traveling Salesperson Problem)란 도시들이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발 도시로 돌아왔을 withhamit.tistory.com 가장 중요한 점 1. 어느 지점에서 출발해도 결국 같은 사이클이 완성될 것이다. 2. 이동 불가능한 간선일 경우 INF(정말로 Integer.max_value면 오버플로우 나니까 적당히 조절) 3. 특정한 visit 상태에서의 now가 이미 탐색되었을 경우 바로 dp[visit][now]를 return publi.. [Java] 백준 2098번 외판원 순회 - TSP, 비트필드 DP https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net - 현재까지 방문한 도시 번호에 대한 정보를 비트마스킹 (visit) - wei는 a 도시에서 b도시로 갈 때의 거리 dp는 visit 상황에서 now 도시에 있을 때 목적지까지 가질 수 있는 최소 거리값 - 모든 도시를 방문하는 사이클이 단 1개 생기기 때문에 어느 도시를 시작점으로 잡아도 답은 같다. ==> 0번 도시를 시작점으로 잡아도 된다! 처음에는 N.. 이전 1 2 3 4 5 6 ··· 11 다음
