크루스칼 알고리즘과 힙 기반 구현

지의 개수가 v-1개다 그러면 멈춰야 된다 이건 아주 쉽다 그래서 예를 들면 힙을 사용하니까 이게 이렇게 되면은 stop 된다는 거죠 complete 됐다는 거죠 자 이런 알고리즘이다

자 지난 시간과 동일한 그래프를 그려놓고 이제 한번 선택을 해봅시다 먼저 1인 친구들이 몇 개 있냐면 두 개 있어요 지난 시간 그래프를 보면 가중치가 1인 친구가 두 개 있어 그래서 여기 먼저 JK를 먼저 방문해서 굵게 칠한 걸 먼저 방문했다고 생각합시다 근데 JK랑 저기 뭐야 AC 중에 누가 먼저 방문합니까는 여러분의 코드 기준으로 생각합니다 손 코딩을 반드시 해야 된다 시험공부를 어떻게 하는 거다 일단 코드는 기본적으로 알고 있어야겠죠 코드를 모르고 어떻게 시험을... 아 그렇죠?

코드는 기본적으로 알고 있어야 되고 내가 이 예제를 실제 손코딩해서 이런 거 봐야겠지 실제로 자 그래서 여기 보면 어쨌든 JK랑 그 다음에 AC가 이렇게 선택이 됐다는 거죠 다행히 처음에는 사이클링을 만드는 애들이 없죠 더으러 갯수가 두 개니까 자 그다음

그 다음은 뭐냐면 가중치가 2인 친구들이 다음 타자들인데 2인 친구들이 몇 개 있냐면 하나 둘 셋 넷 다섯 개가 있어 다섯 개 다섯 개가 있어서 코드에 따라 방문을 한다고 칩시다 먼저 fj를 방문하고 그 다음에 어디 방문을 했어? 어디야? 아 여기

HI를 방문하고 그렇죠? 맞죠? 근데 여기서 문제가 있어 뭐 IJ 그 다음 IJ 그 다음 IJ 뭐 이렇게 세 개를 다 방문했고 하나 더 있어 CD까지 방문했다고 칩시다 4개를 다 방문했는데 마지막 하나에 재미로는

모든 걸 선택할 때 다 검사하는 거야. 내가 이거 처음 시작할 때도 검사하는 거야. 자, 1 얘네 선택해야지. 그때 뭐다? 내가 이걸 선택했을 때 그래프가 사이클릭해지는가? 검사. 아니다. 그럼 선택. 이 방금 말한 사이클릭해지는가는 내 선택마다 돌아가는 거예요. 근데 그 돌아갈 때 여기에 다 걸리게 되겠죠. 누구 할 때, 얘 할 때.

AD 할 때, 그쵸? AD를 하면 어떻게 돼요? 앞에 지금 AC랑 CD 방문했잖아, 그쵸? 그럼 내가 이 순간에 AD를, AD에 맞아? AD를 딱 선택하면 어떻게 돼요? 저 부분이 CycleCat죠? 그러니까 선택을 하면 안 된다는 게 풀스칼 알고리즘이란 말이에요. 그러면 이걸 어떻게 판단하는가를 이제 뒤에서 볼게요.

이렇게 판단을 할거에요. 우리가 집합의 티어리에 의해서 지금 여러가지 나무가 있지만 추리가 있는데 예를 들면 E의 부모는 누구에요? B야. 그렇죠? 근데 B의 부모는

A야. 그러니까 이걸 어떻게 해석할 수 있냐면 E의 부모는 A라고도 표현할 수 있잖아요. 트리상에서. E의 부모는 직접적인 부모는 B인데 B가 또 자기 부모가 있어요. A야. 그러니까 A는 E의 부모가 된다는 거예요.

그러면 이런 E 노드와 D 노드 한번 볼까? D 노드? D의 부모는 누구예요? A야. 그렇죠. 그러니까 이걸 통해서 알 수 있는 거는 A와 E는 뭐다?

동일한 부모로 그렇죠. A와 E는 동일한 부모야 그렇기 때문에 내가 E, D를 이으면 된다 안 된다 안 된다는 거예요 그런데 어떤 선택의 순간에서 E노드와 D노드를 연결하면 스트로스카 알고리즘의 룰에 의해서 바이오레이션

그래서 선택을 하면 안 된다 왜냐? E와 D는 동일한 동호 A를 공유하고 있기 때문이죠 I는 상관없어 왜? I의 부모는 누구예요? 지금 원리를 다 지금 I의 부모는 F야 그렇죠? E의 부모는 A야 그러니까 I를 선택한 그 I에 관련된 엣지를 선택한 거죠 자 이렇게 아 그러면 우리가 이런 생각을 할 수가 있지 결국은

부모를 타고 타고 와서 나와 연결된 친구들 실제로 나의 부모를 계속 보면 되는거죠 우리 부모를 지금 계속 어떤 지난 시간에 우리가 연습도 했지만 어떤 노드를 여기도 나와 있지만 우리 이 어레이를 사용해서 하고 있잖아요 parent parent라는게 실제로 내가 뭐라 그랬어 스페인 트위 모양을 알 수 있다고 그랬죠 왜냐면 나의 부모를 알 수 있으니까 누가 나를 힙에 넣어줬지 방문하면서 나를 넣어준 거기 때문에 스페인 트위 모양을 담고 있는 걸로 고!

