반응형 알고리즘6 최소신장트리 (MST) 핵심 코드 | c++ 최소신장트리의 가장 기본이 되는 코드입니다. 해당 유형의 문제들은 다 이 코드를 수정해서 풀이할 수 있을 것입니다. 사실 최소신장트리의 핵심은 union find 이기 때문에 최소신장트리라고 지칭하는것 보다 union find 응용 문제라고 하는것이 더 나을지 모릅니다. int parent[10001]; struct node { int start; int end; int dist; node(int a, int b, int c) { start = a; end = b; dist = c; } }; struct compare { bool operator()(node a, node b) { return a.dist > b.dist; } }; priority_queue v; int find(int u) { if(u.. 2021. 2. 19. 자료구조-펜윅트리 핵심 코드 | c++ 잦은 업데이트와 합을 구하는데 사용되는 펜윅 트리입니다. 코드가 암기만 하면 너무 간단하여 저는 인덱스트리보다 펜윅트리를 선택했습니다. 뭔가 인덱스트가 조금 더 범용적으로 사용된다긴 하지만 저는 제 기억력의 한계를 알고 있기 때문에 펜윅트리로 정착했습니다. 업데이트 코드입니다. int tree[100]; void update(int a, int diff) { while(a 0) { ans += tree[a]; a -=(a & -a); } return ans; } 확실히 인덱스 트리보다 훨씬 더 코드가 간결하고 간단합니다..... 이제 남은건.. 2021. 1. 29. 그래프-다익스트라 code | c++ 그래프에서 한점에서 한점까지 최단거리를 계산하는데 사용되는 다익스트라 알고리즘의 핵심 코드 입니다. void dijkstra(int start) { //시작 지점 넣고 d[start] = 0; priority_queue pq; pq.push(node(start, 0)); //포문 돌린다. while (!pq.empty()) { //현재 위치 거리 꺼내고 int current = pq.top().next; int distance = pq.top().distance; pq.pop(); //최단거리가 아닌경우 스킵 if(d[current] < distance) continue; //현재에서 이어져있는 모든 노드 호출 for (int i = 0; i < arr[current].size(); i++) { //선택.. 2021. 1. 29. 시간복잡도와 공간복잡도 개념. 알고리즘 초보라면 필독!! 알고리즘 공부를 시작함에 있어서 시간복잡도와 공간복잡도의 개념은 알고리즘 평가의 기본이 되는 개념입니다. 규모가 크거나 매우 복잡한 컴퓨터 프로그램을 개발할 때는 해결해야 할 문제를 제대로 이해해서 정확히 정의하고, 그 복잡도를 관리하고 구현하기 쉬운 작은 작업으로 분리하는데 가장 많은 노력이 투자되어야 합니다. 그러기 위해서는 복잡도 분석을 할 수 있어야합니다. 그렇기 때문에 알고리즘 평가의 기본이 되는 개념이 복잡도 개념인 것입니다. 복잡도의 개념은 크게 두 가지가 있습니다. 바로 시간복잡도 (Time Complexity) 와 공간복잡도 (Scpae Complexity)입니다. 재밋게도 저 둘은 사람들에게도 가장 중요한 자원들입니다. 이 두 자원을 어떻게 관리하냐가 알고리즘과 더 나아가서 프로젝트 전.. 2020. 5. 5. [맥] 맥에서 C++ 사용하기!!! 하 얼마전에 윈도우 노트북을 정리하고 맥으로 넘어왔다. 이런 저런 이유는 포스팅으로 작성해 놨다. [맥] 씽크패드(윈도우)에서 맥북 16인치로 바꾼 이유!!! 새 해 계획을 짜던 도중에 계속 윈도우 노트북의 팬소리와 발열이 거슬렸다. 내가 집에서 컴퓨터를 사용하는 용도는 아주 일반적인 용도이다. 넷플릭스, 유튜브, 인터넷, 일기 블로그 작성등 문서 업무 등등 모두.. kinotion.tistory.com 그런데 회사에서 준비하는 시험이 C++을 사용해야하는데 물론 맥에서 부트캠프로 윈도우를 사용할 수 있지만 껏다 켰다 하기 귀찮아서 웬만하면 맥에서 내가 필요한 기능들을 다 사용하고 싶었다. 그래서 맥에서 C++을 사용하는 법을 알아봤다. XCODE!! 가장 간단한 방법이다. 맥에서는 기본 개발툴로 XCo.. 2020. 2. 1. 알고리즘에 쏠쏠한 swap 함수 알고리즘 문제를 풀다보면 정렬을 해야할 경우가 많이 생긴다. 정렬의 기본적인 로직은 A B 두 항목을 비교해서 설정한 로직에 따라 순서를 바꾸는 것이다. 조건에 따라서 이런 정렬을 자주 해야하는데 거기서 A B의 순서를 바꿔주는 행위는 필수 적이다. 이걸 지금까지 매번 구현했었는데.... algorithm에 구현되어 있는 걸 얼마 전에 알았다. 그 이름도 너무도 직관적이게 swap!!!!!!! 물론 알고리즘 expert 레벨에서는 include를 할 수 없기 때문에 전부 자기가 구현해하기 때문에 장기적으로 보면 모두 다 바로바로 구현할 수 있는게 시험을 대비하는데는 좋겠지만.... 이미 아는 로직에 더 이상 불필요한 시간을 할애하지 않아도 되니까! [사용법] 1. 라이브러리 호출 #include 2. 사.. 2019. 8. 20. 이전 1 다음 반응형
