전체 글
-
[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..
-
[KOITP] 내리막 길자료구조 및 알고리즘/문제풀이 2017. 1. 19. 07:40
출 처 : http://koitp.org/problem/SDS_PRO_7_2/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1694322 (19%)273 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세..
-
[KOITP] Convex Hull자료구조 및 알고리즘/문제풀이 2017. 1. 19. 07:39
출 처 : http://koitp.org/problem/CONVEXHULL/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1523208 (14%)147 문제2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (Convex Hull) 이라 한다. N개의 점이 주어질 때 볼록껍질을 이루는 점의 개수를 구하여라. 만약 볼록껍질을 이루는 한 선분에 3개 이상의 점이 포함된 경우, 양 끝점만을 센다.입력첫 번째 줄에 점의 개수 N이 주어진다. (3 ≤ N ≤ 100,000) 두 번째 줄부터 N개의 줄에 걸쳐 각 점의 좌표를 의미하는 두 정수 x, y가 공백으로 분리되..
-
[KOITP] 점의 위치자료구조 및 알고리즘/문제풀이 2017. 1. 19. 07:38
출 처 : http://koitp.org/problem/SDS_PRO_9_2/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1267218 (17%)176 문제이차원 평면에서 점 N개로 이루어진 다각형이 주어진다. 그리고 평면위의 점 P1, P2가 주어졌을때 점 P1, P2가 다각형의 외부에 있는지, 내부에 있는지 판별하는 프로그램을 작성하시오. 점 P1, P2 는 주어진 다각형의 선분 위에 존재하지는 않는다. 입력첫째 줄에 다각형을 이루는 점의 갯수 (1 ≦ N ≦ 100,000)이 주어지고, 둘째 줄 부터 N개의 점의 정수 좌표(-10^9 ≦ x, y ≦ 10^9)가 입력으로 주어진다. 다각형의 좌표는 시계 방향 또는 반시계 방향 순서로 주어진다. 마지막 두 줄에..
-
[KOITP] 다각형의 넓이자료구조 및 알고리즘/문제풀이 2017. 1. 19. 07:37
출 처 : http://koitp.org/problem/SDS_PRO_9_1/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB2205127 (6%)108문제이차원 평면에 점 N개로 이루어진 단순 다각형이 주어진다. 이때 이 다각형이 평면에서 차지하는 면적을 구해보자. 다각형의 면적은 반드시 0보다 크다.입력첫째 줄에 다각형을 이루는 점의 갯수 (1 ≦ N ≦ 100,000)이 주어지고, 둘째 줄 부터 N개의 점의 정수 좌표(-10^9 ≦ x, y ≦ 10^9)가 입력으로 주어진다. 다각형의 좌표는 시계 방향 또는 반시계 방향 순서로 주어진다.출력주어진 단순 다각형이 이루는 넓이를 소수 둘째 자리에서 반올림 한 값을 출력한다.힌트입력 예시3 1 1 1 2 2 1 출력 ..
-
[KOITP] 증가 부분수열 나누기(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 18. 15:14
출 처 : http://koitp.org/problem/IS_GROUP/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수2.0 초512 MB122 (17%)1문제크기가 NN인 정수로 이루어진 수열이 있다. 이 수열을 여러 개의 증가 부분수열로 나누는데, 수열의 한 원소는 반드시 한 개의 부분 수열에 속해야한다. 이 때, 필요한 증가 부분수열의 최소 개수를 구하는 프로그램을 작성하시오.부분 수열(Subsequence)은 어떤 수열에서 순서를 유지하되, 그 중 일부 항만을 선택하여 만들 수 있는 수열이다. 예를 들어, [1,3,2,4][1,3,2,4]로 이루어진 수열이 있다면, [1,3,4][1,3,4], [1,2,4][1,2,4]등은 부분 수열이 될 수 있지만, [1,2,3][1,2,3]..
-
[KOITP] 최장 증가 부분 수열(LIS) 2자료구조 및 알고리즘/문제풀이 2017. 1. 18. 15:13
출 처 : http://koitp.org/problem/LIS2/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수2.0 초512 MB1513306 (20%)255 문제부분 수열(Subsequence)은 어떤 수열에서 순서를 유지하되, 그 중 일부 항만을 선택하여 만들 수 있는 수열이다. 예를 들어, [1,3,2,4][1,3,2,4]로 이루어진 수열이 있다면, [1,3,4][1,3,4], [1,2,4][1,2,4]등은 부분 수열이 될 수 있지만, [1,2,3][1,2,3]은 부분수열이 될 수 없다. 최장 증가 부분 수열(Longest Increasing Subsequence)은 어떤 수열의 부분 수열 중 각 항이 이전 항에 비해 증가하는 부분 수열을 의미한다. 예를 들어, 수열 [1,8,..
-
[KOITP] 출근자료구조 및 알고리즘/문제풀이 2017. 1. 18. 15:12
출 처 : http://koitp.org/problem/RIGHTDOWN/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB689175 (25%)160 문제삼성이는 매일 출근을 한다. 도로는 아래 그림과 같이 가로 방향 도로가 (H+1)(H+1)개, 세로 방향 도로가 (W+1)(W+1)개가 바둑판 모양으로 배치되어 있다. 상성이네 집은 (1,1)(1,1)이고, 회사는 (H+1,W+1)(H+1,W+1)에 있다. (a,b)(a,b)는 위쪽에서 aa번째, 왼쪽에서 bb번째에 있는 교차로이다. 매일 같은 경로로 운전해간다면 졸음운전의 위험이 굉장히 높아진다. 따라서 아래와 같은 재미있는 방법으로 회사까지 가려고 한다.항상 오른쪽, 또는 아래쪽으로 이동한다.맨 아래와, 맨 오른..