전체 글 (84) 썸네일형 리스트형 [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.. [Java] CCW (Counter Clock Wise) - 세 점의 방향성 파악 https://travelbeeee.tistory.com/45 [알고리즘] 세 점의 방향성 파악하기 'CCW 알고리즘' 안녕하세요. 여행벌입니다. 오늘은 세 점이 주어졌을 때, 방향성을 파악할 수 있는 CCW 알고리즘에 대해 다뤄보겠습니다. 다음과 같이 세 점 A, B, C 가 있을 때, 세 점의 방향성을 시계방향 / 반시 travelbeeee.tistory.com 반시계 방향 : 1 시계 방향 : -1 일직선 : 0 static int ccw(Node n1, Node n2, Node n3){ long s = (n1.x * n2.y + n2.x * n3.y + n3.x * n1.y) - (n1.y * n2.x + n2.y * n3.x + n3.y * n1.x); if (s > 0) return 1; el.. [Java] 백준 17387번 선분 교차 2 - CCW https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 한 문제 푸느라 반나절이 날아갔다... 처음에는 수학적으로 접근하려 했는데 double을 쓰다보니 범위를 감당할 수 없어져서 CCW 알고리즘임을 알았다. case work에 실수가 많아서 시간이 많이 들었다. import java.util.*; import java.io.*; public class g2_17387 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWr.. [Java] 백준 12094번 2048 (Hard) - 빡구현 https://www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 12100번 2048(Easy)와 유사하지만 수행이 5번인 easy와 다르게 10번이나 되어서 빡센 가지치기가 필요했다. 3시간 걸림; import java.util.*; import java.io.*; public class p4_12094 { static FastScanner fs = new FastScanner(); static PrintWriter pw = ne.. [Java] Topological Sort(위상 정렬) - 방향성 있으며 사이클 없는 그래프 https://bcp0109.tistory.com/21 위상정렬 Topological Sort (Java) 위상정렬 연습 문제 1 연습 문제 2 위상 정렬은 그래프 정렬을 말합니다. 그래프의 순서를 정렬하기 때문에 조건이 있습니다. 위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사 bcp0109.tistory.com 필요한 정보 1) 각 노드가 가리키는 노드 번호에 대한 정보 2) 각 노드를 수행하기 전에 탐색되어야 하는 노드의 개수 (inDegree) 3) 탐색 시작 시점에 inDegree == 0인 노드 (출발 노드의 위치, 개수) 사이클 유무 확인 방법 탐색한 노드들을 Answer Queue에 넣어놓았을 때 크기가 n보다 작다면 => 사이클이 존재! [Java] 백준 2623번 음악프로그램 - 위상 정렬 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net import java.util.*; import java.io.*; public class g2_2623 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(System.out); static int n, m; static List list = new ArrayList(); st.. 이전 1 2 3 4 5 6 7 ··· 11 다음