그래서 예를 들면 여기에 p에 e를 넣으면 어떻게 된다는 거야? 뭐가 나와야 된다는 거야? b라는 거죠. 그렇죠? 근데 한 번 더 타고 올라간다는 거지 parent b가 누구예요? a라는 거죠. 그러니까 e의 부모는 누구다? a라고 볼 수 있다는 거야. 그리고 parent b

D의 부모도 A야 같다는 거죠 이걸 구현하면 돼, 이 동작을 E가 인덱싱이 돼서 B 그 다음에 P가 다시 여기 인덱싱이 돼서 A까지 어디까지 올라가면 돼? 제 부모까지 올라가면 되죠 제 부모의 parent, 어레인에 뭘 저장해놨어? PFS에 뭘 저장했지? 지난 시간에

그렇죠. 복수를 제대로 -1이 저장되어 있죠. 그러니까 이 품은 걸어가지고 양수일 때까지 계속 올라가면 되지 저거 리퀄틱이 탁 올라가면 되지 풀을 두르면서 Y 그렇게 해서 나온 인덱스가 있을 거 아니에요. 그 인덱스랑 또 다른 선택한 인덱스 계속 똑같이 해가지고 한 인덱스가 같다! 그럼 너 이 두 개 엣지 선택하면 된다 안 된다? 안 된다? 안 된다! 라고 이거 함수를 이렇게 만들어주면 된다는 거예요. 오케이?

간단하죠. 그래서 여기 보면은 노드는 이제 여기 A, B, C, D, E, F, G에서 M까지 있잖아요. 그러니까 G에다가 얘는 이제 자식인거죠. 이 노드라고 쓴 거는 이제 자식인거고 각 자식의 부모를 밑에다 써준거에요.

Fs랑 k는 다 뭐예요? root야 부모가 없어 내가 제일 부모라나? 그렇죠? 그러니까 지금 원래는 여기 아까 학생이 말한 것처럼 이렇게 돼 있지만 원래는 제 -1일 차이점이 있죠? 지난 시간에 꼬링한 거예요. 내가 얘기했잖아요. 그렇죠? 지난 시간에 root임을 표기하기 위해서 -1을 넘었다. 그래서 -1을 넘었다. 나머지는 어때요? B에 부모 A, C에 부모 A, D에 부모 A, D에 부모 B 그렇죠?

근데 이제 for loop를 한 번 더 돌면 어떻게 된다? e의 부모가 b였다. for loop를 한 번 더 돌면 코드가 어떻게 짜야 한다? b가 이리로 가겠죠. 그래서 나는 a를 찾고 그 다음 어떻게 돼? a를 찾고 갔더니 뭐를 만나? -3를 만나면 끝. 이 loop를 짜면 된다는 거죠. e의 부모를 봤더니 b. for loop를 돌아서 b. 그래? 그럼 b의 부모는 누굴까? a. 그래? 그럼 a의 부모는 볼까? -1. 그럼 -1. 응수네. 끝. 그럼 e의 부모는 누구다? a다. 라고 판별이 돼. a다. 라고 택싱을 해줄 거예요.

이렇게 간단한 코드 아니겠어요? 그렇죠? 코드도 두 줄이면 짜요 자 그렇게 되어 있어요 그래서 밑에는 내가 지금 말한 걸 설명을 해 놓은 거야 그래서 우리가 실제 ABCD를 넣을 수는 없어 인덱스가 아니잖아 int to date, name to int를 바꿔줘야겠죠 name to int로 바꿔주면 숫자로 표기가 되겠죠 우리는 이제 2 같은 경우는 4인거지 그래서 다시 쓰면은 실제로 이렇게 들어가는 거죠. 코드사인 parent사는

즉 1이 되는거죠. 그쵸? 그리고 parent1은 0이 되는거고 그 다음에 마지막으로 parent 0은 -1. start! 그러면 이때 인덱스가 부모 누구의? 이 친구의. 4의 부모는 0이 되는거죠.

4는 0으로 2고 0은 2죠. 그렇죠? 그렇게 판별하면 된다. 질문. 어려워? 간단하죠? 그렇죠? 아주 간단하죠. 부모를 공유한다. 나무에서 부모를 공유하면은 봐보세요. 부모를 공유하면 나를 이렇게 연결하면 다 어떻게 돼?

같은 부모 끼리 연결하면 이런 식으로 다 사인 클릭해지잖아 그쵸 그렇기 때문에 부모가 같은 애들끼리 연결하면 안 된다는 거야 그 컨셉인거에요 자 질문 없으면 얘를 실제로 어떻게 구현하는가 아까 E랑 D를 한번 가지고 예제를 앞에서 E랑 D 있죠

바로 해봅시다. 그래서 int to name을 쓰면 뭐야. name to int를 써야겠지. 자 그래서 lm과 associate 여기 보면 플래그가 있는데 사실은 이 함수는 좀 더 advanced한 뭔가를 이용하기 위해서 좀 만든 건데 지금은 그냥 뭐

