본문 바로가기

Algorithm(알고리즘)131

[Jungol][Java][Greedy,활동 선택 ] 1828 - 냉장고 jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=30 JUNGOL www.jungol.co.kr 문제 N개의 화학 물질 C1, C2, …, Cn이 있다. 이들 각각은 보관되어야 할 온도가 각기 다른데, 각 Ci마다 최저 보관 온도 xi와 최고 보관 온도 yi가 정해져 있다. 즉 Ci는 온도 xi이상, yi이하의 온도에서 보관되어야만 안전하다. 이 화학 물질들을 모두 보관하기 위해서는 여러 대의 냉장고가 필요한데 가능하면 적은 수의 냉장고를 사용하고 싶다. 이를 해결하는 프로그램을 작성하시오. 입력형식 첫줄에 화학물질의 수 N이 입력된다. N의 범위는 1이상 100 이하이다. 두 번째 줄부터 N+1줄까지 최저보관온도와 최고보관온도가 입력된다. 보관온도는.. 2021. 2. 18.
[Java] [백준 1062][재귀,분할정복] 쿼드트리 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된.. 2021. 2. 17.
[Java] [백준 1062][백트랙킹,비트마스크] 가르침 www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌.. 2021. 2. 16.
[완전탐색][재귀][Bitmask][Java] 순열과 조합, 부분집합에 관하여 순열 (Permutation) 순열이란 서로 다른 것들 중 몇개를 뽑아 한 줄로 나열하는 것을 말한다. 쉽게 말하자면 뽑은 수들의 순서가 의미가 있으면 순열이다. (ex) 반장, 부반장 한명씩 뽑는 경우 : 뽑는 순서에 따라서 다른 의미를 가진다. => ab와 ba는 다르다. 순열을 재귀함수로 표현하기 위해서는 해당 인덱스에 해당하는 숫자가 이미 사용중인지 저장하고 있는 별도의 배열이 필요하다. 만약에 이미 뽑은 인덱스의 경우에는 넘어간다. 뽑지 않았다면 해당 수를 저장하고 방문처리를 하고 index+1을 하고 재귀에 들어간다. 이때 주의해야 하는 점은 방문처리를 다시 되돌려야 한다는 점이다. 되돌리지 않는다면 다음 순열을 구할때 영향이 미친다. import java.util.Arrays; public .. 2021. 2. 7.

티스토리툴바