알고리즘 문제풀이

1245번 - 농장관리 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 256 99 78 46.988% 문제 농부 민식이가 관리하는 농장은 N*M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 guard를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다. 산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다. 문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다. 입력 첫째 줄에 정수 N(1>..

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번 아이의 뒤로 옮겨보자. 그러면 다..

3190번 - 뱀 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 28475 10709 7087 36.024% 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어..

18119번 - 단어 암기 문제 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주어진다. 1 x : 알파벳 x를 잊는다. 2 x : 알파벳 x를 기억해 낸다. 처음에 모든 알파벳을 기억하는 상태고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다. 각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하여라. 입력 첫 번째 줄에는 정수 N \(1 ≤ _N_ ≤ $10^{4}$)과 M (1 ≤ M ≤ 5×$10^{4}$)이 주어진다. 다음 N개의 줄에는 문자열이 하나씩 주어진다. 문자열의 길이는 $10^{3}$을 넘지 않는다. 다음 M개의 줄에는 정수 o와 문자 x가 ..