자료구조 및 알고리즘/문제풀이
-
[KOITP] 가장 가까운 두 점자료구조 및 알고리즘/문제풀이 2017. 1. 18. 08:36
출 처 : http://koitp.org/problem/SDS_PRO_7_7/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수4.0 초512 MB72687 (12%)73문제2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. 제한시간 : 2초입력첫째 줄에 자연수 n(2≤n≤500,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다.출력첫째 줄에 가장 가까운 두 점의 거리의 제곱을 출력한다.힌트입력 예제4 0 0 10 10 0 10 10 0 출력 예제100 사실 너무 아슬아슬하게 통과해서, 이걸 맞췄다고 봐야할지도 애매한 것 같..
-
[KOITP] 나누기자료구조 및 알고리즘/문제풀이 2017. 1. 18. 08:34
출 처 : http://koitp.org/problem/SDS_PRO_7_4/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초32768 MB587387 (66%)328 문제아래와 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 0으로 칠해져 있거나 1로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 0 또는 1로 칠해진 색종이를 만들려고 한다.11000011 11000011 00001100 00001100 10001111 01001111 00111111 00111111 전체 종이의 크기가 N×N(N=2^k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종..
-
[KOITP] 중앙 문자열(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 17. 08:13
출 처 : http://koitp.org/problem/SDS_PRO_6_8/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB816191 (23%)163문제문자열에서 교체 연산은 문자열의 한 문자를 다른 문자로 바꾸는 연산이다. 예를 들어, 문자열 “computer”에서 4번째 문자 p를 m으로 교체하면 “commuter”가 된다.같은 길이의 두 문자열 P와 Q의 거리 d(P,Q)는 P를 Q로 바꾸기 위한 교체 연산의 최소 개수로 정의된다. 예를 들어 P = “computers”, Q = “consumers”라 하면, P에서 3번째 문자 m을 n으로, 4번째 문자 p를 s로, 6번째 문자 t를 m으로 바꾸면 Q가 된다. 따라서 P와 Q 사이의 거리는 3이다.A, B,..
-
[KOITP] 상인(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 17. 08:12
출 처 : http://koitp.org/problem/SDS_PRO_4_8/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1134131 (12%)93문제사막에 N(1≤N≤100,000)개의 도시가 있고, 각 도시에는 1부터 N까지의 번호가 매겨져 있다. 두 도시를 연결하는 N-1개의 길이 있으며, 임의의 두 도시 사이에는 길들을 따라 이동할 수 있는 경로가 하나만 존재한다. 어떤 사람이 하나의 길을 지나는 데는 정확히 하루가 걸리며, 길 이외의 장소에서는 마실 물을 구할 수 없어 이동할 수 없다.한 상인이 1번 도시부터 N번 도시까지를 순서대로 방문하며 장사를 하려고 한다. 이 상인이 1번 도시부터 N번 도시까지 순서대로 방문하는데 며칠이 걸리는지를 계산하여 출력..
-
[KOITP] 술 약속(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 17. 08:11
출 처 : http://koitp.org/problem/SDS_PRO_6_6/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1209259 (21%)231문제동현이는 술을 좋아한다. 그런데, 동현이는 멍청하게도 같은 날에 여러개의 술 약속을 잡았다. 약속을 잡은 모든 사람들은 다들 동현이에게 술을 먹이고 싶어 한다.각 약속에서 만나는 사람들은 동현이가 1분 늦을 때마다 동현이에게 술을 Di 병씩 마시게 할 것이다. 각 약속은 동현이 집에서 Ti 분 거리여서, 동현이는 약속 장소에 가고 오는데 총 2*Ti분이 걸리게 된다. (약속 장소에 갈 때는 항상 동현이 집에서 출발한다.) 다행히도, 오늘의 사정을 아는 사람들은 사람들은 조금의 자비를 베풀어 동현이가 집에서 약속 ..
-
[KOITP] 보석(Not Solved)자료구조 및 알고리즘/문제풀이 2017. 1. 17. 08:10
출 처 : http://koitp.org/problem/SDS_PRO_6_5/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수3.0 초512 MB2548320 (13%)254문제세계적인 도둑 동현이는 보석점을 털기로 결심했다.동현이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 동현이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 각 가방에는 최대 한 개의 보석만 넣을 수 있다.동현이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (1 ≤ Mi, Vi ≤ 1,000,0..
-
[KOITP] 풍선자료구조 및 알고리즘/문제풀이 2017. 1. 17. 08:10
출 처 : http://koitp.org/problem/SDS_PRO_6_4/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1644385 (23%)343 문제큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다. 우리의 목표는 모든 풍선을 ..