-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
메모이제이션 관련 질문있습니다.
22.07.03 16:46 작성 조회수 174
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 1:1 문의하기를 이용해주세요.
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 1:1 문의하기를 이용해주세요.
안녕하세요 강사님 좋은 강의 감사드립니다.
한 가지 이해가 되지 않는 부분이 있어 질문드리려고 합니다.
트리를 일일이 뻗지 않게 하려고 메모이제이션을 쓴다고 뒷부분에서 말씀하셨는데,
26분 13초에 그림을 보니 unf[v] = Find(unf[v])를 하는 것 자체가 계속 가지가 뻗는 것처럼 보입니다.
그냥 가지를 뻗는 것과, 메모이제이션이 똑같다는 느낌을 받는데, 혹시 차이가 정확히 어떤 것인지 궁금합니다.
답변을 작성해보세요.
0
네오플들어가자꼭
2023.08.22
해결하셨는지는 모르겠지만 답변이 없어서 제가 대신 답변드려봅니다!
말씀하신대로 26분 13초에 가지를 뻗는 건 맞습니다. 다만 나중에 두 사람이 친구인가의 관계를 확인할 때 차이가 있습니다.
unf[v] = Find(unf[v]) 를 안 할 경우
: 나중에 3과 8이 친구인가를 확인할 때 Find(3)과 Find(8)을 한 후에 두 값을 비교해야합니다. 이 때 가지를 2번 뻗어서 찾아야하는 소요가 있습니다.
unf[v] = Find(unf[v]) 를 할 경우
: 이 때는 unf[3]과 unf[8] 두 값이 같은지만 확인하면 됩니다.
도움이 되셨기를...!
답변 1