자료구조 및 알고리즘/문제풀이
-
[KOITP] 히스토그램에서 가장 큰 직사각형(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 20. 08:29
출 처 : http://koitp.org/problem/ULM_LOCAL_2003_H/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수2.0 초128 MB31 (33%)1문제히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수 있다. 예를 들어, 아래에서 왼쪽 그림은 높이가 순서대로 2,1,4,5,1,3,32,1,4,5,1,3,3이고, 너비는 모두 11인 직사각형으로 이루어진 히스토그램이다.너비가 1인 N개의 직사각형으로 이루어진 히스토그램이 주어진다. 이 때, 위에서 오른쪽 그림처럼 히스토그램 내에서 가장 큰 직사각형의 크기를 구하는 프로그램을 작성하시오.입력입력은 여러 개의 테스트케이스로 이루어져 있다. ..
-
[KOITP] 철로(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 20. 08:29
출 처 : http://koitp.org/problem/ICPC_2016DAJI_RAILWAY/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB61076 (12%)66문제집과 사무실을 통근하는 nn명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A,BA,B에 대하여, AA의 집 혹은 사무실의 위치가 BB의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 dd로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하..
-
[KOITP] 지름(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 20. 08:28
출 처 : http://koitp.org/problem/ICPC_2016DAJI_DIAMETER/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB797 (9%)7문제2차원 좌표 평면에 nn개의 점이 주어진다. 주어지는 점을 두 개의 집합으로 나눌 수 있다. 한 집합 내에 가장 먼 두 점의 거리를 지름(diameter)라고 하는데, 두 집합의 지름 합을 최소화하는 프로그램을 작성하시오예를 들어, (a)처럼 9개의 점이 좌표 평면에 있다고 하자. 9개의 점을 두 집합으로 나누는 방법은 여러 가지가 있다. (b)처럼 빨간 점 집합, 파란 점 집합, 두 개의 집합으로 나누는 경우 파란 점 집합의 지름이 √42+32=542+32=5가 되고, 빨간 점 집합의 지름이 √52+12..
-
[KOITP] 호감도(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 20. 08:27
출 처 : http://koitp.org/problem/GOOD_FEELING/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초256 MB21233 (16%)19문제키에 관심이 많은 수근이는 키가 호감도에 영향을 주는지 알고 싶다. 약 한달동안 주변 사람들에게 설문을 해 데이터를 얻었다. 각 데이터는 키에 따른 호감도 정도인데 x 축이 키 이고 y 축이 호감도이다. 우리는 이들이 상관관계가 있는지 알고 싶다.하지만 수근이는 상관관계를 어떻게 구하는지 모르기 때문에 여러 고민을 하게 된다. 그래서 생각해낸 방법이 어떠한 직선 위에 데이터의 20% 이상 점들이 있으면 상관관계가 있다고 생각하려고 한다. 키에 예민한 수근이를 도와 데이터를 받아 상관관계가 있는지 없는지 체크해주는 프..
-
[KOITP] Number of Inversion(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 20. 08:26
출 처 : http://koitp.org/problem/NUMBEROFINVERSION/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB640155 (24%)132문제Inversion이란, 어떤 수열 A에서 i A_j 인 경우를 의미한다. 예를 들어, 수열 A의 원소가 각각 순서대로 3, 1, 2인 경우, (i=1, j=2)인 Inversion과 (i=1, j=3)인 Inversion 두 개가 존재한다.1부터 N까지 수들로 이루어진 순열이 주어질 때, Inversion의 개수를 출력하라.입력첫 번째 줄에 순열의 길이 N이 주어진다. (2 ≤ N ≤ 100,000)두 번째 줄에 순열의 각 원소가 공백으로 분리되어 주어진다.출력첫 번째 줄에 주어진..
-
[KOITP] 가장 거리가 먼 두 점(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 19. 07:45
출 처 : http://koitp.org/problem/FARTHEST_PAIR/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초128 MB21 (50%)1문제2차원 좌표 평면에 NN개의 점이 주어진다. 좌표가 같은 점이 주어질 수도 있다.두 점 사이의 거리는 유클리드 거리로 정의한다. 유클리드 거리에서 두 점 (x1,y1)(x1,y1), (x2,y2)(x2,y2) 사이의 거리를 √(x1−x2)2+(y1−y2)2(x1−x2)2+(y1−y2)2로 정의한다.이 때, 가장 먼 두 점 사이의 거리를 구하는 프로그램을 작성하시오.입력첫 줄에 점의 개수를 나타내는 자연수 NN이 주어진다. (2≤N≤200,0002≤N≤200,000)그 다음 NN개의 줄에 각 점의 xx, yy 좌표를 나타내..
-
[KOITP] 최대공약수가 1이 되는 것자료구조 및 알고리즘/문제풀이 2017. 1. 19. 07:44
출 처 : http://koitp.org/problem/GCDISONE/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB656144 (22%)123문제어떤 수열 S가 주어진다. 수열 S에서 한 개 이상 원소를 선택했을 때, 선택한 수 혹은 수들의 최대공약수가 1이 되는 것의 개수를 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100) 두 번째 줄부터 N개의 줄에 걸쳐 수열의 각 원소 Si가 주어진다. 어떤 두 원소가 같을 수 있다. (1 ≤ Si ≤ 100,000)출력첫 번째 줄에 정답을 10,000,003으로 나눈 나머지를 출력한다.힌트예제 입력3 2 4 3 예제 출력3 예제 설명주어진 수를 이용해서 선택하는 모든 방법..
-
[KOITP] 집합 판별(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 19. 07:43
출 처 : http://koitp.org/problem/SDS_PRO_8_7/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수2.0 초512 MB35265 (18%)55문제민규는 어떤 문자열이 주어졌을 때, 그것이 집합인지 판단하는 것은 매우 쉬운 일이라고 주장하고 있다.당신은 민규의 콧대를 납작하게 만들어 주기 위해, 다음과 같이 집합(Set)을 정의했다. 는 집합이 비어 있을 수 있다는 것을 의미한다.이렇게 집합을 정의하면 집합의 원소를 이루는 문자열이 모호해지기 때문에, 집합인지 판단하는 것이 어려운 문제가 된다.Set::= Set ::= "{" Elementlist "}" Elementlist ::= | List List ::= Element | Element "," List E..