BOJ3 [단계별로 풀어보기] - 유니온 파인드 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 다음
