Altiora Petamus

4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고,..

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 🤔생각해보기 DFS와 BFS의 기본 개념을 익히기 위한 문제다. 자바에서는 2차원 배열로 edge 들을 설정한 뒤에 해결했었는데 파이썬에서 딕셔너리를 활용하여 풀어보았다. 개인적으로는 2차원 배열이 가독성이 끔찍하다고 느껴져서인지 어려워하는 편인데 딕셔너리를 활용해보니 이해하기도 편하고 훨씬 쉽게 해결 할 수 있는 것 같다. 성공 코드 from collections import deque from collections imp..

BinaryGap coding task - Learn to Code - Codility Find longest sequence of zeros in binary representation of an integer. app.codility.com Q. A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N. For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The n..

2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 🤔생각해보기 소수를 찾는 것은 여러가지 방법이 있지만, 평소 애용하는 방법은 제곱근을 통해서 구하는 방법이다. math.sqrt() 의 효율성에 대해 여러 의견이 있긴하던데, 아직까지 느려서 실패한 적은 없는 것 같다. 로직은 다음과 같이 처리하면 된다. 소수인지 검사해서 배열 prime에 담는다. prime이 비어있다면, -1 을 출력하고 값이 있다면 합과 최소값을 각각 출력한다. 성공 코드 # 소수 # 기본수학 2 # 소수를 찾아서 리스트에 넣기 # 배열에서 최소값 m..

11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 🤔생각해보기 n을 i 로 나눠보고 나머지가 0 이라면 출력, n //= i 를 사용하여 n을 몫으로 재설정 n이 i로 나누어지지 않는다면 i += 1 i^2가 n과 같아질 때까지 실행 만약 n = 10이라면, 2 로 나누어지고 n = 5 가 된다. 5는 소수이므로 i는 증가만 하다가 5가 되면서 루프를 빠져나오게 되고 결과가 2와 5만 출력되게 된다. 5는 소수이므로 ⇒ 소수를 판별하는 과정은 제곱근을 활용한다. 자세히 생각해보니 i와 n이 같아질 때까지 검사하는 것은 시간복잡도만 증가시킬 것 같았다. 애초에 루프를 i의 제곱이 n과 같아질 때까지만 실행시키면 된다. 성공 코드 n ..

최대공약수 # new in version python 3.5 import math math.gcd(6, 8) # 2 최소공배수 def lcm(a, b): return a * b // gcd(a, b) python 3.9 버전부터는 math에 최소공배수 함수가 추가되었다. # new in version 3.9 import math math.lcm(15, 25) # 75 Reference math — Mathematical functions — Python 3.9.5 documentation math — Mathematical functions This module provides access to the mathematical functions defined by the C standard. These f..

Reference 백준 10250번 문제풀이 처음 문제로 보이는 그림을 보면 2차원 배열을 사용해서 푸는걸까라는 생각이 들기 쉽다. 물론 2차원 배열로도 풀 수 있지만, 훨씬 쉬운 방법을 통해 풀 수 있다. 문제를 잘 읽어보면 6층 호텔의 10번째 손님은 4층의 객실에 배정된다. 만약 14번째 손님이라면? 2층에 배정된다. 즉 N / H 의 나머지값이 배정받을 객실의 층 수가 된다. 비슷한 로직으로 객실의 번호는 몫 + 1이 된다. 그렇다면 나머지가 0일 경우엔 어떻게 해야할까? 6번째 손님의 경우 601호에 배정되야 하지만, 나머지가 0이므로 층수를 알 수가 없어진다. 12번째 손님도 마찬가지이다. 나머지가 0일 경우 호텔의 층 수가 배정받을 객실의 층 수가 된다. 객실 번호는 몫이 된다. T = in..

Reference 백준 2869번 문제 풀이 이 문제를 푸는데 있어 중요한 키워드는 다음과 같다. 매일 올라가고 (+) 미끄러지고 (-) 목표 높이까지 (조건문 and 반복문) 이 점에 착안하여 현재 위치를 저장할 변수와 날짜를 카운트할 변수를 선언, 초기화해주고 최종적으로 카운트를 출력해주면 해결할 수 있다. A, B, V = map(int, input().split(" ")) position = 0 dayCount = 0 while position = V: break position -= B print(dayCount) 하지만 이런 단순한 풀이로는 시간복잡도를 통과할 수 없다. 언제나 그렇듯... 예제 입력 100 99..