플로이드-워셜 (Floyd-warshall) 알고리즘은 앞서 알아본 다익스트라, 벨만-포드와 같이 그래프에서 최단 거리를 구하는 알고리즘이다. 모든 노드 간에 최단 경로를 탐색 음수 가중치 에지가 있어도 수행할 수 있음 동적 계획법(dp)의 원리를 이용해 알고리즘에 접근한다. 노드 수 -> V일 때 O(V^3)의 시간 복잡도를 가진다. 핵심 이론 A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로이다. 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어진다. 위와 같은 원리로 아래와 같은 점화식을 도출할 수 있다. D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 구현..

http://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net # 조건 n(2 c: table[a-1][b-1] = c for i in range(n): table[i][i] = 0 dist = Floyd_Warshall() for i in range(n): for j in range(n): if dist[i][j] == INF: print(0, end=' ') else: print(dist[i][j], end=' ') print() 플로이드 워셜 알고리즘 참..

http://www.acmicpc.net/problem/11719 11719번: 그대로 출력하기 2 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄이 주어질 수도 있고, 각 줄의 앞 뒤에 공백이 www.acmicpc.net # 조건 n(1

http://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net # 조건 월드나라에는 N개의 지점이 존재하고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀 도로는 무방향, 웜홀은 방향이 존재 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 도착을 하게 되면 시작 하였을 때보다 시간이 뒤로 가게 된다. 한 지점에서 출발하여 시간여행을 하기 시작하여서 다시 출발을 하였던 취로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있..

http://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 대표적인 백트래킹 문제 다른 알고리즘 사이트에서 통과 코드가 시간초과가 발생하여 pypy로만 통과되었다. 따라서 다른 사람의 코드 참고하여 공부가 필요할듯!! # 조건 N x N 크기의 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다 N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. # 접근 방법 전형적인 백트래킹 문제이다. 모든 경우의 수를 살펴보는 브루트포스를 기반으로 이후의 ..

http://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net # 조건 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매 스티커는 아래 그림과 같이 2행 n열로 배치 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져 사용 불가 점수의 합이 최대가 되도록 스티커를 붙여라 # 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 ..

http://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net # 조건 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제 예 ACAYKP와 CAPCAK의 LCS는 ACAK # 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져있으며, 최대 1000글자로 이루어져 있다. ..

LCS (Longest Common Subsequence) 란? 2개 이상의 문자열에서 공통으로 나타나는 부분 문자열 중 가장 긴 문자열을 의미 대표적으로 DNA의 공통 염기서열을 찾아 데이터를 압축하거나 무선 서명을 통해 휴대폰에서 사용자를 인증할 때 사용 풀이 방법 분할정복이 아닌 DP를 이용하여 풀이해준다. 1. Top-down 방법 (재귀적 풀이) 문자열 X, Y 가 X = [x1, x2, x3, .... , xm], Y = [y1, y2, y3, ... , yn] 일 때, 아래와 같은 과정을 반복한다. LCS(X, Y): #수열 X와 Y의 최장 공통 부분 수열(LCS)의 길이 m, n = len(X), len(Y) if m == 0 or n == 0: return 0 else: if X[-1] ..

http://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net # 조건 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리 오더를 구하여라 # 접근 방법 중위 순회와 후위 순회가 주어진다. 중위의 경우 -> LVR 후위의 경우 -> LRV 왼쪽 자식 노드부터 시작한다. 후위 순회의 가장 마지막 수 -> 루트 노드 루트 노드를 중위 순회에서 살펴보면 left tree와 right tree를..