알고리즘 문제풀이

11054번 - 가장 긴 바이토닉 부분 수열 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 17643 9222 7349 52.530% 문제 수열 S가 어떤 수 ${S_k}$를 기준으로 ${S_1 S_{k+1}> ... S_{N-1}> S_N}$을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20,30, 25, 20}과 {10, 20, 30,40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의..

11055번 - 가장 큰 증가 부분 수열 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 21376 9707 7712 45.706% 문제 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100,2,50,60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai≤ 1,000) 출력 첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합..

백준 2631번 - 줄 세우기 문제 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다. 예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자. 3 7 5 2 6 1 4 아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다..