본문 바로가기

전체162

백준 알고리즘 2231 (분해합) - python [문제] 백준 알고리즘 2231 (분해합) > https://www.acmicpc.net/problem/2231 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그 www.acmicpc.net 문제 이름은 분해합이지만, 사실 분해합의 반대 프로세스인 생성자를 구하는 문제이다. 브루트 .. 2019. 10. 16.
백준 알고리즘 9020 (골드바흐의 추측) - python [문제] 백준 알고리즘 9020 (골드바흐의 추측) > https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. www.acmicpc.net 소수 조합의 합으로 모든 짝수를 만들 수 있다는 골드바흐의 추측을 활용한 문.. 2019. 10. 16.
백준 알고리즘 2798 (블랙잭) - python [문제] 백준 알고리즘 2798 (블랙잭) > https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 www.acmicpc.net N개의 수가 주어진 배열에서 3개를 선택해 M에 가까운 수를 만드는 문제이다. 주의할 점은 .. 2019. 10. 16.
백준 알고리즘 4948 (베르트랑 공준) - python [문제] 백준 알고리즘 4948 (베르트랑 공준) > https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) n이 주어졌을 때, n보다 크고, 2n보 www.acmicpc.net 임의의 자연수 n에 대해 n < x 2019. 10. 16.
백준 알고리즘 1929 (소수 구하기) - python [문제] 백준 알고리즘 1929 (소수 구하기) > https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) www.acmicpc.net 에라토스테네스의 체를 이용하라는 문제이다. 소수를 구하기 위해 합성수를 제거하는 방식으로, 2부터 N까지 배수를 제거한다. 2부터 N까지의 소수를 구하기 위해선, N의 제곱근까지만 검사하면 된다. range(N)이 N-1까지이고, 배열이 0부터 시작하는 특성상, 받아온 N을 +1 해주는 트릭을 썼다. [Code] M, N = map(int, input().split()) def prime_sieve(M, N): N += 1 sieve.. 2019. 10. 16.
백준 알고리즘 13460 (구슬 탈출 1,2) - python [문제] 백준 알고리즘 13459 (구슬 탈출) > https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net [문제] 백준 알고리즘 13460 (구슬 탈출 2) > https://www.a.. 2019. 10. 16.
백준 알고리즘 1759 (암호 만들기) - python [문제] 백준 알고리즘 1759 (암호 만들기) > https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net N과 M의 연장선에 있는 문제이다. C와 L로 이름만 바뀌었다. 조건은 최소 1개의 모음과 2개의 자음으로 구성된 암호이고, 사전식으로 가능성 있는 암호를 모두 출력하는 문제이다. 1. 먼저 얻은 배열을 sort() 한다. (문자열 순으로도 됨) L자리의 암호 얻기 위해서 DFS를 적용, 이 때 idx를 i+1을 넘겨주어 사전식으로 가능한 것들만 출력.. 2019. 10. 16.
백준 알고리즘 15665 (N과 M(11)) - python [문제] 백준 알고리즘 15665 (N과 M(11)) - python > https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net N과 M(10)에서 비내림차순 조건을 제외하고, 같은 수를 출력해도 되는 문제 1. 비내림차순 조건을 위해 사용했던 idx로 range 조절 방법을 뺀다. 2. 같은 수를 여러 번 골라도 되므로 visited 방법을 뺀다. [Code] N, M = map(int, input().split()) L = list(m.. 2019. 10. 16.
백준 알고리즘 2581 (소수) - python [문제] 백준 알고리즘 2581 (소수) - python > https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 1978번(소수 찾기)이랑 비슷한 문제이다. 다른 점은 배열이 주어지는 것이 아니라 범위가 주어지고, 소수들의 합을 출력하거나 소수가 범위안에 없을 때는 -1을 출력하는 정도이다. 1978번 풀었을 때와 풀이 방법은 거의 같다. 1이 아닌 요소(i)를 하나씩 꺼내면서 2~ i-1까지 나눠지는 수가 없을 때만을 골라낸다. 나눠지는 수가 존재하면 더 .. 2019. 10. 16.
728x90

티스토리툴바