Computer Science32 Uva 11456 - Trainsorting Problem Link https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=651&problem=2451&mosmsg=Submission+received+with+ID+20661170 Description of Problem 자동차의 행렬이 주어진다. 행렬에는 자동차의 무게가 저장된어 있다. 이때 자동차를 연결한다. 자동차를 연결하는 제약조건은 앞쪽 즉, 왼쪽의 자동차가 뒷쪽 즉, 오른쪽의 자동차보다 무거워야 된다. 이때 주어진 조건을 만족하는 가장 긴 자동차 행렬의 길이를 구하는 문제다. Algorithm to Solve the Problem 답은 제약조건을 만족하는 가장 긴 행렬의.. 2018. 1. 25. 절단점 및 다리(구하기) 절단점 및 다리(Articulation Point & Bridge) 절단점은 그래프G의 정점 중에서 이를 제거했을때(이때 해당 정점에 인접한 간선들도 같이 제거한다) G가 연결되지 않도록 만드는 정점이다. 절단점이 한개도 없는 그래프를 이중 결합 되었다고 한다. 다리는 그래프 G의 간선 중에서 이를 제거했을때 G가 연결 되지 않게 만드는 간선이다. 이둘을 찾는 문제는 보통 무방향 그래프에 대해서 정의된다. Algorithms to get Articulation Point and Bridge 우선 가장 직관적이지만 약간 비효율적인 알고리즘을 소개 하겠다. 첫째. DFS를 수행하여 그래프 G가 몇개의 컴포넌트로 구성되었는지를 파악한다.둘째. 모든 정점을 한번씩 순회하며 해당정점과 정점에 인접한 간선을 제거한.. 2018. 1. 19. Fenwick Tree(Binary Indexed Tree, BIT) FenwickTree 펜윅트리는 동적인 누적 빈도수 테이블을 구현할 때 유용한 자료구조이다. 여기서 동적인 누적 빈도수 테이블이란 다음의 예를 보면 쉽게 이해할 수 있다. 학생11명이 시험을 본다. 당연히 11개의 시험 결과과 나온다. 시험점수는 0 ~ 10점 사이이다. 학생들은 0점부터 10점까지의 점수를 받게되며 각 점수당 0 ~ 11명 사이의 학생이 해당점 수를 받을 수 있다. 즉, 0점을 받은학생, 1점을 받은학생, ... 10점을 받은학생을 다더하면 11명이된다. 그렇다면 0점을 받은 학생의 수, 1점을 받은학생의 수, 2점 ..., 10점을 받은 학생의 수를 알때 이에대한 누적합을 구하려고 한다. 여기서 누적합이란. "누적합(0)"은 0점을 받은 학생의 수이다. "누적합(1)"은 0점을 받은 .. 2018. 1. 19. Uva 11902 - Domanitor Problem link https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=229&problem=3053&mosmsg=Submission+received+with+ID+20625091 Description Problem 위 문제는 시작점이 무조건 0이고, '지배하다'의 뜻만 이해하면 된다. 노드 x가 노드 y를 지배한다면 다음을 만족해야된다. 0 에서 x를 거치지 않고서는 y로 갈 수 없다. 즉, y로가는 모든 경로는 x를 거쳐야 된다. Algorithm to Solve Problem 해당 문제를 해결하기 위하여 DFS(Depth first Search)알고리즘을 이용한다.해당 문제에.. 2018. 1. 18. 이전 1 2 3 4 5 6 ··· 8 다음