백준/카테고리별9 [알고리즘 분류] - 세그멘트 트리 세그멘트 트리 문제를 연습하기 위해 다양한 문제를 찾아 시도해봤지만, 정말 어려운 것 같다.. 기본 세그멘트에서 조금이라도 응용을 뻗어나가면 방법을 모르겠는.. 구간 곱, 구간 합, 최소값 이런 것들은 단순히 init과 update의 함수를 조금씩 수정해주면 되는 부분이라 충분히 해결 가능하다. 플레 5 정도 문제는 가장 기초적인 세그먼트 트리를 이용해서 푸는 문제인데, 그 이후로부터는 Lazy Propagation 등의 추가적인 스킬과 응용 능력이 필요한 것으로 보인다. (어려움..) 2020. 9. 20. [알고리즘 분류] - 최소 스패닝 트리 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. 이전 1 2 3 다음
