알고리즘)문풀2

 

#F 7번~~[  ]

 

 

---

 

 

 

public int compare(...) 메서드는 int 타입을 반환해야 합니다.

• 질문하신 o1.getValue().compareTo(o2.getValue()) > 0는 결과가 true 아니면 false인 boolean 타입입니다.

 

 

 

1. 오름차순 정렬: o1.compareTo(o2) (나 - 남)
2. 내림차순 정렬: o2.compareTo(o1) (남 - 나)

 

 

(Integer 타입이므로 가능):

o2.getValue() - o1.getValue()

 

 

 

 

분할정복법으로 가방문제 

        // 1. 중단 조건 추가 (매우 중요!)
        if (n <= 0 || W <= 0) {
            return 0;
        }

 

 

 

 

 

 

 

 

동적 프로그래밍이 아니니까 P[][]배열이 없는건가,-재귀로 구성(분항정복법)_

있더라도 희소행렬이라서 구리고ㅇㅇㅇㅇ

 

 

어차피 Math.max이고 p[i]+....이니깐, 이 ...부분이 0이 되는거겟지, 1까지 내려가면"

int dontforget=n-1;

 

 

 

 

프림이 greedy\

어떤 알고리즘이 어떤 챕터에 있는지도 

 

 

 

e1.weight - e2.weight;

 

 

 

p 배열은 시작 인덱스를 저장하는 용도이므로, 실제 값을 담으려면 원본 배열인 **A**에서 값을 가져와야 합니다.

 

 

 

기존 코드의 p[i-1][j] = 1 방식은 i나 j가 0일 때 p[-1]을 참조하게 되어

(둘다 0이 아닐때)

 

가장 왼쪽 줄(j=0)에 있을 때는 p 배열을 볼 필요도 없이 무조건 위(i--)로 올라가야 하고, 가장 윗 줄(i=0)에 있을 때는 무조건 왼쪽(j--)으로 가야 한다는 예외 처리가 필요합니다.

 

 

while(true){
    if(i==0 && j==0) break;

    if (j == 0) { // 더 이상 왼쪽으로 갈 수 없으면
        arrList.add(A[--i][j]); // 무조건 위로
    } 
    else if (i == 0) { // 더 이상 위로 갈 수 없으면
        arrList.add(A[i][--j]); // 무조건 왼쪽으로
    } 
    else if (p[i-1][j] == 1) { // 둘 다 가능할 때만 p 확인
        arrList.add(A[--i][j]);
    } 
    else {
        arrList.add(A[i][--j]);
    }
}

 

 

ArrayList는 arrList[index] 같은 배열 기호를 사용할 수 없습니다. 반드시 .get(index)

 

 

리스트에서, arrList.size()가 배열 크기임

리스트에서 배열 변환