채우다

내가 까먹지 않으려고 정리하는 정렬 방법.
클래스를 생성하고, 특정 속성으로 정렬한다는 가정하에 작성했다. 클래스의 속성으로는 id, time 두 개를 설정.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class SortTest {
    public static void main(String[] args) {
        List<SortObject> list = new ArrayList<>();

        list.add(new SortObject(1,1));
        list.add(new SortObject(1,1));
        list.add(new SortObject(2,2));
        list.add(new SortObject(3,3));
        list.add(new SortObject(4,4));
        list.add(new SortObject(5,1));
        list.add(new SortObject(5,2));

    }//main
    static class SortObject{
        int time;
        int id;


        Sort(int time, int id){
            this.time= time;
            this.id = id;
        }

        public int getId() {
            return id;
        }

        public int getTime() {
            return time;
        }

        @Override
        public String toString() {
            return "SortObject{" +
                    "time=" + time +
                    ", id=" + id +
                    '}';
        }
    }//SortObject
}//class

• 한 가지 조건으로 정렬할 경우

// time을 기준으로 오름차순 정렬
list.sort((SortObject s1, SortObject s2)->(s1.time-s2.time));
// time을 기준으로 내림차순 정렬
list.sort((SortObject s1, SortObject s2)->(s2.time-s1.time));

• 두가지 조건으로 정렬할 경우 
  • 람다표현식 사용

list.sort((o1,o2)->{
	//time으로 오름차순 비교
	int compare = Long.compare(o1.getTime(), o2.getTime());
	
	if(compare ==0){
	    //id로 오름차순 비교
    	return o1.getId().compareTo(o2.getId());
    }else{
    	return compare;
    }
})

• Comparator.comparing

//time을 기준으로 내림차순, id를 기준으로 오름차순 정렬
list.sort(Comparator.comparing(SortObject:getTime).reversed().thenComparing(SortObject::getId));

- 플로이드 워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘으로 시간복잡도는 O(V^3)이다.

- 특정 노드 사이의 간선이 없을 경우 INF로 표시하여 인접행렬을 만들 수 있다. ROUND를 반복하면서 인접행렬을 그린다. 노드간의 최단 거리로 인접행렬을 완성한다.

- 소스코드로 구현할 경우 3개의 FOR문으로 만들 수 있다.
먼저 초기 인접 행렬의 값을 사용해 노드 사이의 최단 거리 배열을 초기화한다.

for(int i = 1; i<=n; i++){
    for(int j =1; j<=n; j++){
        if (i == j) dist[i][j] = 0;
        else if (adj[i][j]) dist[i][j] = adj[i][j];
        else dist[i][j] = INF;
    }
}

이후 중간 노드가 될 노드 번호를 FOR문의 가장 바깥 변수로 잡고, 내부 이중 for문의 변수들을 통해 각 노드별 거리를 살펴보면서 k를 중간노드로 삼을때와 아닐때의 값을 비교한 후 더 작은 값으로 업데이트한다.

for(int k = 1; k<= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j<=n; j++){
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}