본문 바로가기

PS

 (53)
[백준 / 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] 12101 1, 2, 3 더하기 2 (cpp) 문제 출처 : https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 만들려는 숫자 n이 주어졌을때, n을 1,2,3을 이용해서 만들고 n을 만드는 경우의 수의 조합중 k번째를 찾아 출력하는 문제이다. 풀이 이런 유형의 DP를 풀어본적이 있어서 DP라고 착각했지만, n의 최댓값이 11로 작아서 완전탐색으로도 풀리는 문제다. 로직은 간단한데, 재귀를 이용해서 1,2,3으로 숫자 n을 만드는 모든 경우의 수를 저장해놓은다음 정렬 후 출력하면 된다. 주요 소스코드 void getComb(i..
[백준 / 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] 10891 Cactus? Not cactus? (cpp) 문제 출처 : https://www.acmicpc.net/problem/10891 10891번: Cactus? Not cactus? 첫 번째 줄에 그래프의 정점의 개수와 간선의 개수를 나타내는 두 정수 N,M (1 ≤ N,M ≤ 100,000) 이 공백으로 구분되어 주어진다. 다음 M개의 줄에는 간선이 연결하고 있는 두 정점을 나타내는 두 정 www.acmicpc.net 양방향 그래프에서 각 정점에서 시작해 자기 자신으로 돌아오는 사이클이 2개 이상이라면 Cactus가 아니며, 하나 이하라면 Cactus이다. 이 때, 주어진 그래프가 Cactus인지 Not cactus인지 출력하는 문제다. 풀이 처음에는 단절점을 찾고, 단절점에 대해 자식 트리가 2개 이상이라면 Not cactus를 출력하게 해줬는데, ..
[백준 / BOJ] 23247 Ten (Java) 문제 출처 : https://www.acmicpc.net/problem/23247 23247번: Ten Your program is to read from standard input. The input starts with two positive integers $m$ and $n$ ($1 \le m, n \le 300$), denoting the dimensions of the land, which are given separated by a space. Each of the following $m$ lines contains $n$ positive in www.acmicpc.net N*M그리드에서 A*B범위의 사각형을 만들때, 그 사각형 범위안에 포함된 원소의 합을 10으로 만드는 사각형 범위의 갯수..
[백준 / BOJ] 2812 크게 만들기 (Java / 세그먼트 트리) 문제 출처 : https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N자리의 수가 주어지며 이 수에서 K개의 숫자를 제거했을때 얻는 가장 큰 수를 구하는 문제이다. 풀이 세그먼트 트리로 푼 문제다. 문제를 N자리의 수에서 (N-K)개의 숫자를 선택하는 문제로 바꾼다면, 현재 선택가능한 범위 (left ~ right)에서 (N-K)번 숫자를 뽑아 최댓값을 만드는 문제로 바뀌게 된다. 이때, left ~ right의 범위는 최대 250,000만큼 차이가 날 수 있으므로, 완전탐색으로 현재 범위에서 최댓값을 찾는다면, (250,00..
[백준 / 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] 9655 돌 게임 (Java) 문제 출처 : https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net N개의 돌이 주어지고, 두명의 플레이어(상근, 창영)가 있다. 각 플레이어는 번갈아가며 돌을 가져가는데 자신의 턴마다 1개 혹은 3개의 돌을 가져갈 수 있다. 플레이어는 매번 최선의 선택을 한다고 가정했을때, 상근이가 이기는지 창영이가 이기는지 구하는 문제다. 전형적인 게임이론 문제다. dp배열을 dp[남아있는 돌의 수][turn] = 이긴 플레이어 와 같이 설정하고 자신이 이기는경우가 있다면 항상 그 경우를 선택하면 된다. 즉, 자신이 이기는 경우가 한번이라도 존재한다면, 절대로 지지 않는다.(매번 최..

티스토리툴바