본문 바로가기

컴퓨터/C,C++6

[알고리즘] 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] C의 qsort는 어떻게 짰을까? (유명 석박사들의 코드 훔쳐보기), shift 연산을 해야하는 이유 반갑습니다!!! ​ 오늘은 저녁에 뭔가 인강듣기는 싫고,, 복습하기도 싫어서 C언어의 소스코드는 어떻게 생겼나 훔쳐봤습니다. ​ 여러가지를 보다가 재미있는걸 발견했는데, 공유하기 위해서 저도 씁니다^^ ​ c++의 sort는 여러가지 소트를 합친걸로 알고있습니다. Tim,intro, heap,quick 등등.. 여러개를 합쳤는데요. ​ 예전에 알고리즘 수업에서 과제 중 하나가, 어떤 숫자에서도(숫자 몇십억개가 넘는) 가장 빠른 정렬을 할 수 있는 코드를 짜는게 숙제였습니다. 그걸로 학생들의 시간을 측정해서 차등으로 성적을 매겨줬습니다. ​ 그때 굉장히 많이 찾아봤었는데, 저는 median-of-three라는 pivot 설정으로 quicksort를 짰는데, pivot 고르는걸 잘못했는지.. 어디 하자가 있.. 2021. 7. 31.
[C++] STL 기초 (range_based for문) vector 안녕하세용!! STL Vector에서 for(int i = 0; i < v.size() ; i++) v[i] 이런것에 너무 익숙해져서 남들도 다 쓰는 자동반복을 연습해보도록 하겠습니다. #include #include #include #include typedef long long ll; using namespace std; int main() { int size; int num; int temp; vector v; scanf("%d",&size); for(int i = 0; i < size; i++) { scanf("%d",&num); for(int k = 0; k < num; k++) { scanf("%d",&temp); v.push_back(temp); } sort(v.begin(),v.end()).. 2021. 1. 30.
[C언어 기초] 범위를 넘어가는 수를 저장할때 주의할것 (int 의 합이 long long인경우) 아.. 이거 제목을 어떻게 지을지 너무 고민했다. 아니 이거를 어떻게 설명하지 ... ​ int a, int b 의 합이 long long 인 경우에 #include typedef long long ll; int main() { ll sum; int a = 1111111111; int b = 1111111111; sum = a+b; printf("%lld",sum); } 이건 오류가 난다. 왜일까? 분명 범위내에 들어가는 수를 저장한 a와 b를 더해서 그걸 바로 long long에다가 옮겨준것인데.. ​ 이걸 인터넷에 어떻게 검색해야할지 몰라서 그냥 직접 까봤다. 리눅스에서 gcc file.c -S -o file.S 를 하면 assembly 코드를 볼 수 있다. vim file.S 로 파일을 열어보면 인.. 2021. 1. 20.
[자료구조] 계산기 C코드 (괄호포함,스택) 오늘은 계산기를 해보곘습니다. 지금에서야 올리는 여러가지 이유가 있지만 ^^ 많이 방문해주세요 ^^ ​ 계산기에 없는 기능 : 2자리 이상 계산은 안됨( 사실 2탄으로 한번 더 빼먹으려고 참는중) 13/36은 안됨. but 기본 연산 됨 이런 느낌으로 보면 됩니다. ​ 아마 여기까지 찾아온거면 기본적인 중위표기식 -> 후위표기식 바꾸는건 다 알것이라고 생각합니다. stack은 C로 그냥 가볍게 구현하시면 됩니다. (나중에 포스팅해서 여기에 링크 걸 예정) ​ 구현의 핵심 1. infix -> postfix로 바꿔야함 2. 연산자 우선순위 고려해야함 ​ 구현 방법 1. 처음에 expression을 배열로 받는다 2. 연산자 스택, postfix 배열을 만든다 3. '숫자'면 postfix 배열로 바로 보낸.. 2021. 1. 7.
728x90

티스토리툴바