전체 글166 백준_1717_집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 해결 방법 > Disjoint set을 이용한다. > input() 대신에 sys.stdin.readline()을 이용한다.(시간의 .. 2020. 2. 10. 백준_15956_숏코딩(해결 못함2)... 기존 포스트 https://seungbok3240.tistory.com/51?category=819423 백준_15956_숏코딩(해결 못함) https://www.acmicpc.net/problem/15956 15956번: 숏코딩 코드 페스티벌 온라인 예선에 참가하고 있던 라이언은 이제 남은 시간이 00:00:00밖에 없다는 것을 깨닫게 되었다. 라이언은 이미 머릿속에서 풀이를 구상.. seungbok3240.tistory.com 문제점 > 코드가 길어지다보니 나 자신조차 머릿속에서 생각이 꼬여버렸다. > 다시 처음부터 풀었다. > 코드를 다 짜고 보니 예제는 알맞게 출력되지만 질문검색 사이트에서 찾은 반례가 통과되지 않는 문제점을 알았다. https://www.acmicpc.net/board/view/.. 2020. 2. 9. 2020 동계 학습 동아리_3회차_2020-02-07(금) Union-find(Disjoint-set) - Disjoint set : 서로 중복되지 않는 집합(서로소 집합) - Union-find : disjoint set을 표현하기 위해 사용하는 알고리즘 Union-find의 메소드 - find(x) : x가 속한 집합의 대표값을 반환한다. - union(x,y) : x가 속한 집합과 y가 속한 집합을 합친다. 구현 방법 1. 배열 - find(x) : O(1) - union(x,y) : O(N) 2. 트리 - find(x) : O(트리의 높이) - union(x,y) : < O(N) 관련 알고리즘 문제 https://www.acmicpc.net/problem/tag/Disjoint-set Disjoint-set - 1 페이지 www.acmicpc.net 초심.. 2020. 2. 7. 2020 동계 학습 동아리_2회차_2020-02-04(화) 목표 > 카카오 코드 페스티벌 2018 예선 B번 문제 풀기 https://www.acmicpc.net/problem/15954 15954번: 인형들 첫 번째부터 세 번째까지의 인형을 선택하면 표준편차는 2/3의 양의 제곱근이 되고, 이 때 표준편차가 최소가 된다. 두 번째부터 네 번째까지의 인형을 선택하는 경우와, 세 번째부터 다섯 번째까지의 인형을 선택하는 경우에도 값은 같다. www.acmicpc.net 결과 해결 방법 > 항상 그렇듯이 카카오 문제는 이해를 하는 것이 가장 어려운 것 같다. > 입력으로 들어오는 N은 인형들의 수, K는 골라야 하는 인형들의 수, 두 번째 줄에 들어오는 배열은 인형들을 선호하는 사람들의 수이다. > 쉽게 말해서 N개의 인형들 중에 K개 이상의 연속된 인형을 뽑아서(.. 2020. 2. 4. 이전 1 ··· 26 27 28 29 30 31 32 ··· 42 다음
