전체 글

// 2250년, 인류는 지구 뿐 아니라 여러 행성을 다니며 살고 있다.// 이 행성 간을 빨리 오가기 위해 새롭게 터널을 구축하려 한다.// 행성은 (x, y, z) 좌표로 주어진다.// 행성1: (x1, y1, z1), 행성2: (x2, y2, z2)// 이 때 행성간 터널 연결 비용은 min(|x1-x2|, |y1-y2|, |z1-z2|) 로 계산한다.// n 개의 행성 사이를 n-1 개의 터널로 연결하는데 드는 최소 비용을 구하는 프로그램을 작성하세요.// 입출력 예시// 입력:// data = {{11, -15, -15}, {14, -5, -15}, {-1, -1, -5}, {10, -4, -1}, {19, -4, 19}}// 출력: 4/** * 간선 정보부터 만들어야하는 문제임 * * -> ..

[프림 알고리즘]시작 노드에서 출발해 인접 노드를 확인하면서 트리를 확장하는 노드 중심 알고리즘. 인접 리스트를 사용하기 때문에 노드 간의 연결을 효율적으로 확인하기 위해 양방향 간선을 저장.- **임의의 노드에서 시작**- 연결된 노드들의 간선 중 **낮은 가중치를 갖는 간선 선택**- **간선의 개수가 많을 때** 크루스칼 보다 유리- O(ElogV)- PriorityQueue 와 visited 배열 사용- 간선 수가 노드 수 -1 되면 전체 계산이 된 것 착안해서 계산cf) 크루스칼, 프림 모두무방향 그래프를 대상-> 크루스칼은 간선 중심 알고리즘이기 때문에 간선 단방향 저장/** * 기존 답안이나, 잘못 설명된 것이 많은 것 같아서 의아한 점은 주석으로 남김 */// 프림 알고리즘public cl..

[크루스칼 알고리즘]간선을 가중치 순으로 오름차순 정렬하고, 사이클을 검사하면서 최소 신장 트리를 구성하는 간선 중심 알고리즘.간선을 양방향으로 저장할 필요 없이 단방향만 저장해도 충분.사이클 체크 방법 -> 유니온 파인드주로 간선 수가 적을 때 사용O(ElogE) -> 간선 만큼의 정렬 복잡도를 따라감cf) 크루스칼, 프림 모두무방향 그래프를 대상-> 프림은 노드 중심 알고리즘이기 때문에 간선 양방향 저장public class Main { static int parents[]; public static int example(int[][] data, int v, int e) { int weightSum = 0; parents = new int[v + 1]; ..

안녕하세요. 이름을 바꿨습니다. 이제 미더덕이예요. 토이프로젝트에 적용해두었던 Lucy-XSS-Servlet-Filter가 Jakarta패키지를 지원하지 않음에 따라 XSS 방지 기능을 리팩토링하는 시간을 갖게 되었습니다. 이번 기간에 제가 부족한 부분을 많이 느껴 경험했던 이슈를 기초부터 자세히 정리하고 넘어가고자 합니다. 사실 이번 게시글은 XSS 방지에 대한 글이라기 보단 XSS 방지를 해결하기 위해 알아야할 선수 지식들에 대한 정리입니다. [이번 주제에서 다룰 내용들]1.  HTTP - Method & Content-Type2. Spring Web Annotations3. HttpServletRequestWrapper 4. HttpMessageConverter  이번 게시글에선 가장 기초가 되는 ..

public class Main { public static int INF = 1_000_000_000; public static void floydWarshall(int v, int e, int[][] data, int start) { int[][] dist = new int[v + 1][v + 1]; for (int i = 1; i 경유지 k에 대해서 k가 가장 안쪽 루프에 위치하면, i와 j에 대해 이미 선택된 경로가 경유지를 거치지 않고 직접 경로로 결정될 수 있음 */// for (int i = 1; i j (k를 거쳐서 가는 경우가 짧을 때 업데이트) for (int i = 1; i

public class Main { public static class Edge { int from; int to; int weight; public Edge(int from, int to, int weight) { this.from = from; this.to = to; this.weight = weight; } } public static void bellmanFord(int v, int e, int[][] data, int start) { Edge[] edges = new Edge[e]; for (int i = 0; i dist[edge..

public class Main { public static void dijkstra(int v, int[][] data, int start) { ArrayList> graph = new ArrayList(); for (int i = 0; i ()); } for (int i = 0; i pq = new PriorityQueue(Comparator.comparing(node -> node.weight)); pq.add(new Node(start, 0)); //시작 위치 큐에 가중치값 0으로 넣기 while (!pq.isEmpty()) { Node curNode = pq.poll(); /..

- 출발점에서 목표점까지의 최단 경로를 구하는 알고리즘- 한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음- 간선에 음의 가중치가 없어야함- 그리디 + DP 형태- 알고리즘 복잡도 O(ElogV)public class Main { public static void dijkstra(int v, int[][] data, int start) { //그래프 만들기 ArrayList> graph = new ArrayList(); for (int i = 0; i ()); } for (int i = 0; i dp[j]) { minValue = dp[j]; curIdx = ..

// 숫자 7193 은 7193 도 소수이고,// 719, 71, 7 도 각각 소수이다.// n 이 주어졌을 때, n 자리 수 중에 위와 같은 소수를 찾는 프로그램을 작성하세요.// 입출력 예시// 입력 n: 3// 출력: 233, 239, 293, 311, 313, 317, 373, 379, 593, 599, 719, 733, 739, 797public class Main { public static ArrayList result; public static ArrayList solution(int n) { result = new ArrayList(); int[] primes = {2, 3, 5, 7}; // 1의 자리 소수 for (int i = 0; i

// 정수형 n과 m이 주어졌을 때,// 1 부터 n 까지의 정수 중에서 중복 없이 m 개를 고른 수열을 출력하는 프로그램을 작성하세요.// 입출력 예시// n: 3// m: 2// 출력: [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]import java.util.Arrays;public class Main { public static boolean[] visited; public static int[] out; public static void solution(int n, int m) { visited = new boolean[n]; out = new int[m]; permutation(n, m, 0); }..