hail2y.log

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  다익스트라(Dijkstra) 알고리즘출발 노드와 모든 노드 간의 최단 거리 탐색 (출발 노드와 도착 노드, 두 노드만이 아님)에지(가중치)는 모두 양수여야 한다시간 복잡도는 O(E * logV)그리디 알고리즘- 접근 방법그래프를 인접 행렬, 인접 리스트로 구현할 수 있지만 일반적인 경우에서 인접 리스트가 더 빠름, 하지만 상황에 따라 달라짐- 인접 행렬 O(V^2) - 밀집 그래프에 유리, 연결 노드 확인하는 데 O(1)- 인접 리스트 O(E * log V) - 희소 그래프에 유리, 연결 노드 확인하는 데 O(연결된 간선의 수)최단 거리 배열을 초기화 (최댓값으로 모두 채우기)거리 배열에 출발 노드 인덱스에 0..

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  이 글은 증명보다는 방정식의 해를 구할 때 어떻게 접근해야 하는지 설명한다.유클리드 호제법이 두 수의 최대공약수를 구하기 위한 것이라고 보면, 확장 유클리드 호제법은 방정식의 해를 구하는 것이라고 볼 수 있다. 이름에서 알 수 있듯이 확장 유클리드 호제법은 기본 호제법을 알고 있어야 진행된다ax + by = c주어진 a, b, c, x, y는 모두 정수라고 생각한다. 이때 x, y의 해는 c % gcd(a,b) = 0 조건이 성립되어야 정수해를 구할 수 있다. 그렇기 때문에 문제에 접근할 때 먼저 c의 값이 gcd(a,b)의 배수가 맞는지 확인부터 해야 한다. 배수가 맞다면 일차 조건은 만족한 것이다. c가 g..

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  오일러 피 함수 P[N]코딩 테스트에 자주 나오지는 않으나 알고 있어야 보임1부터 N까지 범위에서 N과 서로소인 자연수의 개수원리는 에라토스테네스('배수를 제거한다'는 원리)와 비슷다른 점은 현재 배열의 값이 소수일 때, 그 배수를 제거하기 위해 배열의 끝까지 P[i] = P[i] - (P[i] / K) 연산을 수행한다는 것(K는 현재 선택된 수, i는 K의 배수)이 과정은 N에서 해당 소인수 K의 배수를 제거하고 남은 수의 개수를 반영한다실제 구현할 때는 N까지를 배열로 구현하지 않아도 되는데, 1부터 N까지의 서로소 개수를 result 변수로 생각하는 것이다. 그래서 처음에 N을 넣고 K를 2부터 시작해 N..

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  분할 정복(divide and conquer) 방식: 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘가장 작은 데이터 집합(크기 1)으로 나눈 후 2개의 그룹을 합치면서 정렬2개의 그룹을 합칠 때는 투 포인터를 이용하여 둘 중 더 작은 수를 결과 배열에 먼저 저장그런 다음 포인터를 1씩 증가시키는데, 어느 한 포인터가 배열의 끝에 먼저 도달하면 나머지 배열의 값들도 옮겨 붙임   시간 복잡도는 평균 O(nlogN)- 크게 보면 row 하나 당 n번의 데이터 접근- 병합 과정에서 logN번만큼 정렬버블 정렬(swap)과 연관지은 핵심 아이디어- 버블 정렬에서는 swap이 몇 번 일어날까- 첫째 줄에서 5..

모판을 만들어서 푸는 문제가 많이 나온다.구간합을 미리 다 구해놓은 합 배열을 만든다. https://www.acmicpc.net/problem/1292  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ1292_ans { public static void main(String[] args) throws IOException { int[] t = new int[1001]; // 0, 1, 2, 2, 3, 3, 3 ... int idx = 1; for (..