본문 바로가기 메뉴 바로가기

ACM-ICPC 상 탈 사람

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

ACM-ICPC 상 탈 사람

검색하기 폼
  • 분류 전체보기 (360)
    • 서버 관련 (9)
      • JS (5)
      • AmazonWebService (1)
      • Backend 지식 (3)
    • 일상 (13)
      • Daliy (1)
      • 잡담 (10)
      • 개인 (2)
    • 알고리즘 관련 (337)
      • BOJ (303)
      • UVaOJ (8)
      • SPOJ (1)
      • 알고리즘&이론 (25)
  • 방명록

union find (3)
advanced disjoint set

오늘은 disjoint set에 대해서 글을 적어보겠습니다. 직역하면 상호배타적 집합이며, union-find 라는 자료구조로 표현됩니다. [disjoint set, DSU(disjoint union),union find] 는 전부 union find 자료구조를 칭하는 말입니다. union find 는 union연산과 find연산을 매우 빠르게 해주는 자료구조로서, 상호배타 집합에서는 어떠한 집합에서도 공통 된 원소가 존재하지 않으며, 동시에 모든 집합의 합집합은 전체집합이 됩니다. 이해를 돕기 위하여 특수한 상황을 가정해보겠습니다. a라는 나라와 b라는 나라가 동맹이고, b라는 나라와 c라는 나라가 동맹을 맺게된다면 a와 c나라도 자동으로 동맹이 되는 경우를 생각해봅시다. 해당 경우로 각각의 나라의 동..

알고리즘 관련/알고리즘&이론 2018. 6. 24. 20:04
BOJ)10216 Count Circle Groups

문제: icpc.me/10216 N개의 진영이 주어 질 때 각 진영이 통신영역이 닿거나 겹치는 부분이 있으면 서로 통신이 가능하다. 그리고 직접적으로 통신이 불가능 하더라도 중간에 몇개의 통신을 거쳐서 통신이 가능하다면 i와 j는 통신이 가능하다고 본다. 통신이 서로 가능한 진영들을 그룹으로 묶을 때 그룹의 수를 출력하는 문제이다. 우리는 a와b가 통신이 가능하고 b와c가 통신이 가능하면 a와c가 통신이 가능한 그룹이 된다는 사실을 가지고 disjoint set을 통하여 문제를 해결할 수 있다. N이 3000밖에 되지 않으므로 N^2의 방법으로 각 진영들을 비교하여 같은 그룹이 아닌 그룹들중에서 통신영역이 겹치는 두 그룹을 union 시켜주면서 시켜줄때마다 그룹의 수를 하나씩 차감시키는 방법으로 답을 구..

알고리즘 관련/BOJ 2017. 1. 17. 17:34
BOJ)4195 친구 네트워크

문제 : icpc.me/4195 친구 관계가 생길 때 마다 가입한 두사람의 친구 네트워크에 몇명이 있는지 구하는 문제이다. 문제의 답은 union_find를 통하여 쉽게 구해줄 수 있지만 string으로 들어오는 입력 때문에 좌표 압축이나 map을 이용한 테크닉이 필요하다. -좌표압축 이용123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #include #include #include #include using namespace std;int par[200010];int t, n;int num[200010];vect..

알고리즘 관련/BOJ 2017. 1. 10. 16:24
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Node.js로 DynamoDB 시작⋯
  • Node.js로 DynamoDB 시작⋯
  • Express와 Apollo server⋯
  • GraphQL 스키마 작성하기⋯
최근에 달린 댓글
  • 도움이 많이 되었습니다 굳굳⋯
  • 간선의 방향을 다 거꾸로 받⋯
  • 넵 요즘은 거의 node js 만⋯
  • 문제 설명 감샇바니다. :) 'B⋯
Total
315,369
Today
36
Yesterday
199
링크
  • 민호형
  • 제주시민
  • 꼴뚜기
  • 김흿
  • 태양쓰
  • 정률이
  • 정이 형
  • stack님
  • 세지니
  • 매브레이커
  • 박트리님
  • 플즈런님
  • 맹킹
  • 송이 블로그
TAG
  • 세그먼트 트리
  • 이분 탐색
  • 다이나믹 프로그래밍
  • 힙
  • 그리디 알고리즘
  • LCP array
  • 플로이드 워셜
  • MST
  • lazy propagation
  • KMP
  • SCC
  • Suffix Array
  • 분할 정복
  • 라인 스위핑
  • disjoint-set
  • 트리
  • 이분 매칭
  • 디닉
  • 네트워크 플로우
  • 다익스트라
  • MCMF
  • partial sum
  • brute force
  • 위상 정렬
  • 에라토스테네스의 체
  • lca
  • BFS
  • 좌표 압축
  • dfs
  • 수학
more
«   2021/03   »
일 월 화 수 목 금 토
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
글 보관함
  • 2020/05 (2)
  • 2020/04 (6)
  • 2020/03 (1)
  • 2018/07 (4)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바