문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다. 창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올..
*내용에 있는 그래프는 방향 그래프(Directed Graph)입니다. DFS (Depth First Search) 현재 정점과 인접한 간선들을 검사하고, 방문하지 않은 정점으로 향하는 간선이 존재하면 그 간선을 따라서 이동한다. 더이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 위의 그래프가 있고 출발 지점이 0이라고 했을 때, DFS 과정은 아래와 같다. 정점 0 1 2 3 4 5 방문여부 X X X X X X 먼저 0에 방문하고, 0과 연결되어있는 정점을 모두 찾는다. 정점 0 1 2 3 4 5 방문여부 O X X X X X 0과 연결되어있는 정점은 1, 2, 3 이다. 1을 방문한다. 정점 0 1 2 3 4 5 방문여부 O O X X X X 1과 연결되어 있..
그래프의 표현에는 여러가지 방법이 있다. 위와 같은 그래프가 있을 때, 그래프를 표현하는 방법은 크게 두 가지 방법이 있다. 인접 행렬 0 1 2 3 4 0 0 1 0 0 1 1 0 0 0 0 0 2 1 0 0 1 0 3 0 0 1 0 1 4 1 0 0 0 0 인접 리스트 두 가지 표현 방식은 완전히 정반대의 특성을 가지기 때문에, 구현하려고 하는 문제의 알고리즘 종류나 그래프의 종류에 따라 적절히 선택해 사용해야 한다. 인접 행렬 정점의 번호 u, v가 주어졌을 때 두 정점을 잇는 간선이 있는지 한 번의 배열 접근만으로 확인할 수 있다. |V| x |V| 크기의 2차원 배열을 사용하기 때문에 실제 간선의 개수와 관계 없이 항상 O(|V^2|) 크기의 공간을 사용한다는 문제점이 있다. 인접 리스트 간선 ..
신찬수 교수님의 알고리즘 동적계획법 - zigzag 문제 영상을 정리했습니다. 수열 [1,7,4,9,2,5] 가 있을 때, 이를 지그재그 수열이라고 한다. 크기가 큰 것과 작은 것이 번갈아 나오는 수열을 지그재그 수열이라고 한다. 수열 [1,5,3,2,7] 은 3 다음의 원소가 3보다 작은 2 이기 때문에 지그재그 수열이 아니다. 수열이 주어졌을 때, n개를 뽑아서 지그재그 수열을 만든다. 예를 들어, [3,2,0,7,1,4,5,8,3]에선 [2,7,1,4,3]을 뽑아서 길이가 5인 지그재그 수열을 만들 수 있다. 만들 수 있는 지그재그 수열 중, 가장 길이가 긴 지그재그 수열을 구하는 것이 문제이다. 수열 [3,-1,2, 5, 7, 4, 5, 9, 8]에서, 5 (인덱스 6) 로 끝나는 지그재그 수열 ..
신찬수 교수님의 알고리즘 동적계획법 - LCS 문제 영상을 정리했습니다. 동적계획법의 순서 다시 정리 ! 1. 해를 분석 후 부문제로 분할 2. 부문제의 해로 큰 문제의 해를 표현(점화식) 3. 적당한 순서로 DP table을 채우기 4. DP table에서 원문제의 해를 계산하고 알고리즘의 정당성 증명 LCS(Longest Common Subsequence) 문제 주어진 수열에서 일부 원소(문자)를 지웠을 때 남은 수열(문자열)을 부분 수열이라고 한다. 주의할 것은 원래 수열에서 연속하지 않아도 된다는 것이다. 영어 대문자로 구성된 X, Y 문자열이 주어진다. X = ABCDDAB Y = BDCABA 이때 ABCDDAB에서 부분 수열이라고 하면 ABCDDAB의 CDD와 같이 연속으로 이어진 것만 가능하..
신찬수 교수님의 알고리즘 동적계획법 -예제 문제 - 최대구간합 1 영상을 정리했습니다. 최대구간합 문제 : 4가지 풀이법 n개의 정수 리스트가 주어졌을 때, 연속되는 숫자의 합이 최대가 되는 구간을 구하는 문제 A = [1, -1, 3, -4, 5, -4, 6, -2] 첫 번째 방법 : 브루트 포스 문제의 정답은 A[i] + ... + A[j]가 된다. (i = r: return A[l] m = (l+r)//2 L = max_interval(A, l, m) R = max_interval(A, m+1, r) # M 계산 # for loop를 통해서 구한다.O(N)의 시간이 걸린다. # M 계산 부분 (코드 생략) return max(L, M, R) L과 R을 구하는 과정은 각각 T(A의 원소수/2), M을..
