알고리즘 문제풀이

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 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어..

삽입정렬 ( Insertion Sort ) 기본 IDEA : 배열의 원소들을 카드라고 생각하자. 정렬된 카드를 왼손에 배치한다고 생각했을 때, 정렬되지 않은 카드들을 한개씩 뽑아서 매번 적절한 위치에 배치시킨다. 이 과정을 탁자위의 카드가 한개도 남지 않을 때 까지 반복하면 결국 손에 남아 있는 카드들은 정렬 된 상태를 유지한다. 입력 : n개의 수들로 이루어진 수열 { $a_1$, $a_2$, $a_3$, .... , $a_n$ } 출력 : $a'_1$ $\leq$ $a'_2$ $\leq$ $a'_3$ $\leq$ .... $\leq$ $a'_n$ 을 만족하는 입력 수열의 재배치 STEP : PSEUDO CODE ( 의사 코드 ): 0. Insertion_sort( A ){ 1. for j = 2 to..

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가 ..

문제 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음 그림은 N=3일 때의 예이다. 입력 첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다 출력..