알고리즘) dp2

 

플로이드, 외판원 계산문제 [  ]

 

앞엣것들도 계산문제, 실제로 답찾는[  ]

 

 

공간복잡도 

---

 

최단경로 경로 출력

 

 

 

 

 

void path(q, r) {
    if (P[q][r] != 0) {
        path(q, P[q][r]);        // 1. 왼쪽 경로(q에서 k까지) 재귀 탐색
        print(" v" + P[q][r]);   // 2. 중간 정점 k 출력 (Root 역할)
        path(P[q][r], r);        // 3. 오른쪽 경로(k에서 r까지) 재귀 탐색
    }
}

 

 

 

 

 

 

노드출력

String toString(Node ptr) {
    if (ptr == null) return ""; // 빈 자식은 빈 문자열
    
    // 1. 부모를 먼저 출력 (Pre-order의 핵심)
    String result = ptr.data; 
    
    if (ptr.left != null || ptr.right != null) {
        // 2. 부모 출력 후 괄호를 열고 자식들을 재귀 호출
        result += "(" + toString(ptr.left) + ", " + toString(ptr.right) + ")";
    }
    
    return result;
}

 

 

 

이항계수 이해

 

 

플로이드 

 

 

 

 

"최단"을 측정하기 위한 기준점입니다.

최단경로라는 말 자체가 **"A에서 B까지 가는 길 중 가장 짧은 것"**을 의미합니다. 만약 도착점이 정해져 있지 않다면, 어디로 가느냐에 따라 거리가 계속 달라지기 때문에 어떤 길이 '최적(Optimal)'인지 비교할 기준이 사라집니다.

• 마치 내비게이션에 목적지를 찍지 않고 "가장 빠른 길로 안내해줘"라고 하는 것과 같습니다. 목적지가 있어야 그곳까지 가는 여러 방법(해답) 중 가장 좋은 것을 고를 수 있습니다.

두개를 뺴는 이유(출발지,도착지)

 

 

 

 

 

 

 

 

 

 

 

거쳐가는점이 제일 바깥루프임

 

각k에 대해서 모든 i,j를 해야하기 떄문인가

 

 

 

 

 

 

 

 

 

 

• "p 갱신해주려면 조건문을 써야?":
  • 네, 맞습니다. Math.min은 값만 바꿔주지만, if를 쓰면 값이 바뀔 때 그 이유가 된 **'누구를 거쳐갔는지(k)'**를 동시에 기록할 수 있습니다.
• "계속 d로 하나 w안쓰던가":
  • 보통 w는 입력 데이터(수정하지 않음)로 두고, d를 새로 만들어 거기서 계산을 수행합니다. 그래야 나중에 원본 그래프가 어땠는지 참조할 수 있기 때문입니다.

 

 

 

 

외판원 문제

 

 

 

 

기호의미 

 

 

 

 

무작정 방식이랑 다른점(기록하기)

피보나치 계산할때도 기록해뒀잖아 

 

 

 

 

 

 

 

 

 

시간복잡도 

 

 

 

 

 

 

그 끈다는건 사용안한다는거니깐, 그 안에 갯수가 여러가지인 경우 포함하는건가ㅇㅇ

 

 

 

 

 

기호의미 

 

 

 

 

 

 

 

이거 약간 재귀형식이알서,

d배열이라고 썻지만 결구ㅜㄱ 계산은 w배열로 하게되는건가,

그러면 최솟값 갱신은 언제하는거지 이건 이미 구해놓ㅇ는게 언제 활용되는거지