반응형 Programming/Algorithm(알고리즘)4 최소신장트리 (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. 이전 1 다음 반응형
