개발 일지

문제 2565번: 전깃줄 (acmicpc.net) 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 전깃줄이 어떤 상황에 교차되는지 따져보면 금방 LIS 문제라는 것을 알 수 있다. 따라서 전선을 나타내는 리스트를 만들어 가장 긴 증가하는 부분수열을 찾아주면 된다. N = int(input()) graph = [0]*501 for _ in range(N): a,b = map(int,input().split()) graph[a] = b dp = [1]*501 for i in range(1,501): for j in..

문제 11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net) 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 LIS를 각각 0번 왼쪽 -> 오른쪽으로, 오른쪽->왼쪽으로 한번씩 하면 된다. 일반적인 LIS와 마찬가지로 이진탐색을 쓸 수 있고, 두 번 해주면 되겠다. N = int(input()) A = [0] + list(map(int,input().split())) left = [1]*1001 right = [1]*1001 for i in range(1,N+1): for j in range(1,i): if A[..

문제 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 18353번 - 병사 배치하기 (tistory.com) 18353번 - 병사 배치하기 문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다 forteqook.tistory.co..