lgvv98

크루스칼 알고리즘과 위상정렬 백준 알고리즘: 최소 스패닝 트리에서 연습할 수 있습니다. ✅ 서로소 집합 6개의 노드가 주어지는데 각 연결 관계는 6 4 1 4 2 3 2 4 5 6 으로 주어집니다. 여기서 각 노드를 비교하고, 노드 번호의 부모를 업데이트 하면서 결국은 사이클이 형성되는지 찾을 수 있습니다. 하지만 이 경우 시간 복잡도에 큰 손해가 발생하는데, 이를 단축시키고자 경로 압축 기법을 사용하곤 합니다. * 경로 압축 기법이란? - find 함수를 재귀적으로 호출하여 부모 테이블 값을 갱신하는 방법입니다. 오늘 주로 알아 볼 내용은 크루스칼 알고리즘이므로 서로소 집합에 대한 내용은 아래 포스팅을 참고해주세요! https://velog.io/@syc1013/%EC%95%8C%EA%B3%A0%EB%..

chapter 8. DP ✅ 다이나믹 프로그래밍(DP)에 대해서 알아보자! DP는 학교 수업시간에 피보나치를 공부하면서 계산한 부분을 계산하지 않는 것으로 배웠는데, 그 당시에는 그게 DP인지 몰랐음 알고리즘을 풀면서 DP와 같은 문제들을 잘 못푸는데, 이번에 공부해 보니까 그 사고를 얻어서 조금 자신감도 생김 수능때도 점화식 문제에 유독 너무나도 약했는데, DP는 점화식이 거의 베이스네..? 아무튼 열심히 해보자. ✅ 1로 만들기 점화식을 이용하던데, 특정한 작은 값을 정해서 직접 그러보면 문제를 만드는데 도움이 많이 된다. 또한, 보텀업 방식으로 계산하는게 조금 더 이득이 있다고 하고, 엄청 어렵지도 않으니까 한번 해보자. 비슷한 문제를 백준에서 찾아 풀어보자. 🟠 백준문제 알고리즘을 점화식을 만들어..