요정도 하나 들어가고 자 봅시다 플래그가 0 아니면 1이 들어가는데요 여기 그리고 0 아니면 1이 들어가는데 0이면 여기 보니까 뭐예요 플래그가 0이면 OnlyFind 그러니까 저거는 뭐냐면은 그냥 얘가 지금 사이클릭을 만듭니다 만들지 않습니다만 그냥 판단해줘

그 판단만 하는게 그냥 Only Find고요 Union은 만약 얘가 Cyclic 하지 않는거면 그냥 연결하는 그 동작까지 그래서 예를 들면 이렇게 얘가 지금 A인데 뭐 E를 봤다? 근데 두개가 부모를 공유하지 않아요 공유하지 않죠 A의 부모는 -1이고 I의 부모는 F잖아요

그러면 두개가 사이클릭하지 않으니까 아 사이클릭하지 않다 이 두개를 연결할 엣지를 선택해도 된다 까지만 하는게 뭐다? OnlyFind 근데 실제로 그거 한 다음에 뭐하냐면 그래? 그러면 사이클릭하지 않으니까 얘를 실제로 연결해온다 아이의 자식을

그것까지 하는게 union 그래서 union으로 일단 구현할게요. 스페인트에 만드는 과정 자 그래서 여기 보면은 이제 우리로 치자면 lm으로는 e가 들어갔다고 합시다. 그리고 association d가 들어갔다고 합시다. i의 lm을 카피하고 association

2가 얼마일지 숫자? 숫자 4 t는 숫자 3 자 그럼 이거 보세요 이게 왜 있다고 root는 부모가 -1임을 이용한거죠 root는 부모가 -1임을 이용해서 사실이라고 우리가 정의한거죠 이렇게 이용해서 정보룩을 저와일룩으로 만들어 볼거죠

내 부모가 -1이면 y로프가 안 돌아 안 돌아 안 돌릴거죠. 그러면서 인덱스가 정해지는거죠. 자 그래서 근데 봅시다. 먼저 parent i는 lm 이니까 보면은 파란색으로 쓸까 하죠. 이게 이제 parent 4잖아요. 4가 들어갑니다.

걔의 부모는 누구야? 테런트의 4. 아까 누구였어? B였잖아요. B. 그쵸? B니까 얼마야? 숫자 1이죠. 아 1이죠. 그러니까 1은 0 이상이죠. 그러니까 y로 프를 돌아왔더니 어떻게 돼? 이 부분인거죠. 핵심은. 코드를 이렇게 짜야 되는거죠. 즉 내가 여기서 화살표 친 거 있잖아. 이렇게 한 거.

이렇게 움직였다가 얘를 여기로 이렇게 가는 화살표 이 화살표 어떻게 구현했다? i는 parent i로 구현한거죠 그럼 저 parent라는 어릴 인덱스는 뭐야? 자식이잖아 자식

그쵸? 그리고 거기 안에 들어있는 갑은 뭐예요? 부모잖아. 그러니까 내가 지금 갑을 어디에다 카피한거야 사실. 부모를 누구한테 카피한거야? 자식으로 카피한거잖아. 그 다음에 그러면 parent. 그러니까 이렇게 이동하는 화살표가 명령을 위해서 아주 간단하게 구해놓게 있다는거죠.

그러면 지금 어떻게 되나요? parent i는 얼마가 돼? i는 1이 되는 거죠. 그러면 다시 y loop를 돌아야지. y loop를 돌면 어떻게 되나요? parent 1인 상태잖아요.

얘의 부모는 누구야? 0이죠. 즉 a잖아. a. 걔는 0 이상이죠. 그러니까 다시 또 y looper 안내 들어와서 i는 얼마가 돼? i는 0이 된다고. 그쵸? 그 다음 또 돌아야겠죠? parent 0. parent 0은 뭐예요? 늑수잖아. a.

그러니까 얘는 값이 얼마야? -1. 그러면 이 y로프를 돌지 않고 깨고 나오는 거죠. 그러면 i는 얼마인 상태야 지금? i는 얼마인 상태에서 나왔어? 0인 상태로 나온 거죠. 그러니까 lm의 부모 i는 누구다? a다 라고 하고 나온 거예요. 이렇게 이해되죠?

똑같이 j는 내가 안할게 j는 똑같이 하는거야 j는 지금 3이 들어왔잖아 3이 들어가면 또 j가 0이 나오겠죠 그쵸? 그래서 지금은 어떻게든 2랑 d는 분모가 모두 몰라요 그러니까 ij가 같아 그러니까 저게 돌아 안돌아 안돌아

안 돌고 같지 않을 때만 얘 리터는 1을 한다는 거 찾았다. 엣지를 찾았다는 뜻이야. 같지 않아야지만 내가 선택할 수 있잖아. 같지 않을 때만 1이 리터인데고 같으면 0이 리터인데 저기 잘못 쓰여진 게 있죠. 0이 리터인데죠.

