개발새발 개발자 데브당에

문제 바로가기 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제풀이 시험관에 존재하는 바이러스는 1초마다 번호순으로 증식되기 때문에 BFS를 적용하도록 한다. PriorityQueue를 사용하여 시간/번호순으로 정렬이 가능하도록 Virus 클래스에 Comparable 인터페이스를 적용한다. 구현 0. Virus 클래스에 Comparable을 적용하여, 시간순 -> 번호순으로 큐가 정렬되도록 함 1. 바이러스가 존재하면 PriorityQueue에 offer 2-1. X, Y 좌표..

문제 바로가기 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제풀이 바이러스에 감염된 컴퓨터를 확인하기 위해 컴퓨터끼리의 연결상태를 확인해야한다. 컴퓨터끼리의 연결상태를 인접행렬로 표시한다.(연결되어있으면 1로 표기 ) 감염된 컴퓨터를 큐에 넣고, 큐가 빌때까지 반복하면서 해당 컴퓨터와 연결된 컴퓨터를 감염시킨다.(BFS) 변수 computer : 컴퓨터의 감염여부를 담는 boolean 배열 map : 컴퓨터끼리 연결상태를 나타나는 2차원 인접행렬 q : 바이러스에 감염된 컴퓨터를 확인하기 위해 BFS에서 사용..

문제 바로가기 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 문제풀이 회사원별로 출퇴근 여부를 확인해야하기 때문에 HashMap을 사용하였다. key는 회사원 이름, value는 출퇴근 여부 boolean 값으로 초기화했다. 해쉬맵이 회사원 key 값을 가지고 있으면 value값만 다시 지정해준다. 회사원 key를 가지고 있지 않다면 회사원 정보를 put한다 만약 출입기록이 'enter'이면 value는 true이고 아니면 false가 되도록 한다. hashmap 내림..

문제설명 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 제한사항 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 문제풀이 동전이 오름차순으로 정렬되어 입력되기 때문에 뒤에서부터 동전이 계산 가능한지 확인한다. input 배열을 뒤에서부터 탐색 n번째 input 값이..

문제설명 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 제한사항 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 문제풀이 이번 문제는 이중 for문을 적용할 경우, 시간초과에 걸리는 문제입니다. 따라서 연속된 수열의 시작점(left)과 끝점(right)을 인덱스로 지정하여 ..