알고리즘 배우는 주된 이유
아직 해결하지못한 문제를 해결할 수 있게하기위함.
지적자극을 주는데 흥미있음.
나쁜 프로그래머는 코드를 따지지만
좋은 프로그래머는 자료구조와 알고리즘을 따집니다.
알고리즘은 계산 모델이며, 알고리즘 모델은 과학분야에 있어 수학모델을 대체한다.
반복구문, 배열, 함수, 객체지향, 재귀 호출이 선행과정.
Union find
동적 연결 문제
메모리 사용량 분석등..
Quick Find / Quick Union 알고리즘
유용한 알고리즘 개발하기위해 필요한 것
1. 문제를 모델링
수학적모델 설계 - 수학적 모델 입증
동적연결성 문제(Dynamic Connectivity)
union-find에 대한 추상적인 모델
객체에 0부터 N-1까지 번호를 붙일것
매핑함으로써 검색 심볼에 대해 유리해짐
Union : 두 객체 연결
FindConnected : 두 객체간 연결이 되어있는지 true False 리턴
경로가있는지 YES / FALSE만..
'집합'을 잊지말아라!
연결성문제는 집합의 관계를 아주 중요하게 여긴다.
그저 연결되었는지 연결되지않았는지만 알면된다!
서로 같은 값을 공유하면 연결, 아니라면 비연결 이라고 생각하면 된다.
일단 직접 문제를 풀어보았는데. 다음과같다
클라이언트 부분
package firstWeek;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader StdIn = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(StdIn.readLine()); // 객체 수 받음
System.out.println(N);
UF uf = new UF(N);
while(!StdIn.readLine().equals("end"))
{
int p = Integer.parseInt(StdIn.readLine());
System.out.println("p: " + p);
int q = Integer.parseInt(StdIn.readLine());
System.out.println("q: " + q );
if(!uf.connected(p, q))
{
uf.union(p, q);
System.out.println(p + " " + q);
}
}
uf.show();
}
}
uf 클래스 부분
package firstWeek;
import java.util.ArrayList;
import java.util.Arrays;
public class UF {
// 집합에 엮어서 생각
// 동치, 서로 연결되어있다.
private int[] unionArray;
private int setCount;
public UF(int n)
{
unionArray = new int[n];
setCount = 1;
}
public void union(int p, int q)
{
// 초기화가 안됐을 경우
if(unionArray[p] == 0 && unionArray[q] == 0)
{
unionArray[p] = setCount;
unionArray[q] = setCount;
setCount++;
}else
{
// 초기화가 됐을 경우
if(unionArray[q] != 0)
{
unionArray[p] = unionArray[q];
}
else{
unionArray[q] = unionArray[p];
}
}
System.out.println("p : " + unionArray[p] + "q : " + unionArray[q] + "setCount : " + setCount);
}
public boolean connected(int p, int q)
{
boolean flag = false;
// 같으면 true 대신 초기화가 됐다는 가정하에
if(unionArray[p] == unionArray[q] && !(unionArray[p] == 0 && unionArray[q] == 0) ) flag = true;
return flag;
}
public int find(int p)
{
return 0;
}
public int count()
{
return 0;
}
public void show()
{
System.out.println(Arrays.toString(unionArray));
}
}
ArrayList로 하려고했는데, 힙메모리 할당 오류가 계속나서;; 그냥 배열로 풀었다.
더 좋은 알고리즘이 있을것같다.
그리고 int Arr가 클래스 생성시 0으로 초기화하는거때문에 골머리앓았다. 생각보다 복잡하게 구현되었다.
다음강의를 들어보니 자기 인덱스값으로 초기화하란다.
그리고 for문으로 순회하면서 첫번째 인자의 값과 같은건 두번째 인자에 있는 값을 바꿔주란다.
uf 클래스 부분
package firstWeek;
import java.util.ArrayList;
import java.util.Arrays;
public class UF {
// 집합에 엮어서 생각
// 동치, 서로 연결되어있다.
private int[] unionArray;
public UF(int n)
{
unionArray = new int[n];
// 자기 인덱스로 초기화
for(int i=0;i<unionArray.length;i++) {
unionArray[i] = i;
}
}
public void union(int p, int q)
{
// 근데 누구의 값을 덮어씔 건지 결정, 첫번째 인자에 두번째 인자껄 덮어씌움
// 문제점 1. 첫번째 인자에 들어있는 값에 두번째 인자에 넣는 과정 필요
int pid = unionArray[p];
int qid = unionArray[q];
// 연결되어있는 모든것에 두번째 인자 삽입
for(int i = 0; i < unionArray.length; i++)
{
if(unionArray[i] == pid) unionArray[i] = qid;
}
}
public boolean connected(int p, int q)
{
// 같으면 true 대신 초기화가 됐다는 가정하에
return unionArray[p] == unionArray[q];
}
public int find(int p)
{
return unionArray[p];
}
public int count()
{
return unionArray.length;
}
public void show()
{
System.out.println(Arrays.toString(unionArray));
}
}
초기화 한번 해줬다고 위에 코드보다 더 간결해졌다.
그리고 O(n)도 비싸다고 한다.
여기까지가 조급한(eager) 접근법이다.
---------
더 나은 방법은 게으른 접근법(lazy approach)이다.
같은 자료구조(같은 배열, 같은 사이즈)를 사용하지만 다른 알고리즘을 사용하게 된다.
배열을 tree로 생각하여 구현하게 된다.
요소안의 값이 부모를 가지게 되는 것을 의미한다.
두 개의 요소가 같은 루트를 가져서 연결이 되는지 확인 해 볼 수 있다.
Quick-Union
// 루트 찾는 메서드
private int root(int i)
{
while( i != unionArray[i] ) i = unionArray[i]; // 값을 계속 추적해나가 루트를 구함.
return i;
}
public void union(int p, int q)
{
//QUICK UNION으로 변경
int i = root(p); // 한번에 바꾸어야하므로 이 트리 전체를 q로 받은 것에 붙인다.
int j = root(q); // 루트로 구분하므로 q의 루트를 구해서 붙인다.
unionArray[i] = j;
}
public boolean connected(int p, int q)
{
// 루트를 비교하면 됨
return root(p) == root(q);
}
찾는데 위에것보다 너무 오래걸릴 수 있다.
트리구조가 길어질 경우 문제가 있다.
더 좋은 알고리즘이 있다고한다.
나도 트리구조로 보니까 조금 어렵긴하다;;
만약 규모가 큰 트리와 작은 트리를 합쳐야하면
큰 트리를 작은 트리아래에 두면 안된다.
트리가 커지는 것을 회피해야한다!
'알고리즘과 자료구조' 카테고리의 다른 글
프로그래밍의 배열 인덱스(번호)는 왜 0부터 시작할까? (0) | 2020.01.15 |
---|