자료구조 및 알고리즘
-
[KOITP] 중앙값자료구조 및 알고리즘/문제풀이 2017. 1. 12. 08:05
출 처 : http://koitp.org/problem/SDS_PRO_3_6/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.1 초512 MB1754452 (26%)379 문제정수가 N개 주어진다. 홀수번째 수가 주어질 때마다, 지금까지 주어진 수의 중앙값을 구하는 프로그램을 작성하여라. 예를 들어 1, 4, 5, 3, 6가 주어진다면, 첫번째 수인 1을 입력받을 때 중앙값이 1이고, 세 번째 수인 5를 입력받을 때까지의 중앙값이 4이고, 다섯번째 수인 6을 입력받을 때까지의 중앙값이 4이므로 1, 4, 4를 순서대로 출력하는 것이다.입력첫 번째 줄에 주어지는 정수의 개수 N이 주어진다. (1 ≤ N ≤ 99,999, N은 홀수) 두 번째 줄부터 N개의 줄에 걸쳐 각 줄에 하나씩 정..
-
[KOITP] 같은 문자열(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 12. 08:02
출 처 : http://koitp.org/problem/SEQUENCE/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB15286 (57%)70문제길이가 같은 두 문자열 A,B가 들어온다. A에 포함되어 있는 문자의 순서를 조작했을 때 B가 나온다면 A,B는 같은 문자열이다. 입력으로 들어온 두 문자열이 같은 문자열인지 다른 문자열인지 판단해주는 프로그램을 만들어보자입력문자열의 길이는 N(1
-
[KOITP] Sliding Windows자료구조 및 알고리즘/문제풀이 2017. 1. 12. 08:01
출 처 : http://koitp.org/problem/SLIDING_WINDOWS/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수3.0 초512 MB82597 (12%)76 문제길이가 N인 정수 배열이 있다. 이 배열의 부분배열 중 크기가 K인 부분배열은 총 N-K+1개 있다. 이 부분배열에 대해 부분배열에 속한 최대값, 최소값, 합을 구하는 프로그램을 작성하자. 예를 들어, 배열 [1, 3, -1, -3, 5, 3, 6, 7]이 있고 K=3이라 하자. 이 배열에 크기가 3인 6개의 부분배열들이 있고, 왼쪽에 있는 부분배열부터 순서대로 나열하면 다음과 같다: [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6], [3, 6, 7]..
-
[KOITP] 탑자료구조 및 알고리즘/문제풀이 2017. 1. 12. 08:00
출 처 : http://koitp.org/problem/SDS_PRO_3_4/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수2.0 초512 MB2317549 (24%)432 문제삼성 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높..
-
[KOITP] 동맹의 동맹은 동맹자료구조 및 알고리즘/문제풀이 2017. 1. 12. 07:58
출 처 : http://koitp.org/problem/SDS_PRO_3_2/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수2.0 초512 MB2639491 (19%)382문제낙성마을에는 N명의 사람이 있다. 편의상 각 사람들을 1번부터 N번까지 번호를 매기도록 하자. 처음 이 사람들은 서로를 모르기 때문에, '적대 관계'를 갖고 있다. 하지만 언제까지나 '적대 관계'로 살아갈 수는 없는 법이다. 이 마을의 사람들은 한 두명씩 '동맹 관계'를 맺기로 하였다. 당연히 어떤 사람 A와 B가 동맹 관계를 맺으면, 자연스럽게 A의 동맹들과 B의 동맹들도 서로 동맹 관계를 맺게 된다. 이런 관계들이 많아지다보니 점점 더 복잡한 구조의 동맹 관계가 구성되게 되었다. 누가 누구와 동맹 관계인지 확..
-
[KOITP] 꽃 진열자료구조 및 알고리즘/문제풀이 2017. 1. 9. 19:59
출 처 : http://koitp.org/problem/IOI_1999_FLOWER/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB431106 (25%)78문제꽃집에서는 꽃을 꽃병에 꽂아 진열한다. F개의 서로 다른 꽃이 있고, V개의 꽃병들이 일렬로 있다. 꽃병들은 움직일 수 없고, 왼쪽에서부터 순서대로 1, 2, ..., V번까지 번호가 매겨져있다. 또한, 꽃은 1, 2, ..., F번까지 번호가 매겨져있다. 하나의 꽃병에는 하나의 꽃만 꽂을 수 있는데, 모든 꽃은 자신보다 큰 번호의 꽃보다 왼쪽에 있는 꽃병에 꽂아야 한다. 어떤 꽃을 어떤 꽃병에 꽂느냐에 따라 아름다움의 정도가 다르다. 이 아름다움의 정도는 점수로 수치화되어 표로 정리되어있는데, 만약 꽃이 꽂..
-
[KOITP] 집합(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 9. 19:13
출 처 : http://koitp.org/problem/SET/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1496240 (16%)206문제집합 AA와 BB에 각각 N,MN,M개의 자연수가 들어있다. 이제 다음의 행동을 min(N,M)min(N,M)번 시행할 것이다.집합 AA, BB에서 각각 자연수 하나씩 고르고, 고른 수는 각 집합에서 삭제한다고른 두 수의 차를 그룹 CC에 넣는다.우리의 목표는 그룹 CC에 있는 원소의 합을 최소로 하는 것이다.입력첫 번째 줄에 N,MN,M이 공백으로 분리되어 주어진다. (1≤N,M≤1,000)(1≤N,M≤1,000)두 번째 줄에 집합 AA의 원소인 NN개의 자연수가 공백으로 분리되어 주어진다.세 번째 줄에 집합 BB의 원소인 ..
-
[KOITP] 돌다리 건너기(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 9. 19:13
출 처 : http://koitp.org/problem/SDS_PRO_6_2/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1245393 (32%)339문제절대반지를 얻기 위하여 반지원정대가 출발한다. 원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다. 하나는 이로 다른 하나는 이다.아래 그림 1은 길이가 6인 다리의 한 가지 모습을 보여준다. 그림에서 위의 가로줄은 를 표시하는 것이고, 아래의 가로줄은 를 표시한다. 두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다. 두 다리에 새겨진 각 문자는 {R, I, N, G, S} 중 하나이다.반지원정대가 소유하고 있는 마법의 두루마리에 와 를 건너갈 때 반드시 순서대로..