https://www.acmicpc.net/problem/2042알고리즘 분류 : 자료 구조, 세그먼트 트리 ❓문제🔅해석세그먼트 트리를 이용하는 가장 기본적인 문제이다.인덱스 트리 생성 - init인덱스 트리의 리프 노드에 배열을 담아야 하므로 리프 노드가 시작하는 인덱스 번호를 알아야한다.리프 노드의 개수를 S로 표현하고 S는 N 이상의 2^n으로 표현 가능한 수여야 한다.따라서 S 는 아래와 같이 구한다. (N은 주어진 배열의 크기)S = 1;while (S 리프 노드에 배열에 적혀있는 수를 넣기위해 S번째부터 넣는다.그 외 내부 노드는 S - 1번째부터 자식 노드(왼쪽, 오른쪽) 합을 대입한다.private static void init() { // leaf노드 채우기 for (in..
https://www.acmicpc.net/problem/1927알고리즘 분류 : 자료 구조, 우선순위 큐직접 힙을 구현하여 풀이하였습니다. ❓문제🔅해석직접 힙을 구현하여 풀어본 문제이다. 최소 힙은 ' 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.'는 힙 조건을 가진다.힙 조건에 맞춰 삽입과 삭제 연산을 진행한다. 삽입 연산트리의 가장 마지막 위치에 노드를 삽입한다.추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다.만족하지 않는다면 부모와 자식의 키 값을 바꾼다.조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2 ~ 3을 반복한다. 입력을 받다가 '0'을 만나게 되면 삭제 연산을 수행한다. 삭제 연산힙의 삭제 연산은 항상 루트 노드를 삭제한다.트리의 가장 마지막 노드를 루..
https://www.acmicpc.net/problem/2805알고리즘 분류 : 이분 탐색, 매개 변수 탐색 ❓문제🔅해석투포인터와 비슷하게 세개의 포인터로 문제를 푼다.1 ~ 트리의 최대값까지의 배열을 만들어 start = 1, end = 트리의 최대값, mid = (start / end) / 2 로 초기화한다.mid 값을 현재 절단기 높이라고 생각하고, 입력받은 트리의 순회하면서 mid 값을 각각 빼주고 sum에 더한다. sum이 목표값보다 크다면 나무를 더 많이 잘랐다는 뜻으로 절단기 높이를 높이기 위해 start 값을 mid + 1로 설정한다.반대의 경우, end = mid - 1로 설정한다. 다시 mid = (start + end) / 2로 설정해고 위와 같이 트리를 순회하면서 절단된 나무들..
정렬정렬을 통해 유일성 검사 및 중복 제거가 가능하다.정렬된 데이터를 한번씩만 확인하면 각 숫자의 빈도 수를 확인할 수 있다. 정렬 방법1. Arrays.sort() - 오름차순int[] arr = {5, 3, 2, 8, 1};Arrays.sort(arr);System.out.println(Arrays.toString(arr)); // [1, 2, 3, 5, 8] - 내림차순Arrays.sort(arr, Comparator.reverseOrder());System.out.println(Arrays.toString(arr)); // [8, 5, 3, 2, 1] 2. 사용자 정의 정렬 (Comparator)Integer[] arr = {5, 3, 2, 8, 1};Arrays.sort(arr, new Com..
https://www.acmicpc.net/problem/2003 알고리즘 분류 : 브루트포스 알고리즘, 누적합, 투포인터❓문제🔅해석두 수의 합이 특정 값이 되는 경우를 찾는 문제로 투포인터를 이용한다.입력받은 숫자를 배열에 넣고 low pointer와 high pointer로 합을 구한다. //입력10 51 2 3 4 2 5 3 1 1 2 1) 초기화 및 sum 두개의 포인터 모두 0번째 인덱스부터 출발하고 sum은 0번째 인덱스 값으로 초기화해준다.sum이 특정 값(M) 5보다 작으므로 high pointer를 +1 해준다. 그리고 sum에 증가된 high 번째의 값을 더한다. 2) sum == M sum == M 이 될 때, cnt++ 해주고 low 또는 high을 +1 해준다. 그리고 su..
https://www.acmicpc.net/problem/1713알고리즘 분류 : 구현, 시뮬레이션❓문제🔅해석학생 객체에 학생 번호, 추천 수, 타임스탬프를 저장하여 조건에 맞게 정렬을 한다. Student[] students = new Student[101]; //학생 번호는 1부터 100까지의 자연수이다.학생 객체를 담는 배열을 만들어 학생 번호와 배열 인덱스를 맞춰 저장한다.예를 들어, 2번 학생이 추천을 받았을 때 배열 2번째에 학생 객체가 존재한다면 이미 추천받아 저장되어 있다는 것이다.이 때는 해당 객체의 추천수를 증가시킨다. List photos = new ArrayList(); // 사진틀의 개수 N를 저장한다.배열이 비어있다면 사진틀 리스트에 추가해준다.이 때 사진 틀이 꽉 찼을 때, ..
https://www.acmicpc.net/problem/1256알고리즘 분류 : 수학, 다이나믹 프로그래밍, 조합론❓문제🔅해석'a'와 'z'의 조합으로 n번째 단어를 출력하는 문제이다.사전에는 알파벳 순서대로 수록되어 있으므로 'a'로 시작하는 문자의 조합으로 계산해본다.입력 : 2 2 6 1. a_ _ _ 'a'로 시작하는 문자의 조합 개수는 남은 3자리수와 남은 'z'의 갯수 3C2이다. 3C2 = 3이므로 'a'로 시작했을 때 3가지의 조합을 만들 수 있다.우리는 6번째(K) 순서를 원하므로 'z'로 시작한다는 것을 알 수 있다. (3C2 1) 결과값을 담는 sb에 'z'를 추가하고2) 'z' 카운트를 하나 감소시킨다.3) K의 값을 조합 수 만큼 감소시킨다. 2. z a _ _위에서 'z'로 ..
https://www.acmicpc.net/problem/1837알고리즘 분류 : 수학, 브루트포스 알고리즘, 임의 정밀도 / 큰 수 연산❓문제🔅해석K까지의 소수배열을 만들기 위해 '에라토스테네스의 체'를 활용한다.//에라토스테네스의 체 생성for (int i = 2; i 이중 for문을 돌면서 자신의 배수에 방문 체크를 하여 지워준다. 해당 소수에 암호가 떨어진다면 K보다 작은 소수로 만들어진 암호이므로 소수 배열을 돌면서 입력받은 암호를 나눠본다.주의할 점은, 암호가 10의 100승까지 입력될 수 있어 int, long으로 입력받을 수 없다.BigInteger를 사용하는 방법도 있지만, String으로 입력받아 한 글자씩 연산을 진행하는 방법도 있다.(어떤 문제에는 BigInteger 사용이 ..
https://www.acmicpc.net/problem/3955알고리즘 분류 : 수학, 정수론, 확장 유클리드 호제법❓문제🔅해석확장 유클리드 호제법 알고리즘을 이용한다. (공식 : ax+by=gcd(a,b))방정식에 적용할 a, b, c를 생각해보자면, a와 b는 입력값인 인원수, 한 봉지에 든 사탕 개수로 둘 수 있다.axby인원수인당 나눠줄 사탕 수한 봉지에 든 사탕 수사탕 봉지수ax + 1 = by 아래와 같이 항 정리를 한다.-ax + by = 1 여기서 주의할 점은, 나머지 정의가 0 그래서 a, b에 음수가 들어오지 않도록 x가 음수 값을 가지게 한다.a(-x) + by = 1 이제 확장 유클리드 호제법을 통해 s, t, r 값을 구한다.public static EGResult egcd(l..
https://www.acmicpc.net/problem/14476 알고리즘 분류 : 수학, 정수론, 누적합, 유클리드 호제법❓문제 🔅해석위 문제는 누적합과 유클리드 호제법을 이용하여 풀이해야한다. 먼저 두 수의 최대공약수를 구하는 방법인 유클리드 호제법을 구현한 코드이다.// gcd(a, b) == gcd(b, r) : r = a % bstatic int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a;} 이 유클리드 호제법을 통해 나온 최대공약수를 누적합 배열에 담는다. 8 12 24 36 48예를들어, 입력이 위와 같이 들어왔을 때, 8 ~ 48의 최대공약..
