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

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

위상 정렬 (9)
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)2056 작업

문제: icpc.me/2056 a번 작업을 실행할 때 선행되야 되는 작업 b의 셋이 주어질 때 모든 작업을 완료하는데 걸리는 시간을 출력하는 문제이다. 문제에서 선행관계는 항상 번호가 증가하는 순서로 이루어진다고 하였으므로 사이클이 존재하지 않는 DAG임을 알 수 있다. 따라서 우리는 위상정렬을 해준 뒤 위상정렬의 순서대로 일을 처리해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include using namespace std;int n, in[10002], c[10002], x, y, r;vector vt;int main() { scanf("%d", &n); vt.re..

알고리즘 관련/BOJ 2017. 4. 6. 02:31
BOJ)3665 최종 순위

문제:icpc.me/3665 작년의 등수가 주어지고 올해 등수가 역전 된 두 팀의 목록이 주어질 때 올해 순위를 발표하는 문제이다. 우선 작년의 등수를 기반으로 n^2의 방법으로 간선을 연결해주고 올해에 뒤 바뀐 순위를 기반으로 간선의 방향을 바꿔준다. 이후 위상정렬을 해주면 되는데 이 때 큐에 동시에 2개가 들어간다면 ?를 출력하고 n번을 돌리기전에 큐가 비어버린다면 사이클이 생긴것이므로 IMPOSSIBLE을 출력 해 주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include #include #..

알고리즘 관련/BOJ 2017. 1. 22. 18:57
BOJ)2637 장난감조립

문제:icpc.me/2637 장난감 완제품 N을 만드는데 필요한 기본 부품의 종류와 수를 출력하는 문제이다. 여기 기본 부품은 indegree의 수가 0인 정점들이 되고 위상정렬 순서대로 부품의 개수를 중첩 시켜 나가면 답을 구할 수 있다. a[x][y]가 의미하는건 x번 부품(제품)을 만드는데 필요한 기본 부품 y의 개수이다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include using namespace std;int n, m, a[101][101], in[101], x, y, z;vector vt;int main() { scanf("%d%d", &n, &m); vt..

알고리즘 관련/BOJ 2017. 1. 22. 18:26
BOJ)9470 Strahler 순서

문제: icpc.me/9470 indegree가 0인 노드들의 순서가 1인데 어떤 노드의 indegree와 연결된 노드 중 순서가 가장 큰 값을 i라고할 때 i가 1개 들어오면 해당 노드의 순서는 i 2개 이상 들어온다면 해당 노드의 순서는 i+1이 된다. 우리는 indegree의 정보를 이용하여 위상정렬을 실행하는데 이때 들어오는 indegree의 최댓값과 개수만 count해주어 값을 갱신해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include #include using namespace std;int k, m, p,..

알고리즘 관련/BOJ 2017. 1. 22. 16:33
Topological Sort(위상 정렬)

DAG에서 방향성을 거스르지 않게 정점들을 나열하는 알고리즘을 Topological sort(위상 정렬)이라 합니다. DAG란 Directed Acyclic Graph의 줄임말로 직역하자면 사이클이없는 방향(유향) 그래프 정도가 될 것입니다. DAG는 유향 그래프에서 정의되며 DAG가 되려면 Cycle이 없어야 합니다. 우리는 유향 그래프에서 한 정점에서 DFS를 실행 할 경우 DFS의 방문순서에 따라서 스패닝 트리를 얻을 수 있습니다. 우리는 이러한 트리를 DFS 스패닝 트리(DFS Spanning Tree)라고 부르며 DFS 스패닝 트리에서 간선의 특징에 따라 간선 분류를 할 수 있습니다. 1. 트리 간선-> 스패닝 트리에 포함된 간선 2. 순방향 간선-> 스패닝 트리에는 포함되지 않았지만 선조에서 ..

알고리즘 관련/알고리즘&이론 2017. 1. 20. 06:18
BOJ)1766 문제집

문제: icpc.me/1766 문제집을 푸는 순서가 주어지는데 이때 가능하면 쉬운 문제부터 풀어야 할 경우 문제를 푸는 순서를 출력하는 문제이다. 우리는 문제집을 푸는 순서가 주어질 때 topological sort를 통하여 순서를 출력할 수 있다. 하지만 가능하면 쉬운 문제를 풀어야 하니 topology가 여러개일 경우 작은 순서를 먼저 출력해줘야 한다. 이는 min heap을 통하여 해결 가능하다. 123456789101112131415161718192021222324252627282930313233#include #include #include #include #define MAX_N 32000using namespace std;int n, m, a, b, in[MAX_N + 1];vector vt..

알고리즘 관련/BOJ 2017. 1. 20. 06:13
BOJ)2623 음악프로그램

문제: icpc.me/2623 음악프로그램의 출연 순서의 리스트가 주어졌을 때 모든 리스트를 만족시키도록 출연 순서를 출력하는 문제이다. 만약 모든 리스트를 만족할 수 없는 경우 0을 출력하면 된다. 우리는 출연 순서가 A->B->C 라면 A->B / B->C의 방향으로 간선을 연결해 준 뒤 topology를 구해줌으로서 리스트를 구할 수 있다. 이때 모든 리스트를 만족할 수 없는 경우는 사이클이 생기는 경우로서 그래프의 사이클 여부를 체크해줌으로서 확인 가능하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #include #include #define MA..

알고리즘 관련/BOJ 2017. 1. 20. 04:45
BOJ)2252 줄 세우기

문제: icpc.me/2252 N명이 학생이 주어지고 두 학생의 키를 비교한 M개의 정보가 주어질 때 줄을 세운 결과를 출력하는 문제이다. 우리는 두 학생의 우선관계를 방향 그래프를 이용하여 설정해준 뒤 topology를 구해주면 된다. 즉 DFS를 돌리면서 먼저 끝나는 순서대로 스택에 저장해준 뒤 하나씩 뽑으면서 출력해주면 답을 얻을 수 있다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include #include #define MAX_N 32000using namespace std;vector vt;stack st;int n, m, x, y, visited[MAX_N + 1];void dfs(int ..

알고리즘 관련/BOJ 2017. 1. 14. 03:20
이전 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

티스토리툴바