Java 알고리즘 잡기술 모음

이 페이지는 알고리즘을 공부하면서 빠른 구현을 위한 잡기술들을 모아놓았습니다.

추후에 학습하면서 더 좋은 기술을 발견하면 꾸준히 업데이트 할 예정입니다.

 

 

 

2차원 배열에서 y, x의 위치

int n = 3; // 세로의 길이
int m = 4; // 가로의 길이


int[][] board = new int[3][4];
int index = 1;
for(int i = 0; i < n; i++)
	for(int j = 0; j < m; k++)
    	board[i][j] = index++;
        
// target의 y,x의 좌표
int target = 10;
int y = (target-1) / m;
int x = (target-1) % m;

// 결과 y = 2, x = 1

 

 

 

칸 채우기

// 2차원 배열
int n = 3;
int[][] board = new int[n][n];

int y = 0;
int x = 0;
int index = 0;

// 아래로 칸 채우기
while(y + 1 < n)
{
	board[++y][x] = ++index;
}

 

 

 

2차원 배열안의 정사각형 탐색

// DP를 활용

int n = 3; // 세로
int m = 4; // 가로

// 왼쪽, 왼쪽 위, 위쪽을 탐색한다.

int answer = 0;
int[][] dp = new int[n+1][m+1];

for(int i = 1; i < n+1; i++)
{
	for(int j = 1; j < m+1; j++)
	{
		int one = Math.min(dp[i-1][j], Math.min(dp[i-1][j-1], dp[i][j-1]));
	if(board[i-1][j-1] == 1)
		dp[i][j] = one + board[i-1][j-1];
	else 
		dp[i][j] = 0;
	answer = Math.max(answer, dp[i][j]);
	}
}

answer = answer * answer;

 

 

 

진수 변환하기

int n = 2; // 변환하고 싶은 진수, 예시는 2진수
String convnum = ""; // 변환한 수를 담을 변수
int number = 7; // 진수 변환하고 싶은 숫자

while(number > 0)
{
	convnum = number % n + convnum;
	number = number / n;
}

 

 

 

정렬

// 내림차순 정렬
ArrayList<Integer> list = new ArrayList<>();
Collections.sort(list, (o1, o2) -> o2 - o1);

// comparator를 이용한 정렬
// music 클래스의 play를 기준으로 내림차순 정렬
// play가 같다면 index를 기준으로 오름차순 정렬
class music
{
	int index;
    int play;
    
    public music(int index, int play)
    {
    	this.index = index;
        this.play = play;
    }
}

ArrayList<music> list = new ArrayList<>();
Collections.sort(list, new Comparator<music>() {

	@Override
    public int compare(music o1, music o2)
    {
    	int result = o2.play - o1.play;
        
        if(result == 0
        {
        	return o1.index - o2.index;
        }
        
        return result;
    }

});

 

 

 

이분탐색 (Binary Search)

// 배열(탐색에 성공하면 1, 없으면 0을 반환)
public static int binarySearch(int target, int[] arr)
{
	int n = arr.length;
    
    int start = 0;
    int end = n-1;
    int mid;
    
    while(start <= end)
    {
    	if(arr[mid] == target)
        	return 1;
        else if(arr[mid] < target)
        	start = mid + 1;
        else 
        	end = mid - 1;
    }
    
    return 0;

}

 

 

 

유니온 - 파인드

// n은 갯수, 처음에 부모는 자기자신
static int[] parent = new int[n];
for(int i = 0; i < n; i++)
	parent[i] = i;

// 부모를 찾아주는 함수
public static int find(int a)
{
    if(parent[a] == a)
    	return a;
    else
    	return parent[a] = find(parent[a]);
}

// 부모를 합치는 함수
public static void union(int a, int b)
{
    a = find(a);
    b = find(b);
    
    if(a != b)
    	parent[b] = a;
}

 

 

 

class 내 정렬

class Dot implements Comparable<Dot>
{
	int spot;
    int money;
    
    Dot(int spot, int money)
    {
    	this.spot = spot;
        this.money = money;
    }
    
    @Override
    public int compareTo(Dot e)
    {
    	return this.money - e.money;
    }
}