Development Project

문제 링크 : https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 소요 시간 : 2시간 놀이 공원 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 8880 2265 1582 24.835% 문제 N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다. 모든 놀이기구는 각..

문제 링크 : https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 소요 시간 : 20분 키로거 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 42692 11542 7757 25.369% 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따..

문제 링크 : https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 소요 시간 : 30분 ATM 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 76431 51125 41420 67.455% 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지..

문제 링크 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 소요 시간 : 15분 바이러스 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 114556 55077 37094 46.184% 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있..

문제 링크 : https://www.acmicpc.net/problem/2314 2314번: 이세계 게임 'P' 또는 'L'을 값으로 갖는 4×4 행렬이 공백 없이 주어진다. 이는 현재 주민들의 배치를 나타내며, 'P'는 Portableangel, 'L'은 Legnaelbatrop 종족을 뜻한다. 그 다음 빈 줄이 0개 이상 주어진 뒤 택희가 원 www.acmicpc.net 소요 시간 : 30분 이세계 게임 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 64 27 23 41.071% 문제 트럭 운전사 택희는 오랜 기간 동안의 공로를 인정받아 이세계로 소환되었다. 택희가 소환된 이세계에는 천사 종족 Portableangel과 악마 종족 Legnaelbatrop이 살고 있었다. 택희는 뛰..

문제 링크 : https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 소요 시간 : 2시간 반 경사로 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 22652 12421 8935 55.753% 문제 크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다. 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 다음과 같은 N=6..

문제 링크 : https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 소요 시간 : 2시간 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 256MB 문제 원숭이가 점프 할 수 있는 횟수K(0≤K≤30), 지도의 가로W, 세로 H(1≤W,H≤200) 원숭이가 한번에 상하좌우 한칸씩 갈 수 있는데, K번만큼 체스의 나이트처럼 움직일 수 있을 때 최소 몇번의 이동으로 도착지(지도의 가장 우측하단)까지 갈 수 있는지 출력하는 문제 이해 ..

문제 링크 : https://www.acmicpc.net/problem/17218 17218번: 비밀번호 만들기 첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열 www.acmicpc.net 소요 시간 : LCS 학습하는 시간 포함해서 2시간 반 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 256MB 문제 수형이가 입력한 난수의 길이(1≤길이≤40) 최장공통수열을 구하라는 문제 이해 문제 읽자마자 최장공통수열(LCS) 쓰라는 문제구나 싶었는데, 듣기만 들었지 제대로 학습해 본적이 없어 자료를 찾아보았다. 문제를 익숙한 용어로 재정의와 추상화 문제 이해에 어려..

문제 링크 : https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 소요 시간 : 50분 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 128MB 문제 유저 N명(2≤N≤100), 친구 관계의 수 M개(1≤M≤5,000) 주어진 N명의 사람이 최소 한명씩이랑 친구관계인데, 가장 인맥을 덜 거쳐도 알 수 있는 최소의 관계수를 출력하는 문제 즉, 모두가 나와 누구를 통하지않고 바로 친구관계라면 가장 ..

문제 링크 : https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 소요 시간 : 12분 문제를 읽고 이해하기 제한 시간 : 5초 메모리 : 256MB 문제 저장된 전체 주소 N개(1≤N≤100,000), 궁금한 주소 M(1≤M≤100,000) 주소와 비번쌍이 N개 주어질 때, M개의 주소에 대한 비번을 출력하는문제 이해 너무 간단한 문제라 이해에 시간을 크게 쏟지 않았음 문제를 익숙한 용어로 재정의와 추상화 문제 이해..

문제 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 소요 시간 : 1시간 - 그리디와, 자바의 정렬방법이 익숙치 않아 생각보다 시간을 썼던 문제이다. 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 128MB 문제 회의의 수 N개(1≤N≤100,000), N개의 시작시간과 종료시간(0≤N≤2^31-1) 회의가 같은 시간에 진행 될 수 없을 때, 최대 몇개의 회의를 진행할 수 있는지 출력하는 문제 이해 문제를 보자마자 그리디의 전형이라 생각했고, 어떻게 그리디를 구현해야할지 고민해보았다. 문제를 익숙한 용어로 재정의와 추상화 문제 이해에 어려움은 ..

문제 링크 : https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 소요 시간 : 2시간 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 512MB 문제 N x M의 지도(1≤N,M≤50)에 숫자나 구멍(H)가 기록되어 있다. 지도의 왼쪽 상단으로부터 출발하여 해당 포지션에 기록된 숫자만큼 상/하/좌/우로 이동이 가능한데, 맵밖으로 빠져나가거나 구멍에 도착하지 않는 한 무한히 이동이 가능하다. 이때, 최대로 이동할 수 있는 횟수를 구하는 문제이다..