난 지금 E랑 D는 같잖아요 그래서 어떻게 됐어? 이걸 만족해, 만족하지 않으면 만족하지 않으니까 뭐가 리턴될? 거짓인 상태로 이 항수에 0이 리턴된다 그렇죠? 그래서 이 Find Set을 가지고 우리가 엣지를 힙을 가지고 선택을 막 쫙 할 거 아니야 그렇죠? 그때 얘도 같이 돌아야 된다 Find Set도 계속 같이 돌면서 얘가 1인 애들만 그중에서 딱딱딱 골라낼 수 있도록 0인 애들을 고르면 안 된다 오케이?

그 다음 union set은 아까 연결해 준다는 거였잖아요. 그러니까 한 놈을 하나의 자식으로 만들면 되잖아. 아주 한 줄이면 돼요. 이렇게. 그렇죠? 이건 예를 들면 어떻게 된 거야? parent 아까로 치자면 a의 부모가 누가 되는 거예요?

아이가 되는거죠. 아인가 맞아? 맞죠. 이런식으로 되는거죠. 그렇죠? 카피하는거니까. 어소시에이션 값을 부모, 이게 무슨 뜻이야? 어소시에이션 값을 너 LM의 부모로 해라 라는 뜻이죠. 그렇죠? 어소시에이션 값을 LM의 부모로 해라 라는 뜻이죠. 카피했으니까.

그러면서 결합이 되는거죠. 그렇게 하면서 이제 트리를 만들어 나가는거다. 네트가 같지 않으면 네트는 할 수 있는거죠? 그러면 그런 애들 찾아서 스페인 트리 만들어야 될거 아니야. 그렇죠? 이렇게 쭉 만들어 나간다. 질문. 내가 형광페로 칠한 부분이 핵심적인 어떤 코리니까?

이런걸 자꾸 생각해낼 수 있어요 어떻게 하면 아까 이렇게 화살표로 가는 이렇게 가면 되겠다 이렇게 탐색해 가면 되겠다 라는 생각을 하시기를 구현할 때 이런 생각을 할 수 있어야 된다는 거죠 자 그러면 이제 여기서 다시 돌아가서 우리가 find set을 이용해서 한다고 했으니까 이때는 뭘 한다?

이제 find set이 얼마를 return해? zero를 return하니까 여기 선택을 하지 않는다는 거죠 나머지 앞에 여기 거 쭉 선택했던 애들은 find set이 다 뭐를 return해서? 다 1을 return해서 어떻게 해서? 다 붙였다고 스페인 털링에다가 그렇죠?

붙여놨는데 이제 지금 이 AAD인 부분을 선택을 받지 못했다는 거죠. 사이클리 데이프. 그리고 나머지는 똑같아요. 나머지는 이제 또 다음에 이제 3인 거 찾고 그러다가 언제 멈춘다고 4인 걸 찾고

이제 주면 된다. 이게 이제 cross-card 알고리즘이다. 그래서 cross-card 알고리즘은 휴도코드 여기 중요한 문제 아까도 말했지만 이제 노드가 기준이 아니라 뭐가 기준이다고? 엣지가 기준이야. 그래서 우리가 여기 엣지라는 스트로트를 새로 만들 거예요. 이 엣지 스트로트를.

대단한건 아니고 보면 어떻게 되어있어요? 엣지는 예를 들면 어떻게 생겼어요? 엣지라는건 두 개의 노드가 필요하지 이렇게 그렇죠? AB 이 엣지 E1을 표현하고 싶어 E1이라는 엣지를 표현하려면 AB가 필요해 두 개의 노드 두 개를 다 써줘야 돼 V1, V2 그 다음 웨이트는 가중치가 되어있죠? 그래서 이렇게 간단하게 엣지 스트록처를 만들고 해야 된다

이거 뭐 시험을 떠나서 여러분 잘 알고있어야 노드 이걸 기억해야 노드를 중심으로 푸는 알고리즘이 있고 엣지를 중심으로 푸는 알고리즘이 뒤에서도 계속 이렇게 나올 수 있다는 거예요 자 그래서 한번 볼까 이렇게 만든 엣지 스트로트를 가지고

Tree Initialize for Set Representation Tree Initialization 한다 어? 그 다음 힙을 쓰니까 힙, 힙 initialize 뭐예요? N 힙이었나? N 힙이 0 간단했지 그 다음 힙을 Generation하는데 뭘 이용해서 배치를 이용해서 한다

엔지가 아니라 엣지를 이용해서 힙을 셔너리션입니다 자 그래서 힙이 MT가 아닐 때까지라는 뜻이에요

힙이 MT가 아니면 뭘 해야 되냐면 팝을 해야지 항상 팝을 해서 엣지를 팝하는 거죠 힙에 엣지가 들어있는 거야 노드가 아니라 highest priority 갖고 있는 엣지를 이제 팝해서 꺼내야겠죠 그게 방법이 그 다음 여기서 항상 우리는 뭐했어 PFS에서는 노드를 꺼내 방문하고 어떻게 했어

나랑 연결된 친구가 다 푸트 했잖아. 여기 엣지를 꺼낼 수 없다는 거예요. 엣지를 꺼낼 때 일단 검사를 해야 돼. 누구 검사해야 돼? Does not make the cycle. 사이클을 꺼냈는데 사이클을 만들면 다시 넣어야 돼. 완전 꺼내면 안 돼. 이거 보려고 살짝 들었는데 얘가 엣지를 만들지 않으면 그때 꺼내는 거예요. 꺼내고 엣지만 계속 꺼내 나가서 유니언을 시키면 되는데 내가 엣지를 만들면 어떻게 해야 된다?

