Development Project

문제 링크 : 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/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개의 포지션에 배치될때, 모두의 능력을 잘 발휘하여 모든 선수의 총 능력치 합의 최대를 출력하는 문제 이해 문제가 간단해서 이해가 어렵진 않았다. 문제를 익숙한 용어로 재정의와 추상화 이해가 어렵지 않아서 생략했다. 문제를 어떻게 해결할 것인가 백트래킹을 사용해야 할것같아서 조건을 따지기 위해 그려보았다..

문제 링크 : https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 소요 시간 : 3시간.. 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 512MB 문제 블록을 놓을 횟수(1≤N≤10,000), t개의 블럭 종류(1≤t≤3) 좌표 x(0≤x≤3), y(0≤y≤3) 빨간색 영역 안에서 3가지 종류의 블럭중 하나를 놓으면, 각각 초록색, 파란색 영역으로 떨어진다. 빨간영역에 블럭을 놔둔 좌표를 기준으로 초록영역은 같은 열에 맞게 떨어지..

문제 링크 : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 소요 시간 : 1시간 반 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 256MB 문제 N개의 집(2≤N≤100,000), M개의 길 수(1≤M≤1,000,000), 길 유지비(1≤C≤1,000) 두개의 마을로 분할할때, 나머지 길의 유지비의 최솟값을 출력하는 문제 이해 N개의 집(노드), M개의 길 수(간선), C의 유지비(가중치)이므로,..

문제 링크 : https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 소요 시간 : 10분 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 128MB 문제 서로다른 N개의 자연수의 합이 S(1≤S≤4,294,967,295) S를 알때 N의 최댓값을 구하는 문제 이해 서로 다른 N개의 자연수로 최댓값을 구하는 것이므로, 가장 작은 자연수부터 더했을때 S보다 커지는 값을 찾고 그때 -1을 하면 답이된다! 그 외의 처리나, 다른 절차는 필요없는 문제.. 계획 수행 (실제코드 작성) - 평소였다면 5단계에 위치했을테지만 너무 간단해서 바로 코드로 썼다. Java 11 im..

문제 링크 : https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 소요 시간 : 최적화 시간까지 합치면 4시간.. 어후 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 1024MB 문제 NxM의 지도(2≤N,M≤20), 이동횟수 K(1≤K≤1,000) 주사위를 (1,1)부터 K번만큼 [문제에서 주어진 조건에 따라 방향을 정하고, 해당방향으로 한칸 이동하여(해당 방향으로 주사위가 넘어지게 함) 주사위를 이동한 뒤, 해당 지점으로..

문제 링크 : https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 소요 시간 : 1시간 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 1024MB 문제 NxN의 격자(3≤N≤20), 학생의 번호 ni(1≤ni≤N*N) 각 학생마다 좋아하는(인접하길 바라는) 학생이 4명씩 있다. 자리를 배치할때, 1. 좋아하는 학생이 많이 인접하도록 2. 좋아하는 학생이 같은수로 인접한 곳이 여러개라면, 인접한 칸중 빈곳이 많도록 3. 빈곳도 마찬가..

문제 링크 : https://www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net 소요 시간 : 40분 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 128MB 문제 방의 개수 N개(1≤N≤1,000), 방별 비용(0≤N≤500), 방의 유형은 빈방, 레프리콘방, 트롤방임 1번방에서 N번방으로 갈 수 있는지 여부를 출력하는 문제이고, 방의 경우에 따라 갈수있는지 불가능한지 정해진다 빈방은 변화가 없고, 레프리콘방은 일정금액 이하일경우 돈을 일..

문제 링크 : https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 소요 시간 : 4시간.....ㅎㅎㅎㅎㅎㅎ 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 128MB 문제 노드의 개수 N개(1≤N≤10,000), 간선의 개수 N-1개 트리의 끝부분(리프노드)를 잡고 쫙 폈을때 가장 긴 길이를 구하는 문제 이해 문제 이해는 어렵지 않았는데, 문제에서 예시로 준 그림이 왜 45가 되는지 분석하지않고 문제에 바로 접근해서 많이 삽..