알고리즘 문제를 풀다보면 제곱근에 대한 문제가 종종 있습니다. 흔히 사용하는 math 의 pow 로 해결이 불가능 한 경우가 있습니다. 1024 이상의 제곱근을 사용하면 오류가 발생하거나 엉뚱한 숫자가 나타납니다. 이때 사용하는 것이 BigInteger 의 pow 입니다.
아래는 BigInteger를 이용한 제곱근을 구하는 방법입니다. 그리고 나머지를 구해주는 remainder 까지 사용해 보았습니다.
package study.basic;
import java.math.BigInteger;
public class Big_Integer {
public static void main(String[] args) {
BigInteger big1, result;
big1 = new BigInteger("2");
int exponent=1245;
result = big1.pow(exponent);
String str = big1 + "^" + exponent + " = " + result;
System.out.println(str);
int i = 1000000007;
System.out.println( result.remainder(BigInteger.valueOf(i)));
}
}
시험에 종종나오는 큰수의 경우 BigInteger를 사용하여 처리하면 간단히 구현이 가능합니다. 사용법을 꼭 숙지하십시오.
package segmenttree;
import java.io.*;
import java.util.StringTokenizer;
public class Rmq {
static int[] numbers;
static int[][] questions;
static int[] tree;
public static void init(int node, int start, int end) {
if (start == end) {
tree[node] = numbers[start];
} else {
init(node*2, start, (start+end)/2);
init(node*2+1, (start+end)/2+1, end);
tree[node] = Math.min(tree[node*2],tree[node*2+1]);
}
}
public static int query(int node, int start, int end, int a, int b) {
if (a > end || b < start) {
return -1;
}
if (a <= start && end <= b) {
return tree[node];
}
int left = query(node*2, start, (start+end)/2, a, b);
int right = query(node*2+1, (start+end)/2+1, end, a, b);
if (left == -1) {
return right;
} else if (right == -1){
return left;
} else {
return Math.min(left, right);
}
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("input\\rmq.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
numbers = new int[N];
questions = new int[M][2];
tree = new int[N*4];
for (int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
numbers[i] = Integer.parseInt(st.nextToken());
}
for (int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
questions[i][0] = Integer.parseInt(st.nextToken());
questions[i][1] = Integer.parseInt(st.nextToken());
}
br.close();
init(1, 0, N-1);
// for (int i=0; i<tree.length; i++) {
// System.out.println("tree[" + i + "] : " + tree[i]);
// }
for (int i=0; i<M; i++) {
bw.write(query(1, 0, N-1, questions[i][0]-1, questions[i][1]-1)+"\n");
}
bw.flush();
bw.close();
}
}
맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식입니다.
장점
단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
단점
해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.
세그먼트 트리를 이용하여 구간의 합을 빨리 찾는 문제를 설명하도록 하겠습니다. 이번 포스팅은 영상을 찍어봤는데, 처음이라 자연스럽지 못하지만 나름 열심히 설명하려 노력했습니다. 어색하더라도 양해해 주십시오.
이론설명
초기설정구현
public static int init(int node, int start, int end) {
if (start == end) {
tree[node] = numbers[start];
} else {
int left = init(node*2, start, (start+end)/2);
int right = init(node*2+1, (start+end)/2+1, end);
tree[node] = left+right;
}
return tree[node];
}
구간합 찾기 구현
public static int query(int node, int start, int end, int a, int b) {
if (a > end || b < start) {
return 0;
}
if (a <= start && end <= b) {
return tree[node];
}
int left = query(node*2, start, (start+end)/2, a, b);
int right = query(node*2+1, (start+end)/2+1, end, a, b);
return left + right;
}
전체코드
import java.io.*;
import java.util.StringTokenizer;
public class Rsq {
static int[] numbers;
static int[][] questions;
static int[] tree;
public static int init(int node, int start, int end) {
if (start == end) {
tree[node] = numbers[start];
} else {
int left = init(node*2, start, (start+end)/2);
int right = init(node*2+1, (start+end)/2+1, end);
tree[node] = left+right;
}
return tree[node];
}
public static int query(int node, int start, int end, int a, int b) {
if (a > end || b < start) {
return 0;
}
if (a <= start && end <= b) {
return tree[node];
}
int left = query(node*2, start, (start+end)/2, a, b);
int right = query(node*2+1, (start+end)/2+1, end, a, b);
return left + right;
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("input\\rsq.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
numbers = new int[N];
questions = new int[M][2];
tree = new int[N*4];
st = new StringTokenizer(br.readLine());
for (int i=0; i<N; i++) {
numbers[i] = Integer.parseInt(st.nextToken());
}
for (int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
questions[i][0] = Integer.parseInt(st.nextToken());
questions[i][1] = Integer.parseInt(st.nextToken());
}
br.close();
init(1, 0, N-1);
for (int i=0; i<tree.length; i++) {
System.out.println("tree[" + i + "] : " + tree[i]);
}
for (int i=0; i<M; i++) {
bw.write(query(1, 0, N-1, questions[i][0]-1, questions[i][1]-1)+"\n");
}
bw.flush();
bw.close();
}
}
인접 리스트는 그래프 이론에서 그래프를 표현하기 위한 방법 중 하나입니다. 그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현하는 방법입니다. 인접 행렬에 비하여 변이 희소한 그래프에 효율적 입니다.
동작방식
아래와 같은 그래프가 존재할때 인접행렬을 만들어 보겠습니다. 1노드에서 시작하여 2,3 노드로 연결됩니다. 그리고 3노드는 2,4 노드로 연결됩니다. 이는 단방향을 나타내고 있음을 알수 있습니다. 2차원 배열을 준비하고 배열의 Y축을 시작 좌표, 배열의 X축을 그래프가 향하는 노드라고 생각을하고 아래 그림과 같이 만들어 사용을 합니다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.PriorityQueue;
public class PriorityQueue_example_0 {
/**
* Priority Queue - Heap 으로 가장 많이 구현되어있다.
* - 먼저넣은 것중 우선순위가 높은 것을 뺀다.
* - 자료를 넣고 빼는 속도 모두 : logN
* - max, min 값 찾기에 많이 쓰임
*/
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
// min heap - 가장 위(0)가 가장 작은값
PriorityQueue<Integer> q = new PriorityQueue<Integer>();
q.add(5);
q.add(3);
q.add(7);
q.add(4);
q.add(5);
System.out.println(q.poll());
System.out.println(q.poll());
System.out.println(q.poll());
System.out.println(q.poll());
System.out.println(q.poll());
System.out.println(q.poll());
System.out.println("=======================");
// max heap - 가장 위(0)가 가장 큰값
PriorityQueue<Integer> qr = new PriorityQueue<Integer>(Collections.reverseOrder());
qr.add(5);
qr.add(3);
qr.add(7);
qr.add(4);
qr.add(5);
// 빼지않고, 가장 우선순위
System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
// --> 힙소트
br.close();
bw.close();
}
}
이번에는 슬라이딩 윈도우 알고리즘과 DAT 자료구조를 이용한 간단한 문제를 풀어보겠습니다.
문제
입력된 문자열(알파벳)에서 길이가 M개의 구간에서 가장 많이 등장하는 알파벳을 출력하라
문자열 : "AAAABBBBAABKKKABKKKKDKAAA" M: 6
코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class SlidingWindow_DAT {
/**
* 슬라이등 윈도우 + DAT
*/
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String str = "AAAABBBBAABKKKABKKKKDKAAA";
int n = str.length();
int m = 6;
int[] dat = new int[100];
//초기세팅 6개 DAT
char maxCh = ' ';
int maxCnt = 0;
for (int i = 0; i<m; i++) {
dat[str.charAt(i)]++;
if (dat[str.charAt(i)] > maxCnt) {
maxCnt = dat[str.charAt(i)];
maxCh = str.charAt(i);
}
}
//슬라이딩 윈도우
for (int i = 0; i<n - m; i++) {
//다음 준비
dat[str.charAt(i + m)]++;
dat[str.charAt(i)]--;
if (dat[str.charAt(i + m)] > maxCnt) {
maxCnt = dat[str.charAt(i + m)];
maxCh = str.charAt(i + m);
}
}
System.out.println(maxCh);
bw.close();
br.close();
}
}
풀이
dat 배열에 길이가 M인 구간에서 나타나는 알파벳을 카운트하여 줍니다. 문자열 AAAABBBBAABKKKABKKKKDKAAA에서 처음 AAAABB 를 확인하면 dat 배열 dat['A']는 4, dat['B'] 는 2가 들어갑니다. 그리고 다음으로 이동합니다. 슬라이딩 윈도우 알고리즘으로 길이가 6인 구간을 기준으로 뒤문자는 카운트를 더해주고, 앞문자는 카운트에서 빼줍니다. 작업이 완려되면 dat배열에 문자번째와 max변수를 비교하여 max변수를 갱신합니다. 이러한 방식으로 M구간에서 가장 많이 나오는 알파벳을 알아낼 수 있습니다.
슬라이딩 윈도우 알고리즘은 배열 요소의 일정 범위 값을 비교할때 사용하면 유용한 알고리즘 입니다.
동작방식
일정 정수로 이루어진 배열 int[] arr= {3,1,5,3,4,1,5,7,5,1,8} 가 있다면, 길이가 5인 배열의 합계가 가장 큰 것은 무엇인가? 라는 문제에 사용될 수 있습니다. 일반적으로 아래와 같이 0번째 부터 4번째 (길이가 5이므로) 합을 구하고 저장합니다. 그리고 1번째 부터 5번째까지의 합을 구하고 저장후 처음에 구했던 값과 비교를 하여 큰것을 가지고 있습니다. 이렇게 반복을 하면 됩니다. 하지만 이 방법은 매번 for 루프로 모든 배열의 요소를 지정된 길이만큼 순회하며 합계를 구해 최대값을 구해야하므로 비효율적 입니다.
이것을 간단히 생각해보면 처음에 해당 길이만큼 합계를 구하는 것은 어쩔수 없습니다. 하지만, 그 이후부터 매번 돌지 않고 인덱스 1~5까지의 합은 처음에 길했던 0~4까지의 합계에 0번째 배열의 값을 빼고, 5번째 배열의 값을 더한 값과 같습니다. 바로 이 부분에서 처음 구했던 0~4까지의 합계를 재사용하며 다음값을 구할 수 있는데, 이것이 슬라이딩 윈도우 알고리즘의 핵심입니다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class SlidingWindow_example {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int[] arr= {3,1,5,3,4,1,5,7,5,1,8};
static int n;
static int getFive(int index)
{
int sum= 0;
for (int i = 0; i<5; i++) {
sum += arr[i + index];
}
return sum;
}
public static void main(String[] args) throws IOException {
n = arr.length;
int max = -9999;
int sum = getFive(0);
for (int i = 0; i <= n - 5; i++) {
if (sum > max) max = sum;
// 마지막순간에는 다음 것을 준비할 필요 없음
if (i == n - 5) break;
// 다음 것을 준비
sum += arr[i + 5];
sum -= arr[i];
}
System.out.println(max);
bw.close();
br.close();
}
}