아 어떻게 됐어? 여기 엣지가 아니면은 이제 스페인 트리에 붙여 나가는 거죠. 이게 무슨 말이야? 방문이라는 뜻이지. 방문. 그 엣지를 방문. 그 다음에 엣지 수를 증가시켜야겠죠. 왜? 이 터미네이크 컨디션 만들기 위해서 엣지의 수가 점점 증가한다. n이 그래서 v-1이 될 때까지 이렇게 됐어.

밑에는 터미네인컨 이슈. 간단하죠 사실은. 그래서 엣지를 우선순위 가장 높은 엣지를 꺼내서 스페이닝 트리에 붙여 나가기만 하면 됩니다. 그런데 꺼낼 때 스페이닝 트리에 붙일지 말지는 누가 결정한다? find set이 결정한다는 거죠. find set의 값이 0이 리턴되면 붙이면 안 된다는 거예요. 그렇죠? 사이클을 만들기 때문에 붙이면 안 된다.

이게 crystal 알고 있습니다. 이걸 그대로 코드로 옮긴 내용이 되겠습니다.

자 그래서 여기 보면 뭘로 돼 있어요? 인풋이 Node야, Edge야. Edge Structure로 인풋이 들어가죠? Edge Structure로 인풋이 들어가고 그 다음에 뭐 줄 때 있고 Find Any V 그렇죠? 뭐예요? Find Set에 그냥 뭐 V

초기화는 뭘 어떻게 해야 되는지 한번 생각해 주세요 parent 초기화인데 예를 들면

처음에 parent 값은 다 -1로 처음엔 다 root로 초기화하는 그런 부분이 있어요 그다음 pqinit 힙도 초기화 해 놔야겠지? n힙이 0였나? 그렇죠? 그 다음에 이제 힙을 구성하는 거 여기 다 뭐예요? 누구 기준이야?

엣지 기준이죠. 엣지 기준으로 V가 아니라 누구 기준? 엣지 기준으로 우리가 힙에다가 누구를 넣는다? 엣지를 넣어줘야 된다 하는 거예요. 자, 그래서 여기까지 하면 초기화과의 힙을 일단 만들었어요. 우리가 퓨스카 알고 힙 만드는 게 목적이 아니잖아요. 방문을 해야 되잖아요. 방문은. 그럼 힙에다 놓물을 꺼내고

방문할 때 전략이 뭐다? 가장 우선 지금 다 힙에는 뭐만 들어있다? 엣지만 들어있다. 그래서 엣지만 들어있는데 그 엣지에서 뭐 PQExtract를 해야겠죠. 꺼내야 되니까 가장 우선순위가 높은 힙에서 엣지를 꺼내면 된다.

그리고 꺼냈고 그 다음 뭐하면 돼요? 이게 앞에랑 그대로 이어지죠? top이라는 게 사실은 get, q니까 그래서 그 다음 뭐한다고 써 있어요? if edge does not make the cycle 판단해야 돼요. 우리는 그걸 뭘 가지고 해요? find set을 가지고 하죠? 그래서

두 개의 노드를 넣어줘야 되잖아 부모가 있고 지금 이 부모에 딸린 애가 두 개가 있는데 얘 두 개를 연결한 엣지를 쓸 건지 말 건지 판단하고 있는데 그러려면 어떻게 해야 된다 두 노드를 이렇게 넣어주면 되죠 아까 봤잖아요 그쵸? 지금 가장 우선순위가 높은 엣지는 바야 바 바에다가 인덱스를 담았으니까 그거에 해당하는 지금 노드 두 개의 V1, V2를 검사를 하면 되겠죠 꺼냈으니까 근데 이게 만약에 0이면 어떻게 해요 BGC 돌지 않아 방문하지 않는다는 뜻이죠 1이면 돌아와요 1일 때는 어느 때 V1, V2가 사이클을 만들지 않을 때만 1이 리턴 되죠 그리고 union 플래그를 줬으니까 그 다음 방문하면서 얘를 스페인 트리에 붙이는 거죠 그 다음에 엣지의 수를 증가시키는 거죠

자 그렇게 해서 이걸 계속 도는데 v-1이 되면 앞에 슈터 코드랑 똑같이 코딩이 되어 있죠 그래서 알고리즘은 항상 뭐다? 컴퓨테이셔널 플러스 이즈다 그래서 이런걸 잘 짜야돼 여러분들이 그 예제를 보면 이렇게

프라시리얼 만들고 그 다음 짜는 거는 거의 원투온맵핑으로 짜일 수 있다는 걸 계속 보잖아요. 이런 절차를 항상 클리어하게 여러분들이 써내야 된다는 거죠. 항상 클리어하게 단계 단계를 써내면 그거에 따라서 코드야. 그냥 원투온맵핑 독해랑 똑같아. 영어 문장 있으면 옆에 한글로 독해하잖아요.

