공부(2018~2019) - 스킨변경전

2357번 최대값과 최소값 기본 세그먼트 트리 알고리즘 문제, 재귀를 활용하기는 방법을 배우기에 좋은 문제라 생각한다 처음에 Max Min을 한번에 2차원 배열로 처리하려고 했는데 Min을 할때 Max의 재귀가 다시 돌아간다는 것을 생각하지 못했다. Max와 Min을 분리해서 처리를 하였다. 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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 ..

1. 2042번 구간 합 구하기Segment Tree를 활용하는 문제, 인덱스의 범위, 구간의 범위에 대한 생각이 필요한 문제123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer; public class Main { stat..

1. 11004번 K번째 수기본 정렬 문제, Arrays.sort를 사용하면 간단하지만 Quick, Merge 정렬을 직접 만들어서 해결하는 것이 좋을 것 같다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Stri..

1. 1074번 Z분할 정복 문제, 큰 배열을 4등분씩 작게 분할하여 원하는 값을 찾는 문제, 큰영역을 분할 하다보면 결국 마지막은 하나의 영역이 된다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static int count = 0; public static void main(String[] args) throw..

1. 10815번 숫자카드기본 이진탐색 문제, 이진탐색은 임의의 중간지점을 선택하고 찾고자 하는 값과 대소비교하여 반복적으로 찾는 알고리즘 ( O(log N) ) 자바에서는 [Arrays.binarySearch(배열, 찾는 값) return 위치] 함수가 존재한다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokeni..

1. 2263번 트리의 순회트리 순회 문제, 전위 후위 중위 순회를 정확하게 알고 있어야 풀 수 있는 문제중위 순회의 순서와 후위 순회의 값을 이용하여 전위 순회에 접근 할 수 있다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static int[] idx = new int[100001]; public static void main(Str..

1. 1735번 분수 합유클리드 호제법 문제1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br =new BufferedReader(..

1. 2579번 계단 오르기DP문제, 처음에는 DFS로 접근하였는데 시간초과가 발생하였다. 최대의 계단이 300개 인데 이때 수많은 경우가 발생한다. 문제에 주어진 조건을 자세히 확인한다음 경우의 수가 얼마나 발생하는지 보고 DP인지 다른 알고리즘인지 판단하는게 좋을 것 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class..

1. 11404번 플로이드기본 플로이드 워셜 알고리즘 문제, 3중 for문을 이용하여 처음 반복은 직선이 아닌 거쳐가는 부분을 뜻하며 두 세번째는 직진루트이다.모든 경로에 대한 최단거리를 구할 때 사용한다. 시간복잡도 O(V^3)모든 경로에 대한 우회루트를 계산하여 가장 작은 값을 최단경로로 사용한다12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; publi..

1. 1922번 네트워크 연결 기본 MST 문제, 정점 수 - 1 개의 간선으로 모든 정점이 연결 되는 지(최저비용으로 연결) 문제는 모두 MST 알고리즘을 사용하면 된다. Prim 알고리즘이 약 180ms 정도 빨랐다. ( Prim O( Edge log Vertex) , Kruskal O( Edge log Edge ) Prim 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889import java.io.BufferedReader;import java.io..

1. 11779번 최소비용 구하기2최소비용 구하기에서 경로와 정점개수를 추가로 출력하는 문제 (다익스트라)주의할점은 경로가 최단거리로 바뀔 수 있기 때문에 유동적으로 배열의 인덱스를 활용해서 접근해야한다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107import java.io.BufferedReader;import java.io.IOException;import java.io..

1. 1916번 최소비용 구하기(Dijkstra) 다익스트라 알고리즘 문제, for문을 이용하는 방법과 우선순위 큐를 이용하는 방법이 있는데 우선순위 큐를 사용하는 것이 좋다. 다익스트라는 시작정점에서 인접정점의 가중치가 가장 최소가 되는 선택하는 그리디 알고리즘이다. 시작정점 -> 인접정점들의 정보 -> 최저비용 정점으로 이동 -> 인접정점들의 정보 -> 업데이트(경유할 때 더 최소비용일 경우) 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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 ..