백준

외판원 순회 문제(TSP) 외판원 순회 문제(TSP)는 조합 최적화 문제 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다. 즉, 아직까지 다항 시간에 해결할 수 있는 해결책을 못찾았으며 해결하지 못한다는 것도 증명하지 못했다. 외판원 문제의 내용은 다음과 같다. 예를 들어, 어떤 외판원이 n개의 도시를 방문할 계획을 갖고 있다고 하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위해 외판원이 출발하는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 경로를 찾고자 할 때, 어떻게 찾을 수 있을까? 만약 20개의 도시가 있을 때 정답을 찾기 위해 다녀야 하는 총 경로 수는..

문제 특정 숫자의 제곱수 합을 구할 때 그 수들의 최소 개수를 구하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Q17626 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] dp = new int[n + 1]; dp[..

문제 풀이 내 풀이 import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) dp = [0] * n dp[0] = arr[0] for i in range(1, len(arr)): dp[i] = max(dp[i-1] + arr[i], arr[i]) print(max(dp)) 이 문제는 단순하게 생각하여 현재까지 합들보다 현재 값이 크면 시작점을 현재 인덱스로 바꾸면 해결되는 문제이다. 이 문제에선 다음을 고려하여 풀이를 진행하면 해결법이 생각날 것이다. 음수 값이 포함되어도 합이 최대 일 수 있다는 점 그렇지만 음수는 합에 영향을 준다는 점 (모두 0 이상인 수라면 전체 합이 최대이다) 한 번 다음 ..