Algorithm (35) 썸네일형 리스트형 세그먼트 트리 기존 구간합을 구하기위해선 범위 안에 있는 모든 배열을 탐색해서 구해야하고 그 때마다 배열을 탐색해야한다. 하지만 세그먼트트리는 다이나믹프로그래밍의 일종으로 작은 단위부터 더해가서 각각 구간들의 합을 저장한다. 구간합은 Binary Tree 와 재귀를 사용해서 만들수가 있다. 구간합을 구하는 Tree 의 크기는 2^k >= N (n은 배열의 수) 를 만족하는 가장 작은 k값을 구하고 2^k *2 한것이 Tree의 크기가 된다. 생각하기싫은 N*4의 크기로 할당하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 public class Segment { static int.. 트리의 지름 트리의 지름을 구하는 방법은 그리디를 이용해서 풀수가 있다. 1. 임의의 노드 a 에서 가장 깊은 노드 b를 DFS or BFS를 이용해서 구한다. 2. b노드에서 가장깊은 노드 c를 찾으면 b-c가 트리의 지름이 된다. DFS를 Stack을 이용해서 풀어보자. https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 재귀함수를 이용하는게 아닌 Stack구조를 이용하여서 문제를 풀어보았다. 기존 DFS 탐색은 Stack 많은 값이 쌓이면 스택오버플로우를 일으킨다. 하지만 Stac.. 유니온 파인드 : JAVA 정의 어떤 그래프에서 서로 인접한 그래프가 있을때 특정 노드 u와 v가 서로 같은 그래프에 있는가를 판별할 때 사용하는 방법이다. graph[i][j] = 1 이라는 것은 서로 연결되어 있다는 뜻이다. 만약 서로 연결되어 있다면 Union 두개의 노드를 같은 집합으로 합친다는 뜻이다. 이때 Find(i) Find(x) 를 하게 되는데 Find는 가장 위에 있는 부모의 값을 리턴하고 재귀과정에서 연결되 Node를 부모 노드에 바로 붙여준다. 이렇게 되면 처음 parent값은 한다리를 거쳐간다는것인데 이렇게되면 parent[x]의 값은 x가속한 집합이라고는 할수 없다. 하지만 각각에대해 Find를 돌리면 find가 재귀적으로 가장 부모노드에 연결시켜주므로 값이 제대로 나오는 것을 확인 할 수 있다. 소스코드.. 정렬 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 package test; import java.util.Arrays; import java.util.Comparator; public class test { public static class Chemi implements Comparable{ int x; int y; public Chemi(int x, int y) { super(); this.x = x; this.y = y; } @Override public int compareTo(Chemi o) { // TODO Auto-gener.. 특정 Map 회전 시키기 기본 Map 0 1 2 3 4 5 6 7 8 90도회전 6 3 0 7 4 1 8 5 2 조건을 찾아보면 Map[0][0] = Map[0][2] Map[0][1] = Map[1][2] Map[0][2] = Map[2][0] 가운데 인덱스는 서로같고 양쪽 합은 행렬의 lengh -1 과 같다. turnRight 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public static void turnRight(int[][] m) { int n = m.length; int copy[][] = new int[n][n]; for(int i=0;iColored by Color Scripter JAVA : Log 함수를 이용한 자리수 구하기 Math.log10 함수를 이용한 자리수 구하기. 1 2 3 public static void main(String args[]) { System.out.println((int)Math.log10(213)+1); } http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter Log10 값은 승수를 구해준다. 1은 10^0 10 은 10^1 100은 10^2 50은 1.69 정도 나온다.. 따라서 Math.log10을 이용한 값에서 (int)형으로 변환해서 소수를 제거후 +1 해주면 빠르게 자리수를 구할수 있다. 부분집합의 조합 구하기 : JAVA 부분집합의 모든 조합 구하기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 package com.ssafy.algo; public class Test69 { public static void main(String[] args) { int[] A = { 1, -2, 3, -4, 5, -6, 7, -8, 9 }; int cnt = 0; //부분집합의 개수 for (int i = 0; i 이전 1 2 3 4 5 다음
