자료구조3 [알고리즘] Prim`s algorithm. MST 구하는 2번째 방법. 프림 반갑습니다. 이번엔 O(ElogV) 시간복잡도를 가지는 Prim알고리즘에 대해서 알아보겠습니다. 이건 음.. heap을 알아야 하는데, 힙구조를 가지는 priority_queue를 사용할 수 있으면 좋습니다. 없으면 kruskal이 구현하기 더 낫습니다. Kruskal VS Prim 결과부터 말하면 Edge가 많으면 Prim, Edge가 적으면 Kruskal이 좀 더 좋습니다. (이론상) Kruskal은 sort과정에 O(ElogE)이 피할 수 없기에 E에 영향을 받고, Prim은 O(ElogV)입니다. 이미 방문된 지점은 다시 방문되지 않기에 pq의 push나 pop과정이 없어서 그렇습니다. 근데 MST를 찾는다는건 기본적으로 V < E니까 쓰겠죠...? 근데 그냥 편한대로 합시다. .. 2021. 10. 2. [자료구조] MST를 구할 때 사용하는 크루스칼 알고리즘(Kruskal) 설명에 앞서, Union - Find 연산에 대해서 학습을 해야하는데, 이 부분은 제가 봤던 유튜브로 대체하겠습니다. https://www.youtube.com/watch?v=eTaWFhPXPz4 이것과 Optimized Union/FInd를 보시고 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 이 문제를 풀어서 제대로 이해했나 확인해보시면 됩니다. Kruskal 알고리즘을 왜 쓰는가? - MST를.. 2021. 9. 30. [자료구조] 계산기 C코드 (괄호포함,스택) 오늘은 계산기를 해보곘습니다. 지금에서야 올리는 여러가지 이유가 있지만 ^^ 많이 방문해주세요 ^^ 계산기에 없는 기능 : 2자리 이상 계산은 안됨( 사실 2탄으로 한번 더 빼먹으려고 참는중) 13/36은 안됨. but 기본 연산 됨 이런 느낌으로 보면 됩니다. 아마 여기까지 찾아온거면 기본적인 중위표기식 -> 후위표기식 바꾸는건 다 알것이라고 생각합니다. stack은 C로 그냥 가볍게 구현하시면 됩니다. (나중에 포스팅해서 여기에 링크 걸 예정) 구현의 핵심 1. infix -> postfix로 바꿔야함 2. 연산자 우선순위 고려해야함 구현 방법 1. 처음에 expression을 배열로 받는다 2. 연산자 스택, postfix 배열을 만든다 3. '숫자'면 postfix 배열로 바로 보낸.. 2021. 1. 7. 이전 1 다음 728x90
