반응형 알고리즘/알고리즘 정리3 크루스칼 알고리즘(kruskal Algorithm), 최소 신장 트리(MST) c++ 구현 우리는 흔히 알고리즘 문제를 풀다보면 적은 비용으로 연결! 하는 문제를 자주 접하게 되는데요. 자주는 보지는 않지만 가끔씩 보면 까먹기 마련입니다. 저도 까먹고 풀다가 어..? 크루스칼 알고리즘인데 하는 생각이 들어서 이번에 다시 기억하고자 포스팅을 하려합니다. 크루스칼 알고리즘 (Kruskal Algorithm) -> 최소신장트리(MST) 구하기 위해 사용 앞서 위에서 말씀 드린듯이 적은 비용으로 연결하는 것이 핵심입니다. 무방향으로 연결된 노드와 간선이 주어졌을때 우리는 간선의 가중치(비용)에 대해서 모든 노드가 연결이 되어야 하는데 가중치(비용)이 최소화 되는것을 찾을때 사용하게 되는 알고리즘입니다. 최소 신장 트리(MST)가 뭐야? 신장 부분 그래프 (Spanning tree)에서 사용된 간선들의.. 2023. 7. 6. 투포인터 알고리즘(Two-Pointer Algorithm)이란? (예시,활용코드) Two Pointer 알고리즘이란 1차원 배열에서 두개의 포인터를 활용하여 원하는 결과를 얻기 위한 알고리즘입니다. 보통 연속된 수의 합이 충족하는 갯수를 구하게 되는데 dfs로 풀게 되면 엄청난 시간복잡도를 야기하게 됩니다. 이를 위해 1차원 배열에서 두개의 포인터를 이용하여 경우의 수에 대해서 마지막에 도달할 경우 값을 구할 수 없어 종료를 시키게 합니다. 시간 복잡도는 O(n)으로 굉장히 알고리즘 문제에서 가끔씩 사용하게 됩니다. 예시의 이해를 위해 우리가 주어진 1차원 배열에서 합이 6인 숫자들의 케이스를 모두 카운팅하는 것에 대해서 예시를 들어보겠습니다. 배열 예시 [1,2,3,3,6,5,1] 원하는 합이 6이 되는 연속된 숫자들의 조합 갯수 투포인터 활용 설명 합이 6보다 작을때는 end의 인.. 2023. 6. 28. 알고리즘 공부 방식,순서 (개인적인 경험) 안녕하세요 아직도 알고리즘에 대해서 항상 문제를 풀고있고 취업을 위해.. 항상 열심히 하고 있는 개발자 지망생중 하나입니다. 아직 실력도 많이 부족하고 알고리즘 걸음마 뗀것 같지만 그래도 알고리즘을 시작하거나 아직 막막하신 분들을 위해 몇자 적어보고자 합니다 😀 알고리즘이란?누구나 항상 개발자 지망생이라면 매일같이 하는 말이 "1일1알고리즘.." 이라는 말을 입에 붙혀산다고 생각합니다. 개인적으로는 취업을 위해 그리고 아직 경험을 못해봤지만 현업에서도 실무를 처리를 위해 알고리즘에 대해서 공부를 하곤 합니다. 내가 꿈꾸는 그리고 지금 이글을 보고 계신 모든분들이라면(사실, 현업자분들은 알고리즘 공부방식에 검색해서 보지 않을꺼라 생각합니다.) 효율적으로 공부를 하고 싶고 저 또한 항상 그럽니다. 개인적으로.. 2023. 6. 26. 이전 1 다음 반응형