그거랑 똑같다고 슈도 코드 한 줄 있으면 그걸 시어놓은 코드로 독해하면 된다고 근데 이쪽이 잘 안 쓰여져 있는데 예를 들면 영어 문장 하나도 없는데 갑자기 함물로 뭘 번역하래 여기 뭐가 이상하게 돼있는데 번역이 돼야 안돼 안되잖아요 그거랑 똑같다는 거예요 그러니까 하지만 독해는 영어 문법을 배우는거죠 문법을 배우죠

여러분들 항상 강조하지만 문법이 중요한 게 아니라 그걸 써내는 사람이 되어야 된다는 거죠 영어의 한 구단을 써낼 수 있는 사람 지금 영문법은 그냥 숟가락 같은 거고 반면에 다시 한번 삼기게 한 거예요 그 다음에 여기 보면은 자 이걸 잘려면 여기 PQExtract라는 애가 있고

뭐가 또 있어요? PQInsert라는 친구가 있죠? 얘네 두 개는 다 뭘로 구성돼있어? UpHip이랑 뭘로 구성돼있어요? DownHip으로 구성돼있죠? 여기 나와있는 똑같애. 그래서 오른쪽에 나와있지만 우리 힙, 힙, 복습, 아 복습가 아니라 힙 힙을 우리 배울 때 했던거죠? UpHip, DownHip 근데 여기서 이 함수 있잖아요? UpHip이랑 똑같아요. 똑같죠? 달라진거 하나도 없죠? 여기까지는 똑같은데 UpHip, DownHip 함수까지 똑같을까? 그렇지 않다는거야. 왜? 스트록처가 바뀌었잖아 이제. 엣지로.

업힙 다운힙 할 때 거기 비교하는 부분들 있잖아요 거기에 코드를 어떻게 바꿔야 되는지 이번 시간 내가 코드를 진짜 안줌혀야 하니까 그거는 여러분들이 여기서 고쳐서 해보세요 그건 간단히 이해했으면 바로 해볼 수 있는 거니까 업힙 다운힙해서 어떤 부분을 고쳐야 되는지는 내가 다 알려줬어 엣지 스트럭처를 쓰니까 엣지 스트럭처에 맞게끔 비교 될 수 있게끔 거기에 고치라는 거죠 오케이 지금 인서트랑 인스트랙트는 다 똑같아

자 이게 다에요. Up-Heap Down-Heap이 만들어지면 PQ Insert PQ Extract를 만들 수 있고 이걸 가지고 Fru-Scal Algorithm을 짤 수 있다는 거죠. 힙이 이렇게 중요해. 우리의 Weighted Graph를 방문할 때 두 가지 전략, Prime-First Search랑 Fru-Scal Algorithm 두 가지 알고리즘을 배웠는데 다 뭐를 기반하고 있어요? 다 힙을 기반하고 있어요. 왜냐면 그럴 수밖에 없는 게 Weighted Graph라는 거는 그러니까 어떻게 구성되어 있으니까 가중치 덩어리거든 가중치 덩어리를 담을 수 있는 통이 우리가 알고 있는 힙 밖에 없다고 지금 같아요.

그러니까 다 힙을 쓰게 되어있다는 거죠 그래서 업힙 다운이 위 PQE 이렇게 해서 힙을 자유자재로 다루는 게 되게 잘 능수능력이 여러분 연습이 되어야 된다 그리고 이 뒤에 배울 그래프들은 다 이제 가루치가 있어 이게 더 의미가 있잖아요 그렇죠? 실생활에서 왔다 하는 거죠 예제적 자리입니다

자 그래서 여기 보면 메인펑션 그래서 그래프 지난 시간에 우리가 이미 그래프를 이제 더이상 타이핑하지 않고 텍스트를 읽을 수 있게 만들어놨죠 자 그래서 그래프를 이제 뭐 그래프.txt 어 안가졌네 그 이거 지난 시간 꼭

똑같아요 그래프 여기 지난 슬라이드 보면 node 개수, etch 개수를 한다면 쫙 써놓은거 있죠 그거 그대로 지난 시간에 썼던 txt 사용하면 됩니다 자 그렇게 해서 쭉쭉 보면은 아 그 다음에 우리가 또 해볼 수 있는게 뭐냐면 여기 뒤에 나오겠지만 좀 더 직관적으로 우리가 포스트를 계산할 수 있다는 거죠 왜냐면 플러스카라 알고지면 내가 etch를 선택하잖아

그러니까 바로 뭐가 나와? 바로 가중치가 얼마가 나오잖아요 내가 이걸 다 더한 포스트를 얻고 싶다 그럼 코드를 어떻게 짜려면 한 줄이면 되겠지 어떻게 해요? 그냥 누적시키면 되지 이렇게 아까 우리 엣지에는 두 개의 노드도 있지만 가중치도 같이 갖고 있는 스트러쳐죠 그러니까 엣지 값을 그냥 누적만 하면은 내가 이 방문하고 났을 때 발생하는 비용을 계산할 수 있다 없다? 계산할 수 있다 라는 거죠

