http://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net # 조건 N줄에 0이상 9이하의 숫자가 세 개씩 적혀 있다. 첫 줄에서 시작하여 마지막 줄에서 끝나게 되는 놀이이다. 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 아래와 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어있는 수로만 이동할 수 있다. 별표는 현재 위치, 파란 동그라미가 내려갈 수 있는 위치 ..

http://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net # 조건 정수 A를 B로 바꾸려고하는데 가능한 연산은 아래 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. # 접근 방법 만들 수 없는 경우에는 -1을 출력한다. B+1만큼의 빈 리스트를 만들어서 BFS 탐색해준다. A에서 2를 곱한 수와 1을 오른쪽에 추가한 수에 현재 카운트를 기록해주며 B를 만난 경우 종료 해준다. 메모리 초과 모든 숫자에 대해 리스트에 기록해주니 입력이 커서 메모리초과 import sys sys.stdin = open('input...

http://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net # 조건 루트 없는 트리가 주어진다. 이 때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램 작성 입력 첫 줄에 노드의 개수 N (2 방문한 것 dfs 풀이 import sys sys.stdin = open('input.txt') input = sys.stdin.readline def dfs(start): parent=[0] * (N+1) parent[start] = 1 stack = [start] while stack: node = st..

플로이드-워셜 (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)이 주어진다. 다음 두 줄에는 ..