Han's Tech LAB

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 오늘의 DP문제는 연속합이다. n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. O(n^2)의 복잡도를 갖는다. 코드는 아래와 같다. import sys num = int(input()) num_list = list(map(int, sys.stdin.readline().rst..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 오늘도 DP 문제를 가져와 보았다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 연산을 사용하는 횟수의 최솟값을 출력하는 것이다. 입력으로 주어는 값을 x에 넣는다. 재귀를 이용하여 구현해준다. 해당 코드는 하향식으로 제일 큰 값에서 작은 값으로 바뀌도록 구성되었다. x=int(input()) dp={1:0} def rec(n): if n in dp.keys(): return dp[n] if n%3==0 and n%2==0:..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 오늘은 DP 문제를 풀어보고자 한다. 배낭 문제(knapsack)을 풀어보려 고한다. 배낭에 넣을 수 있는 최대값이 나오고 한도 안에 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 최적화 문제이다. 짐을 쪼개지 않고 푸는 문제이므로 DP로 문제를 해결한다. 코드는 아래와 같다. import sys N, K = map(i..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net Floyd Warshall Algorithm 을 이용하여 구현하였다. import sys INF = sys.maxsize N, M = map(int, input().split()) s = [[INF] * N for i in range(N)] for i in range(M): num1, num2 = map(int, input().split()) s[n..

문제 경로 : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬에 대한 백준 문제이다. 위상정렬(Topological Sorting) 이란? 문제 상황 -> 비순환 유향 그래프(DAG : directed acyclic graph)가 주어질 때 방향성을 거스리지 않게 모든 정점들을 나열하는 것 예제 프로젝트 관리 선수 과목 요리하기 위상정렬 특징 # 그래프가 사이클을 가질 경우 DAG를 만족하지 ..

Network flow 문항을 찾다가 Max flow문제를 발견하였다. https://www.acmicpc.net/problem/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 시간 복잡도 : O(VE^2) 정점 중 Capacity가 주어진 파이프 그래프가 주어졌을 때, 정점 start_node에서 정점 end_node까지의 최대 flow를 출력하는 문제이다. Edmonds_Karp Algorithm을 적용하여 풀이하였다. 코드를 조금씩 살펴보도록 하자. import sys from c..

NetWork Flow Algorithm # 네트워크 전송 및 통신 분야에서 사용하는 Algorithm 아래 그림과 같이 간단하게 용량과 유량을 표시합니다. 그림에서 가장 손실 없이 유량을 전달할 때, 가장 적합한 유량은 몇 일까요? 만약 5를 유량으로 보내게 된다면, 5는 b에서 c를 갈 때, 3만큼만 갈 수 있으므로, b에서 2만큼의 손실이 발생하게 됩니다. 따라서, 위 그림에서 손실 없이 유량을 보내는 방법은 3을 보내는 것입니다. 그리하여 최대한 낭비되는 것 없이 유량을 보낼 수가 있습니다. 이를 Max Flow Problem(최대 유량 문제)라고 합니다. 이렇게 최대 유량 문제 란 네트워크 상에서 얼마나 많은 데이터를 흘려 보낼 수 있는지를 나타냅니다. 최대 유량 문제 는 각 간선에 정해진 용량..