hail2y.log

책 [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 (..