[백준][Python][14889][브루트포스] 스타트와 링크
문제 : https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 브루트 포스 문제다. 모든 팀 조합을 구하고, 그 조합들에서 차이가 가장 안나는 조합으로 최솟값을 구한다. 문제의 N이 작으므로 조합을 통해 다 구해보자. for c in combinations(orig,n//2) 은 0~n-1 까지의 모든 숫자를 반으로 나눈다. 그 다음 각각 나눠진 팀을 c, news 라 한다. 이는 Set 연산으로 구할 수 있다. 그 후 각각의 c에 대해 score연산을 통해 최솟값을 구..
더보기
[백준][Python][11053][DP]가장 긴 증가하는 부분 수열
문제 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net DP 문제 중에 유명한 문제다. Longest Increasing Subsequence LIS라는 문제다. 이 문제는 DP로 풀면 O(n^2) 가 나오고, binary search 등을 이용하면 O(nlogn)까지 줄일 수 있다고 한다. 물론 난 안줄인다. ㅎㅎ dp 배열을 만들고, 다음과 ..
더보기
[백준][Python][10816][이분탐색] 숫자 카드 2
문제 : https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,00 www.acmicpc.net 이분 탐색 문제다. list.index()는 O(N) 이므로, count를 사용할 경우 O(N^2)가 되어 시간 초과가..
더보기