문제 링크 : https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 소요 시간 : 2시간 반 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 128MB 문제 W x H의 지도(1≤W,H≤100) 지도에 출발점 및 도착점(C), 벽(*), 빈방(.)이 있을때 C를 연결하기위한 최소 거울의 수를 출력하는 문제 거울은 /과 \모양이 있으며, 90도씩 방향을 회전 시킬 수 있다. 이해 문제이해는 어렵지 않았고, 완탐을 통해 전체 탐색하거나, 규..

문제 링크 : https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 소요시간 : 자바 파이썬 둘다 코딩하는 시간 포함 15분정도. 행복한 문제~ 이번 문제는 솔브닥 클래스를 올리고싶어서 풀게된 문제로, 최소힙을 구현할 수 있는지에 관한 문제이다! 우선 힙을 어떻게 구현해야하는지 살펴보자! 자바의 경우 PriorityQueue를 이용해 최소힙과 최대힙 둘다 구현 가능하다 만약 사용자 정의 Class를 큐로 쓰고싶다면, Compara..

문제 링크 : https://www.acmicpc.net/problem/1581 1581번: 락스타 락동호 한국이 낳은 세계적인 락스타 락동호는 2007년 2월 1일 역대 최대 규모의 콘서트를 열었으며, 2007년 2월 11일에 자신의 음악세계를 세상에 알리고, 2007년 3월 4일에는 자신의 작곡 비법을 세계에 공 www.acmicpc.net 소요 시간 : 1시간 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 128MB 문제 빠른 시작-빠른 끝(FF), 빠른 시작-느린 끝(FS), 느린 시작-빠른 끝(SF), 느린 시작-느린 끝(SS) (0≤FF, FS, SF, SS≤1,000) [_F]는 무조건 [F_]앞에 와야하고, [_S]는 무조건 [S_]앞에 와야한다 [F_]가 하나라도 있다면 첫곡은 [F..

문제 링크 : https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소요 시간 : 1시간 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 1024MB 문제 자연수 N(1≤N≤4,000,000) N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제 이해 문제이해도 어렵지 않고, 소수라는 말만 봐도 에라토스테네스의 체를 이용하는게 최선이므로, 바로 구현방법이 떠올랐다. 문제를 익숙한 용어로 재정의와 추상화 문제이해가 어렵지 않아서 생략하겠다. 문제를 어떻게 해결할 것인가 1st 접근 - 에라토스테네스의 체와 투포인터 배열) 소수를 에라토스테네스의 체를 ..

문제 링크 : https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 소요 시간 : 2시간 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 512MB 문제 NxN의 지도(2≤N≤20), M명의 승객(1≤M≤N^2), 초기연료(1≤N≤500,000) 지도의 크기및 상태가 주어지고 택시의 출발점, 각 승객의 출발지 도착지가 주어졌을때, 주어진 연료를 사용하여 모든승객을 도착지로 데려다주고 남은 연료의 최댓값을 구..

문제 링크 : https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 소요 시간 : 3시간 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 192MB 문제 N개의 꽃(1≤N≤100,000) 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어있어야 하고, 가능한 정원에 심는 꽃들의 수를 가능한 적게 해야한다. 이해 조건대로 수행하면 되는데, 이제 어떻게 접근하여 최적화 할지 생각해야하는 문제이다. 문제를 익숙한 용어로 ..

문제 링크 : https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 소요 시간 : 40분 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 1024MB 문제 문제의 수(0≤N≤500,000), 문제를 칠하는 색상은 각각 B아니면 R 한 문제 이름을 덧칠해도 마지막 칠한색만 보여질때, 최소로 문제를 칠할 수 있는 횟수를 출력 이해 문제에서 B와 R중 많은색을 먼저 배경에 칠해두고, 적게 칠해진 색을 칠하는 방식으로 짜야한다고 생각했다. 문제를 익숙..

문제 링크 : https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 소요 시간 : 50분 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 128MB 문제 11명의 선수가 11개의 포지션에 배치될때, 모두의 능력을 잘 발휘하여 모든 선수의 총 능력치 합의 최대를 출력하는 문제 이해 문제가 간단해서 이해가 어렵진 않았다. 문제를 익숙한 용어로 재정의와 추상화 이해가 어렵지 않아서 생략했다. 문제를 어떻게 해결할 것인가 백트래킹을 사용해야 할것같아서 조건을 따지기 위해 그려보았다..