비집 할 때마다 이 함수 돌아가면 될까 내가 방문 할 때마다 누적 시켜주면 되잖아요 방문 할 때마다 누적 시키면 되잖아 그 답을 그러니까 비집 함수에 한 줄만 추가해놓으면 되지 그리고 cost는 global variable로 만들고 자 그래서 다시 처음 메인 펑션 보면은 뭐 이거 블라블라

그 다음에 parent 그 다음 white, white, or tree인데 자 그 다음에 cost global로 돼있고 and heap을 위한 heap이 길이니깐 변하죠 그 다음 heap을 또 따로 저장해야 되니까 그 다음에 우리가 쓸 오늘의 structure는 뭐다? 요 부분 우리가 오늘 사용할 부분은 요 부분이죠 etching 소문자를 쓰면 안 돼요 왜냐하면 structure 이름이 etch죠 그러니까 요게 또 소문자를 쓰면 structure 이름이랑 시언어가 구분을 못하니까 그래서 대문자를 쓰면 헷갈리면 다른 이름을 쓰세요

그래프라고 쓰던가고 마음대로 이렇게 써도 돼요 small h는 structure 이름이니까 내가 구분하기 위해서 variable는 structure array는 저렇게 되면 잘 썼다 그 다음에 나머지 find in은 내가 뭐라 그랬어요? parent를 -1로 그냥 초기화하는 그런 함수라고 그랬죠?

그래서 인풋 엣지 이거는 파일로 읽을 수 있게끔 코드를 제공했어요 또 못할까봐 지난주까지는 엣지 타입이 아니었잖아요 이전 V1 VT이 아니었잖아요 그래서 못할까봐 바꿔 하면 못 바꾸니까 그대로 코드 있으니까 그대로 사용하세요 그러면 파일을 엣지로 읽어둘 수 있다는 거죠 엣지 스트럭처럼

보면은 뭐만 달라졌어요? 달라진거죠 그렇죠? 우리 이제 이렇게 들어가잖아요 부 11에서 ab는 3이요, cd는 2요 이런식으로 들어가잖아요 그럼 얘가 뭐예요? 얘가 v1인거고 얘는 뭐예요?

그래야지 이렇게 엣지가 되는 거잖아 1이 한데 이렇게 해야지 A라는 것과 내가 지금 주안점을 두는 건 누구야? 여기 라고 여기 그냥 엣지 E1 이라는 친구인데 E1 하고 이렇게 넣을 수가 없잖아요 E1이 뭐야 도대체 A랑 B로 구성된 거지 그래서 V1, V2로 우리가 넣어주고 여기 이제 3이 있죠 그걸 표현한 게 G-STOP 선거죠.

이렇게 표현이 되어있다 오케이 나머지는 그대로 자 그래서 메인함수 보면은 엣지 입력을 받고 크루스칼 출력해보세요 그러면 순서가 어떻게 나오는지 요 그래프 이거는 지난 시간과 동일한 그래프 서울대전 대구 우산 그 그래프에요 그 그래프 가지고 한번 출력해보게 바랍니다

그럼 여러분들이 지금 해야될 건 뭐예요? UPHEAP과 DOWNHEAP을 지금 다 얘기했죠? 코드 혹시 모르는 부분 있어요? 질문 질문 코드 어떻게 우선 레인치한 질문 없어 이해했어? 큰 그림에서? 네? 큰 그림 이게 제일 큰 그림이야 API 그렇죠? 이건 다 초기화한 부분 어쨌든 힙을 써야 되니까 배치의 우선순위를 판단하기 위해서 힙을 만들어 놔야 되거든요 그래야 우선순위라는 게 정의가 되어 있기 때문에

근데 누굴 가지고 만든다? 엣지를 가지고 만든다 만들어놓고 그 다음 프루스카 알고 지금 돌아가는데 그건 매우 간단한 거야 힙에서 뭘 만하면 돼? 가장 못 쓰는 손이가 높은 엣지를 꺼내기만 하면 돼 꺼내서 스페인트 순서대로 붙여주기만 하면 돼 근데 붙여주는 건 다 함수가 돼있어 유니온 근데 붙여줄때 하나만 검사하라는 거야 뭐? 그게 사이클을 만든지 안 만든지만 검사하고 안 만들면 붙이라는 거야 그게 끝이야 프루스카

붙이는 행위가 뭐다? 방문한다는 동일하다는 것입니다. 내가 이 엣지를 스페인 트리 붙입니다는 이큐벌런트하게 방문한다는 것입니다. 이렇게 해서 도는데 여기 짜려고 보니까 pqinsert와 pqextra를 짜야 되네? pqinsert와 pqextra는 우리가 알고 있듯이 uphick과 downhick으로 인성이 되어 있는데 다 똑같은데 지금 structure가 엣지로 바뀌어 있기 때문에 그 부분만 여러분들이 좀 코딩을 바꿔주고 병을 돌려보면 불쌀 알고심이 반성이 된다

해보세요.

힙 함수는 그러니까 꼭 들고 다녀야겠죠? 힙. 당연히 들고 다니고 그냥 쫙 그대로 갔다가 쓰면 되겠죠. 바꿔서 코딩하고, 지스트로스에 의해서. 국방문, 권호준, 김동우, 김석현, 김성태,

