본문 바로가기

Algorithm706

[Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자 [ Contents ] 1. 이진탐색 (Binary Search, 이분탐색) 이진탐색: 정렬된 자료를 절반씩 나누어서 탐색하는 방법 오름차순(또는 내림차순)으로 정렬된 자료에서 사용합니다. 찾고자 하는 숫자와 자료의 중간값과 비교하여 탐색 범위를 절반씩 줄여갑니다. 찾고자 하는 수보다 작으면 작은 쪽을, 크면 큰 쪽을 찾습니다. 이진탐색 과정 1) 찾는 값과 중앙값을 비교합니다. 2) 중앙값과 같다면 탐색 종료. 작다면 작은 쪽을 크다면 큰 쪽을 찾습니다. 3) 값을 찾을 때까지 1, 2 과정을 반복합니다. 예를 들어 32를 찾고자 한다면, 중앙값인 63과 값을 비교합니다. 63보다 작으니, 작은 쪽에서 찾습니다. 12, 32, 41의 중앙값은 '32'입니다. 32를 찾았으므로 종료합니다. 2. 이진탐색.. 2022. 2. 9.
[구현/수학] 백준 1769 3의 배수 - Python [ Contents ] 1. 문제 (링크 참조) 1769번: 3의 배수 문제가 잘 풀리지 않을 때, 문제를 바라보는 시각을 조금만 다르게 가지면 문제가 쉽게 풀리는 경험을 종종 해 보았을 것이다. 여러 가지 방법이 있지만 그 중 하나로 우리가 풀고 싶은 문제를 www.acmicpc.net 2. 문제 풀이 자연수 n이 주어집니다. n이 1의 자리가 될 때까지 각 자릿수를 더해 변환합니다. 각 자릿수를 더한 합이 3의 배수이면 더하기 전의 수도 3의 배수입니다. 1의 자리가 3의 배수(3, 6, 9) 일 경우, n은 3의 배수입니다. 2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학 [Algorithm] 단골 1번 문제, 구현 / 수학 [ Contents .. 2022. 2. 9.
[수학/소수] 백준 4948 베르트랑 공준 - Python [ Contents ] 1. 문제 (링크 참조) 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 2. 문제 풀이 n보다 크고 2n보다 작은 소수의 개수를 출력하는 문제입니다. 2022.02.08 - [Algorithm] - [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체 [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체 에라토스 테네스의 체를 통해서 소수를 판별하는 알고리즘을 알아보겠습니다. [ Contents ] 1. 소수 소수(Prime): 약수가 1과 자기 자신밖에 .. 2022. 2. 9.
[수학/소수] 백준 11653 소인수분해 - Python [ Contents ] 1. 문제 (링크 참조) 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 2. 문제 풀이 주어진 N을 소인수분해 하는 문제입니다. 2022.02.08 - [Algorithm] - [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체 [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체 에라토스 테네스의 체를 통해서 소수를 판별하는 알고리즘을 알아보겠습니다. [ Contents ] 1. 소수 소수(Prime): 약수가 1과 자기 자신밖에 없는 수 '소수'는 1과 자기 자신으로만 나누어 떨어지는 star7sss.tistory.com 에라토스 테네스의 체처럼, 2부터 나누는 수를 1씩 올려가.. 2022. 2. 9.
[수학/소수] 백준 2581 소수 - Python [ Contents ] 1. 문제 (링크 참조) 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 2. 문제 풀이 자연수 M이상 N이하의 소수들의 합과 최솟값을 구하는 문제입니다. 소수가 없을 경우에는 -1를 출력합니다. 2022.02.08 - [Algorithm] - [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체 [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체 에라토스 테네스의 체를 통해서 소수를 판별하는 알고리즘을 알아보겠습니다. [ Contents ] 1. 소수 소수(Prime): .. 2022. 2. 9.
[구현/수학] 백준 10250 ACM호텔 - Python [ Contents ] 1. 문제 (링크 참조) 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 2. 문제 풀이 호텔의 층 수와 층별 방의 개수가 주어졌을 때, n번째 방을 찾는 문제입니다. 방의 순서는 101, 201, 301... 과 같이 층 수가 높아지며, 마지막 층에 다다르면 1층 다음방(102)으로 넘어갑니다. 2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학 [Algorithm] 단골 1번 문제, 구현 / 수학 [ Contents ] 1.. 2022. 2. 9.
[Brute Force] 백준 2798 블랙잭 - Python [ Contents ] 1. 문제 (링크 참조) 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 2. 문제 풀이 N장에 카드 중 3장을 뽑아, M에 가장 가까운 수를 만드는 문제입니다. 2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법? [Algorithm] 브루트 포스(Brute Force)는 노가다 기법? [ Contents ] 1. 브루트 포스란? Brute(짐승 같은, 난폭한) + Force(힘, 폭력.. 2022. 2. 9.
[수학/소수] 백준 1929 소수 구하기 - Python [ Contents ] 1. 문제 (링크 참조) 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 2. 문제 풀이 M이상 N이하의 모든 소수를 출력하는 문제입니다. 2022.02.08 - [Algorithm] - [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체 [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체 에라토스 테네스의 체를 통해서 소수를 판별하는 알고리즘을 알아보겠습니다. [ Contents ] 1. 소수 소수(Prime): 약수가 1과 자기 자신밖에 없는 수 '소수'는 1과 자기 자신으로만 나누어 떨어.. 2022. 2. 8.
[Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체 에라토스 테네스의 체를 통해서 소수를 판별하는 알고리즘을 알아보겠습니다. [ Contents ] 1. 소수 소수(Prime): 약수가 1과 자기 자신밖에 없는 수 '소수'는 1과 자기 자신으로만 나누어 떨어지는 자연수입니다. 반대로 1과 자기 자신 외에 다른 약수가 있으면 '합성수'라고 합니다. '소수 판별'은 특별한 공식이 없으며, 정의대로 1과 자기자신 사이의 수 중 약수가 있는지 검증해야 합니다. 숫자가 클수록 검증해야 하는 숫자들이 많아지며, 계산복잡도도 높아집니다. 따라서 RSA와 같은 각종 보안 알고리즘에 응용되며, 소수 판별 알고리즘의 중요성도 커지고 있습니다. 만약 소수를 빠르게 찾아낼 수 있는 공식을 찾아낸다면, 블록체인을 비롯해서 사회 전반의 보안 알고리즘을 뚫어낼 수 있습니다. (그럴.. 2022. 2. 8.

티스토리툴바