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

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)
  • 방명록

SCC (7)
UVaOJ)12645 Water Supply

문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4393 오염된 물을 정화하기 위해서 단방향 그래프에서 0번 정점에서 나오는 정화제를 x개의 간선을 추가하여 모든 정점에 뿌려야할 때 연결해야하는 간선 x개의 최솟값을 구하는 문제이다. 이 문제는 정점들을 scc로 묶어준다음 위상정렬을 통하여 해결가능하다. 즉 0번 정점을 포함한 scc를 제외한 indegree가 0인 scc의 개수를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545..

알고리즘 관련/UVaOJ 2017. 6. 19. 16:51
BOJ)3682 동치 증명

문제: icpc.me/3682 그래프에서 동치임을 증명하기 위해 사용하는 함축의 수의 최솟값을 출력하는 문제이다. 우리는 동치임을 증명하기 위해서 그래프의 사이클을 생성해주면 된다. 우리는 그래프의 SCC를 분류한 뒤 다시 SCC들을 정점으로 가지는 그래프로 압축하여 각 SCC의 indegree와 outdegree의 수를 구해준 뒤 indegree가 0인 정점과 outdegree가 0인 정점중 최댓값을 출력해주면 된다. 그래프의 사이클을 만들어야 하기 때문에 사이클이 존재하려면 indegree와 outdegree가 적어도 1씩 존재해야 하기 때문이다. 단 그래프가 하나의 SCC를 이룰 경우는 예외처리를 해주어야만 한다. 12345678910111213141516171819202122232425262728..

알고리즘 관련/BOJ 2017. 1. 31. 18:07
BOJ)10265 MT

문제: icpc.me/10265 K이하의 사람이 버스에 탈 수 있을 때 버스에 탈 수 있는 최대 인원을 출력하는 문제이다. 문제에는 조건이 있는데 A라는 사람은 B라는 사람이 버스에 안타면 A도 반드시 안타는 정보 N개가 주어진다. 우리는 이러한 조건을 B->A라는 방향 그래프로 만들어 준 SCC끼리 분류를 한다음 다음 위상 정렬을 이용하여 X라는 정점이 방문 가능한 모든점 Y는 반드시 X의 인원을 포함한다고 정의 가능하다. 이 때 X의 인원은 SCC의 그룹 크기와 동치가 된다. 따라서 연결 그래프마다 최소 인원~최대 인원 셋을 저장한 뒤 Knapsack문제를 해결하듯이 다이나믹 프로그래밍을 이용해주어 답을 계산해주면 된다. 이때 연결 그래프의 수는 SCC 그래프의 indegree가 0인 SCC의 개수이..

알고리즘 관련/BOJ 2017. 1. 24. 21:28
BOJ)3977 축구 전술

문제: icpc.me/3977 A->B로 이동해야하는 전술들이 주어질 때 시작 지점이 될 수 있는 위치를 찾는 문제이다. 이 때 적절한 시작지점이 없으면 Confused를 출력하면 된다. 여기서 SCC를 이루는 그룹이면 어떤 곳에서 시작하던 topology에 의해 나머지 지점들을 전부 탐색 가능하니 정점들을 SCC로 묶은 뒤 indegree가 0인 지점이 하나일 때는 해당 SCC에 속하는 모든 점들이 시작지점이 될 수 있고, 만약 indegree가 0인 지점이 여러곳일 경우에는 어떤 지점에서 시작해도 모든 점을 방문 불가능하기 때문에 Confused를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424..

알고리즘 관련/BOJ 2017. 1. 24. 18:25
BOJ)4196 도미노

문제:icpc.me/4196 X번 블록이 넘어지면 Y번 블록이 넘어지는 정보가 여러개 주어질 때 도미노를 직접 넘어뜨려야하는 최소 블록 개수를 출력하는 문제이다. 도미노를 직접 넘어뜨려야 한다는 건 결국 다른 도미노에 의해서 넘어지지 않는다는걸 의미하는데 이는 곧 indegree가 0인 정점의 개수다. 또 하나 고려해줘야 하는 경우가 있는데 cycle을 이룰 경우 indegree가 0이지 않지만 누가 먼저 넘어지지 않는 이상 영원히 넘어지지 않는다. 따라서 우리는 방향 그래프에서 SCC를 구해준 후 SCC로 이루어진 그래프에서 indegree가 0인 SCC의 개수를 세어주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839..

알고리즘 관련/BOJ 2017. 1. 24. 17:44
SCC(Strongly Connected Component)

방향 그래프에서 어떤 그룹 X에 있는 임의의 두 정점 A,B에 대해서 항상 A->B로 가는 경로가 존재한다면 그 그룹을 SCC(Strongly Connected Component)라 칭합니다. 더 정확하게 정의하자면 SCC가 되는 그룹은 항상 최대로 정의되기 때문에 다음과 같은 조건을 만족해야 합니다. 1. 같은 SCC 내의 임의의 두 정점 A,B사이의 경로가 항상 존재한다.2. 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이의 경로 A->B로 가는 경로와 B->A로 가는 경로는 동시에 존재할 수 없다. (SCC 끼리는 사이클이 존재하지 않는다.) SCC를 직역하면 "강한 연결 요소" 라는 뜻이됩니다. 즉 SCC는 집합 내에서 정점들이 서로 왕복 가능한 최대 크기의 집합입니다. 다음과 같은 그래프에..

알고리즘 관련/알고리즘&이론 2017. 1. 21. 20:31
BOJ)2150 Strongly Connected Component

문제: icpc.me/2150 SCC를 구하는 기본 문제이다. 출력을 SCC가 속한 가장 작은 정점의 정점 번호 순으로 출력해야 하므로 정렬이 필요하다. 코사라주 알고리즘을 통하여 구현하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include #include #define MAX_V 10000using namespace std;int v, e, visited[MAX_V + 1], x, y, r;vector scc;vector vt;vector rvt;stack st;bo..

알고리즘 관련/BOJ 2017. 1. 21. 18:34
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Node.js로 DynamoDB 시작⋯
  • Node.js로 DynamoDB 시작⋯
  • Express와 Apollo server⋯
  • GraphQL 스키마 작성하기⋯
최근에 달린 댓글
  • 도움이 많이 되었습니다 굳굳⋯
  • 간선의 방향을 다 거꾸로 받⋯
  • 넵 요즘은 거의 node js 만⋯
  • 문제 설명 감샇바니다. :) 'B⋯
Total
315,368
Today
35
Yesterday
199
링크
  • 민호형
  • 제주시민
  • 꼴뚜기
  • 김흿
  • 태양쓰
  • 정률이
  • 정이 형
  • stack님
  • 세지니
  • 매브레이커
  • 박트리님
  • 플즈런님
  • 맹킹
  • 송이 블로그
TAG
  • MCMF
  • 트리
  • 이분 매칭
  • MST
  • dfs
  • 그리디 알고리즘
  • 수학
  • disjoint-set
  • BFS
  • 다이나믹 프로그래밍
  • KMP
  • 힙
  • 디닉
  • 좌표 압축
  • SCC
  • 이분 탐색
  • LCP array
  • 네트워크 플로우
  • 위상 정렬
  • 세그먼트 트리
  • lazy propagation
  • 다익스트라
  • partial sum
  • lca
  • 분할 정복
  • 플로이드 워셜
  • 라인 스위핑
  • 에라토스테네스의 체
  • Suffix Array
  • brute force
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

티스토리툴바