본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/수학

 (16)
[백준 / BOJ] 1153 네 개의 소수 (Java) 문제 출처 : https://www.acmicpc.net/problem/1153 1153번: 네 개의 소수 임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. www.acmicpc.net 1
[백준 / BOJ] 1124 언더프라임 문제 출처 : https://www.acmicpc.net/problem/1124 1124번: 언더프라임 자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다. 어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, www.acmicpc.net 두 양의 정수 A,B가 주어졌을때, A,B사이의 언더프라임을 구하는 문제다. 여기서 언더프라임은 정수의 소인수분해의 결과로 나온 소수들의 길이가 소수인 수를 의미한다. 풀이 에라토스테네스 채를 이용해서 A,B사이의 모든 소수들을 구해놓은 후, A,B사이에 있는 임의의 정수 X가 언더프라임인지 확인하는 방식으로 푸는 문제다. 이 때, 시간이 애매할거 같아서, 연산을 빠..
[백준 / BOJ] 17403 가장 높고 넓은 성 (Graham scan) 문제 출처 : https://www.acmicpc.net/problem/17403 17403번: 가장 높고 넓은 성 첫 번째 줄에 n개의 정수 x1, x2, ..., xn을 공백으로 구분하여 출력한다. xi는 i 번째 표지판이 사용되었을 경우 사용된 층수이며, 사용되지 않았으면 0이다. www.acmicpc.net 2차원 평면에 n개의 표지판이 주어진다. 이 표지판을 이용해서 다음 규칙을 만족하는 가장 높은 성을 짓는 문제이다. - n층은 n-1층 위에 지어진다. 이때, 각 층은 최대한 넓어야하며, 가능한 한 적은 수의 표지판을 사용해야 한다. 풀이 컨벡스 헐 알고리즘으로 푸는 문제다. 논리는 간단한데, 1. 현재 선택되지않은 표지판을 이용해 가장 넓은 성을 만든다. 2. 남아있는 표지판을 이용해 가장 ..
[백준 / BOJ] 1060 좋은 수 (CPP) 문제 출처 : https://www.acmicpc.net/problem/1060 1060번: 좋은 수 정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다. A와 B는 양의 정수이고, A < B를 만족한다. A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다. 정수 www.acmicpc.net 정수 집합 S가 주어진다. 이때 다음 두 조건을 만족하는 범위[A,B]의 갯수가 적을수록 좋은 수 라고 한다. A와 B는 양의 정수이고, A < B를 만족한다. A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다. 이때, 좋은 수 n개를 좋은 수 순서대로(같다면 작은 수를 먼저) 출력하는 문제다. 풀이 문제 이해만 되면 풀이 생각하기는 쉬운 ..
[백준 / BOJ] 10885 수열의 장인 문제 출처 : https://www.acmicpc.net/problem/10885 10885번: 수열의 장인 승현이는 수열을 찾는 사람들을 위해 길이가 N 인 수열 a1, a2, ··· , aN을 만드는 일을 하고 있다. 승현이는 경력이 짧아서 각 원소가 -2 이상 2 이하의 정수인 수열만 만들 수 있고, 그래서인지 수 www.acmicpc.net 길이 N의 수열이 주어진다. 수열의 각 수는 -2, -1, 0, 1 2로 이루어져있으며, i번째 수열을 Ai, j번째 수열을 Bj라 하자. (i
[백준 / BOJ] 9375 패션왕 신해빈 (Java) 문제 출처 : https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 해빈이는 N개의 옷을 갖고있다. 패션에 매우 민감한 해빈이는 날마다 다른조합의 옷을 입어야한다. 이때, 해빈이가 옷을 조합이 겹치지않게 입을수있는 최대 날짜를 계산하는 문제다. 풀이 솔브드 난이도가 실4로 되어있길래, 생각없이 백트래킹으로 풀었는데, 시간초과가 났다. N이 최대 30이므로 모..
[백준 / BOJ] 16967 배열 복원하기 문제 출처 : https://www.acmicpc.net/problem/16967 16967번: 배열 복원하기 크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐 www.acmicpc.net 크기가 H*W인 배열A를 아래로 X 오른쪽으로 Y만큼 이동한 배열을 배열 A와 겹쳤을때 나온 배열을 배열 B라고 하자. (배열이 겹쳐지면 같은 위치의 수가 합쳐진다.) 배열의 크기 H, W 이동범위 X, Y, 배열 B가 주어질때 배열 A를 구하는 문제다. 풀이 수학? 구현? 문제다. 배열B가 주어졌을때, 원래 배열의 (i,j)의 값은 다음과 같..
[백준 / BOJ] 1033 칵테일 (Java) 문제 출처 : https://www.acmicpc.net/problem/1033 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 제조하기위한 재료의 갯수 N과 각 재료의 비율이 주어졌을때, 칵테일을 만들기위해 필요한 재료의 질량을 출력하는 문제다. 풀이 유클리드 호제법을 응용해서 푸는 수학 문제였다. 문제에서 두가지 재료의 비율이 주어진다. 이 비율을 갖고 각 재료의 질량을 구하는 공식을 만들어보면, 재료를 각각 a,b 비율을 p,q라 했을때, ..

티스토리툴바