자료구조 및 알고리즘
-
[KOITP] 계단 오르기자료구조 및 알고리즘/문제풀이 2017. 1. 18. 08:37
출 처 : http://koitp.org/problem/SDS_PRO_7_6/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1497180 (12%)162 문제최대 2 칸 까지 오를 수 있을 때 오르는 방법의 가짓수를 생각해 보자. 아래 그림은 n 이 4 인 경우의 예 이다. 1 - 2 - 3 - 41 - 2 - 41 - 3 - 42 - 3 - 42 - 4총 5가지 경우가 존재한다. 그렇다면 계단의 수가 n개일 때는 경우의 수가 몇가지 존재할까? 답이 커질 수 있으므로 답을 1,000,000,007로 나눈 나머지를 출력한다.입력입력의 첫 줄은 계단의 갯수 (1
-
[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..