[백준][Python][1309][DP] 동물원
문제 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net DP 문제다. 예전에 풀어서 그런지 기억이 안났다. 이 문제는 n번째를 n-1, n-2 번째로 각각 나눠서 확인해야 한다. n-1 번째에 [0,X][X,0] 일때 n 번째에서는 각각 [X,0][0,X] 할 수 있는 경우의 수가 있다. 그리고 n-1 번째에 아무것도 놓지 않는 방법의 수, [0,0] 의 수가 있다. 이 때는 어디든 놓을수 있다. 따라서, dp[n] = dp[n-1]* 2 + dp[n-2]의 경우의 수가 있다. import sys n = int(sys.stdin.readline()) dp = [1,3] for..
더보기
[백준][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)가 되어 시간 초과가..
더보기
[프로그래머스 Programmers][Python] 자물쇠와 열쇠
문제 : https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 깡으로 구현해야한다. 우선 맵을 2*len(key) + len(lock) 으로 확장한 뒤에 arr[M][M] 에서부터 lock을 복사해 놓는다. 이제부터는 순서가 중요하다. 아까의 arr 맵을 복사해 tmparr 에 넣는다. key + lock 사이즈 동안 for문을 돌린다. key를 tmpkey에 복사해놓는다. tmpkey를 90도씩 4번 돌릴 수 있게 for문을 만든다. 각 tmpa..
더보기
