백준24 [알고리즘 분류] - 최소 스패닝 트리 MST는 2가지 방법으로 구현할 수 있는데, 하나는 Prim이고, 다른 하나는 Kruskal 이다. 나는 대부분의 문제를 Kruskal 로 풀었는데, 주어진 문제들이 대부분 Sparse Graph 였기 때문이다. Kruskal는 모든 edge를 오름차순으로 정렬하고, 앞에서부터 (작은 순서대로) 판단을 하는데, 해당 edge의 양쪽 node가 같은 Group에 속해 있으면 연결하지 않고, 같은 Group에 속해있지 않으면 연결한다. node의 갯수가 N개일 때, 연결한 edge가 총 N - 1 개가 되면 멈춘다. 같은 Group인지를 판단할 때 Union-find 알고리즘을 그대로 사용한다. (매우 단순하다) edge를 정렬하는 단계에서 ElogE의 시간복잡도가 발생하고, edge를 선택하여 group을.. 2020. 7. 14. [단계별로 풀어보기] - 유니온 파인드 Union Find는 각 대상들이 어떤 집합에 속하는지에 대해 파악하는 알고리즘이다. 하나의 배열로, 각 대상이 index로, value가 parent, 즉 해당 집합을 대표하는 number로 지정된다. 처음 초기화는, parent[i] = i 로 해주고 parent를 찾는 건 배열에 대한 탐색을 재귀적으로 찾되, 재귀적으로 찾은 결과를 현재 값에 적용시켜야 한다. return parent[n] = find_parent(parent[n]) 가 최적화의 핵심이라고 할 수 있다. 공항 문제는, 문제 자체가 이해가 되지 않아서 미루었다. 2020. 7. 7. [BOJ] 단계별로 풀어보기 - 우선순위 큐 잠이 안와서 단계별로에서 이분탐색을 풀다가 멘탈이 나가서 만만한 우선순위 큐를 풀었다. 내일은 어떻게든 이분 탐색 문제를 다 풀어야지.. C++에서 STL을 이용하여 우선순위 큐를 사용할 수 있다. 근데, 이게 너무 편해서 한번 맛 보면 자꾸 생각나게 된다. int에 대한 priority queue를 구성하는데, less와 greater template를 이용해서 여러 자료형에 대한 비교 연산자를 구성할 수 있다. 3번째 인자로 구조체를 넣어야 하는데, 만약 일반적인 타입이 아니라 구조체 혹은 class에 대한 priority queue를 구성해야 한다면, 혹은 custom 연산자를 사용해야 하는 경우엔, 비교 연산자를 구현한 구조체를 넣어주면 된다. 마지막에 푼 가운데를 말해요 문제는 정말 재밌는 문제.. 2020. 7. 6. [BOJ] 2094 수학은 너무 쉬워 전혀 쉽지 않은 문제였다. 각 값을 소인수분해 한 결과를 vector에 저장하고, 해당 소인수분해 결과를 종합해서 입력된 값들이 가질 수 있는 최대공약수를 구하고, 각각의 값들이 해당 최대공약수를 만족하기 위해 필요한 값의 갯수를 찾아서 합치면 된다. 어찌보면 그냥 수학 문제인데, 생각보다 많이 어려웠다. #include #include #include #include #include using namespace std; int numbers[101], N, sieve[1001]; vector datas[101]; map sum; pair dummy; void print_vector(){ for(int i = 0 ; i < N; i++){ vector target = datas[i]; printf("%d.. 2020. 4. 24. 이전 1 2 3 4 5 6 다음