김용진, 김재원, 김정윤, 김정은, 김채환, 김형호, 나타샤, 유성동, 박시환, 박주은, 박준영, 서상혁, 송재근, 신동민, 신주혁, 신지용, 안용준, 안지수, 양현, 검승준, 오병희, 오정민, 윤승환, 이광호, 이 난권, 이 도영, 이성근,

이소희, 이수빈, 이은상, 이창규, 이채현, 임현우, 장은태, 정유나, 정치섭, 조승진, 조승찬, 조혜은, 차지영, 최민혁, 최진우, 한석원,

So, that means that.

그러면 이렇게 순서가 가이노트와 동일하게 잘 나온다 을 확인하길 바랍니다. 그래프는 어떻게 생겼어요? 그래프를 이어갔고, 그렇죠? 가이노트 그래프 이렇게 생겼죠?

웨이트 기준 맞을까? 맞아요. 그러니까 다 거의 비슷하고요. 지금 내가 말한 거는 어쨌든 입력이 바뀌자 형태가 그것만 바꿔주라는 것입니다. 정렬한 건 웨이트 기준으로 정렬한 것 맞을까?

스포츠와 마술 나라 미리 소청하지. 그걸 마술 비공을 하는 이유가 있습니다.

the sky.

확인한 사람? 나 확인했다. 뷔스칼. 잘 나온다. 한 명도 없어? 해봐야지.

자, 안 돼요. 지금 나와서 꼭 해보긴 하면 안 돼. 그래서 반드시 이 순서를 나와야 돼요. 그래프에 기억했을 때 순서는 여기 밑에 써 있는 게 순서라고 보면 돼요. 여기 보면 jk, ac, fj, hicd,ij, 다음 ae, gh, df, ab. 이게 그렇습니까? 우리 지금 순서니까 이 그래프 가지고 꼭 구현해서 확인을 하게 된 거 같아요. 자, 그래서 여기까지가 시험법이고요. 일단 이제 그래프 리프레젠테이션, 그다음에 그래프 서치, 그렇죠? dfs, bfs.

그 다음에 한 가지 더 보였죠? Articulation Point. 그 다음에 넣은 게 뭐예요? Weighted Graph. Weighted Graph의 두 가지 서칭 방법은 PFS, New Style. Weighted Graph의 서칭 방법은 다 뭘 기반하고 있다? HIP을 기반하고 있다. HIP을 자유자재로 잘 다룰 줄 알아야 돼. 형태가 변해도 컨셉을 잘 유지하면서

우리가 프라이어티 서치에서 썼던 힘이라던가 코스쿠에서 썼던 힘이 사실 다 같아요 어떤 태가 비슷하다고요 그렇죠? 그런 것들을 다 볼 수 있는 클리어인데요 코드는 다 기본적으로 알고 있어야 돼요 자, 우리 마치 시험 다음 주 화요일에 봅시다 시험이에요 우리 어디지? 아 그렇지 B473인가 우리? 그렇죠? 다 골라요

한시 반 공지사는 참조하세요 기원시

Thank you.

What's your answer? What's your answer? What's your answer? What's your answer? What's your answer?

Thank you.

ご視聴ありがとうございました

ご視聴ありがとうございました

I'm not sure what you're doing. I'm not sure what you're doing. I'm not sure what you're doing. I'm not sure what you're doing. I'm not sure what you're doing. I'm not sure what you're doing. I'm not sure what you're doing. I'm not sure what you're doing. I'm not sure what you're doing. I'm not sure what you're doing. I'm not sure what you're doing.

Вон еще.

I was not going to do anything. I'm not going to do anything. I'm not going to do anything. I'm not going to do anything.

I knew it was hard to say,"Oh, do you know this?" I knew it was hard to say,"I love it." I knew it was hard to say,"Oh, that's what I was doing." To go to the space, I knew it was hard to say,"I'm not going to be on my arm." I knew it was hard to say,"I'm not going to be on my arm."

그래서, 나는 진짜 이렇게 잡을 이럴나. 그래서, 나는 지금 더 마음을 안고서, 저흥을 한 게, 내가 당연히 좋지. 그런 마음을 다 안 쓰지. 나는 그냥 매몸가 좋은 사람을 내 몸이 좋은 것 같아요.

Ich bin ein bisschen auf die Karte, die ich mir nicht so gut bin. Ich bin ein bisschen auf die Karte, die ich mir nicht so gut bin. Ich bin ein bisschen auf die Karte, die ich mir nicht so gut bin. Ich bin ein bisschen auf die Karte, die ich mir nicht so gut bin. Ich bin ein bisschen auf die Karte, die ich mir nicht so gut bin.

어떻게 해야 할까요? 상무일에 대해 얘기해 주십시오. 응? 너? 스티치. 이렇게. 이렇게. 이렇게. 이렇게. 이렇게. 이렇게. 이렇게. 자. 지금 두 번 주십시오. 종료 배우니까. 시험 갑니다. 네.

지난 시간에 배운 내용이'3'라는 것은 결국 모두의 스트럭처다. 그래서 어떻게 생겼어요? 핸드. '3'가'4'죠.